ArrayList底层原理学习

清疚 2023-07-14 10:55 124阅读 0赞

一直以来，ArrayList都是一个熟悉的陌生人一样的存在，用都会用，也知道底层是数组，再深入问细节就懵逼。

## 1.构造方法 ##

public ArrayList()  
public ArrayList(int initialCapacity)  
public ArrayList(Collection<? extends E> c)  
jdk1.8中ArrayList的无参构造创建的是一个空数组，等真正去添加元素的时候才会创建一个大小为10的数组。

## 2.扩容机制 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70]  
如果是第一次添加则设置默认大小10，判断是否需要扩容是比较minCapacity和当前elementData数组的大小，也就是比较添加操作后预计的大小和当前大小进行比较，如果预计大小或超过当前大小则扩容。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 1]  
每次扩容倍数为1.5，在扩容还需要判断是否超过最大限制MAX\_ARRAY\_SIZE = Integer.MAX\_VALUE - 8，当超过MAX\_ARRAY\_SIZE时，若超过了Integer的最大值则抛出OutOfMemoryError，若在MAX\_ARRAY\_SIZE与Integer.MAX\_VALUE 之间时则取Integer.MAX\_VALUE为当前容量。

## 3.并发控制 ##

一边遍历ArrayList一边add的时候经常会抛出ConcurrentModificationException异常。  
这是因为底层有个modCount在记录修改次数，每次对ArrayList进行增删改操作时都会对modCount++。遍历、排序等操作会先获取一次modCount，若遍历的过程modCount发生变化则抛出ConcurrentModificationException异常。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 2]  
这是读操作可能会抛出ConcurrentModificationException异常，通过迭代器对ArrayList进行读写操作也可能会抛出这个异常。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 3]  
写操作主要判断的是数组越界，在并发的时候可能存在多个线线程都判断不需要扩容，都进行add操作，可能导致数组越界。

## 4.subList的实现 ##

ArrayList的subList并不是想象中的拷贝，对subList进行add会对List产生影响。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 4]  
ArrayList中定义了一个内部类SubList  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 5]  
可以看出构造SubList的过程并不是复制原List的数据，而是将原List作为parent赋给该subList，并记录该subList可访问的偏移地址、总数和当前的修改次数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 6]  
当对subList进行set操作时，实际上是在对原list进行set。在刚才的例子中我先获取了两个subList，此时的modCount为4，当subList1进行一次add操作后，subList1和原list的modCount都更新为了5，为subList2的modCount还是4，因此会抛出ConcurrentModificationException。  
![在这里插入图片描述][20200314184600203.png]  
subList并没有去开辟空间复制数组，而是在返回list的一个视图，，多个subList的情况下不适合进行修改操作。

## 5.jdk1.8新增的ArrayListSpliterator ##

用于多线程中list的分割和遍历，例如将一个大小为20的list分割给四个线程执行，[参考][Link 1]

import java.util.ArrayList;
    import java.util.Spliterator;
    import java.util.function.Consumer;
    
    public class SpliteratorInArrayListStudy {
        public static void main(String[] args) {
            // 初始化list
            ArrayList<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < 20; i++) {
                list.add(i + 1);
            }
            //四线程均分配比方式
            Spliterator<Integer> spliterator01 = list.spliterator();           //01中有20个元素
            Spliterator<Integer> spliterator02 = spliterator01.trySplit();    //01中有10个元素,02中有10个元素
            Spliterator<Integer> spliterator03 = spliterator01.trySplit();    //01中有5个元素,02中有10个元素,03中有5个元素
            Spliterator<Integer> spliterator04 = spliterator02.trySplit();    //01中有5个元素,02中有5个元素,03中有5个元素,04中有5个元素
            MyThread4Spliterator<Integer> t01 = new MyThread4Spliterator<Integer>(spliterator01);
            MyThread4Spliterator<Integer> t02 = new MyThread4Spliterator<Integer>(spliterator02);
            MyThread4Spliterator<Integer> t03 = new MyThread4Spliterator<Integer>(spliterator03);
            MyThread4Spliterator<Integer> t04 = new MyThread4Spliterator<Integer>(spliterator04);
            t01.setName("001");
            t02.setName("002");
            t03.setName("003");
            t04.setName("004");
    
            t01.start();
            t02.start();
            t03.start();
            t04.start();
        }
    }
    class MyThread4Spliterator<T> extends Thread {
        // 寄存变量
        private Spliterator<T> list;
    
        // 构造 - 传递参数
        public MyThread4Spliterator(Spliterator<T> list) {
            setList(list);
        }
    
        // 线程调用run
        @Override
        public void run() {
            Spliterator<T> list2 = getList();
            list2.forEachRemaining(new Consumer<T>() {
    
                @Override
                public void accept(T t) {
                    System.out.println(Thread.currentThread().getName()+" === "+t);
                }
    
            });
        }
    
        public Spliterator<T> getList() {
            return list;
        }
    
        public void setList(Spliterator<T> list) {
            this.list = list;
        }
    }

Spliterator接口还有很多属性和默认实现，见https://blog.csdn.net/starexplode/article/details/80567758

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70]: /images/20230529/2ee38a9d73cd42d69228fc1c314f58ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 1]: /images/20230529/a8b354f336cb4fee86a29224e7b753f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 2]: /images/20230529/181a81bb62f0426993880363ec5df55f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 3]: /images/20230529/d69c909e7d2e4556a450507b0f2e9015.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 4]: /images/20230529/314a45cfb4284a2c96ec3663ae2dbef1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 5]: /images/20230529/724f2efa650841fcad98a811b765aa4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70 6]: /images/20230529/224b3321e5a6493db2f774c9fd2b5d8b.png
[20200314184600203.png]: /images/20230529/ea3dc50133fb454c85e8f8736721caaa.png
[Link 1]: https://www.cnblogs.com/liuyuhangCastle/p/9704090.html