【JDK源码】ArrayList 源码分析

怼烎@ 2023-10-01 11:36 12阅读 0赞

#### 文章目录 ####

*  ArrayList 源码分析
 *   *  1.简介
     *  2.属性
     *  3.构造方法
     *   *  ArrayList(int initialCapacity)
         *  ArrayList()
         *  ArrayList(Collection c)
     *  4.相关操作方法
     *   *  add(E e)
         *  add(int index, E element)
         *  addAll(Collection c)
         *  get(int index)
         *  remove(int index)
         *  remove(Object o)
         *  retainAll(Collection c)
         *  removeAll(Collection c)
     *  5.总结

## ArrayList 源码分析 ##

### 1.简介 ###

ArrayList是一种以数组实现的List，与数组相比，它具有动态扩展的能力，因此也可称之为动态数组。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Be1GBvYx-1641040712338)(ArrayList 源码分析.assets/image-20211228094028357.png)\]][img-Be1GBvYx-1641040712338_ArrayList _.assets_image-20211228094028357.png]

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        
    }

`ArrayList`继承于 **`AbstractList`** ，实现了 **`List`**, **`RandomAccess`**, **`Cloneable`**, **`java.io.Serializable`** 这些接口。

> 实现这些接口有什么作用呢？

*  ArrayList实现了`List`，提供了基础的添加、删除、遍历等操作。
 *  ArrayList实现了`RandomAccess`，提供了随机访问的能力。
 *  ArrayList实现了`Cloneable`，可以被克隆。
 *  ArrayList实现了`Serializable`，可以被序列化。

### 2.属性 ###

//默认容量，10。也就是通过new ArrayList()创建时的默认容量。
    private static final int DEFAULT_CAPACITY = 10;
    
    //空数组，用于空实例。这种是通过new ArrayList(0)创建时用的是这个空数组。
    private static final Object[] EMPTY_ELEMENTDATA = {
        };
    
    //1.用于默认大小空实例的共享空数组实例。通过new ArrayList()创建时用的是这个空数组
    //2.我们把它与EMPTY_ELEMENTDATA数组区分出来，以知道在添加第一个元素时容量需要增加多少。与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY（10）个元素。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    
    //1.数组列表中存储元素的数组缓冲区。数组列表的容量是数组缓冲区的长度
    //2.将在添加第一个元素时,长度扩展为DEFAULT_CAPACITY。
    //3.使用transient是为了不序列化这个字段
    transient Object[] elementData; 
    
    //ArrayList 所包含的元素个数,而不是elementData数组的长度。
    private int size;

*  **DEFAULT\_CAPACITY**：默认容量为10，也就是通过`new ArrayList()`创建时的默认容量。
 *  **EMPTY\_ELEMENTDATA**：空的数组，这种是通过`new ArrayList(0)`创建时用的是这个空数组。
 *  **DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA**：也是空数组，这种是通过`new ArrayList()`创建时用的是这个空数组，与EMPTY\_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT\_CAPACITY（10）个元素。
 *  **elementData**：真正存放元素的地方，使用`transient`是为了不序列化这个字段。
 *  **size**：真正存储元素的个数，而不是elementData数组的长度。

### 3.构造方法 ###

#### ArrayList(int initialCapacity) ####

传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY\_ELEMENTDATA空数组，如果小于0抛出异常。

//带初始容量的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小）
    public ArrayList(int initialCapacity) {
        
        if (initialCapacity > 0) {
        
            //如果传入的初始容量大于0，创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        
            //如果传入的初始容量等于0，使用空数组EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        
            //如果传入的初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

#### ArrayList() ####

不传初始容量，初始化为`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`空数组，会在添加第一个元素的时候扩容为默认的大小，即`10`。

//默认无参构造函数
    public ArrayList() {
        
        //DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

#### ArrayList(Collection c) ####

传入集合并初始化elementData，这里会使用拷贝把传入集合的元素拷贝到elementData数组中，如果元素个数为`0`，则初始化为`EMPTY_ELEMENTDATA`空数组。

//构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
    public ArrayList(Collection<? extends E> c) {
        
        //将集合转换为数组
        elementData = c.toArray();
        //如果elementData数组的长度不为0
        if ((size = elementData.length) != 0) {
        
            //  检查c.toArray()返回的是不是Object[]类型
            if (elementData.getClass() != Object[].class)
                //如果不是，重新拷贝成Object[].class类型
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
        
            //如果c的空集合，则初始化为空数组EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

> 为什么 `c.toArray()`返回的有可能不是`Object[]`类型呢？

这里我们看一个例子：

/**
     * @author xppll
     * @date 2021/12/28 10:01
     */
    public class ArrayListTest {
        
        public static void main(String[] args) {
        
            Father[] fathers = new Son[]{
        };
            //打印结果为：class [Lcom.itheima.test.Son;
            System.out.println(fathers.getClass());
            List<String> strList = new MyList();
            //打印结果为：class [Ljava.lang.String;
            System.out.println(strList.toArray().getClass());
        }
    }
    
    class Father {
        
    }
    
    class Son extends Father {
        
    }
    
    class MyList extends ArrayList<String> {
        
        /**
         * 子类重写父类的方法，返回值可以不一样
         * 但这里只能用数组类型，换成Object就不行
         * 这应该算是java本身的bug
         *
         * @return
         */
        @Override
        public String[] toArray() {
        
            // 为了方便举例直接写死
            return new String[]{
        "a", "b", "c"};
        }
    }

### 4.相关操作方法 ###

#### add(E e) ####

添加元素到末尾，平均时间复杂度为O(1)。

public boolean add(E e) {
        
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);  
        //把元素插到最后一位
        elementData[size++] = e;
        return true;
    }

检查是否需要扩容`ensureCapacityInternal(int minCapacity)`：

private void ensureCapacityInternal(int minCapacity) {
        
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

接着看`calculateCapacity(Object[] elementData, int minCapacity)` ：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        //如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10
        //获取“默认的容量”和“传入参数”两者之间的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

接着看`ensureExplicitCapacity(int minCapacity)` ：

private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }

扩容方法`grow(minCapacity)`：

private void grow(int minCapacity) {
        
        //oldCapacity为旧容量，newCapacity为新容量 
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        ///检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 以新容量拷贝出来一个新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

//使用最大容量
    private static int hugeCapacity(int minCapacity) {
        
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

扩容的整个过程：

1.  检查是否需要扩容
2.  如果elementData等于`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`则初始化容量大小为`DEFAULT_CAPACITY`
3.  新容量是老容量的`1.5`倍（`oldCapacity + (oldCapacity >> 1)`），如果加了这么多容量发现比需要的容量还小，则以需要的容量为准
4.  创建新容量的数组并把老数组拷贝到新数组

#### add(int index, E element) ####

添加元素到指定位置，平均时间复杂度为O(n)。

/**
     * 添加元素到指定位置，平均时间复杂度为O(n)
     *
     * @param index   指定元素插入的位置
     * @param element 要插入的元素
     */
    public void add(int index, E element) {
        
        // 检查是否越界
        rangeCheckForAdd(index);
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将index及其以后的元素都往后移一位，此时inex位置就空出来了
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        //将元素插入到index位置
        elementData[index] = element;
        //元素数量加一
        size++;
    }
    //检查是否越界
    private void rangeCheckForAdd(int index) {
        
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

整个流程：

1.  检查索引是否越界
2.  检查是否需要扩容
3.  把插入索引位置后的元素都往后挪一位
4.  在插入索引位置放置插入的元素
5.  元素数量加1

#### addAll(Collection c) ####

求两个集合的并集。

/**
     * 将集合c中所有元素添加到当前ArrayList中
     *
     * @param c
     * @return
     */
    public boolean addAll(Collection<? extends E> c) {
        
        //将集合c转为数组
        Object[] a = c.toArray();
        int numNew = a.length;
        //检查是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //将c中的元素全部拷贝到数组的最后
        System.arraycopy(a, 0, elementData, size, numNew);
        //集合中元素的大小增加c的大小
        size += numNew;
        //如果c不为空就返回true，否则返回false
        return numNew != 0;
    }

整个流程：

1.  拷贝c中的元素到数组a中
2.  检查是否需要扩容
3.  把数组a中的元素拷贝到elementData的尾部
4.  元素数量加c的大小

#### get(int index) ####

获取指定索引位置的元素，时间复杂度为O(1)。

public E get(int index) {
        
        //检查是否越界
        rangeCheck(index);
        //返回数组index位置的元素
        return elementData(index);
    }
    //检查是否越界
    private void rangeCheck(int index) {
        
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //返回指定位置的元素
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        
        return (E) elementData[index];
    }

整个流程：

1.  检查索引是否越界，这里只检查是否越上界，如果越上界抛出IndexOutOfBoundsException异常，如果越下界抛出的是ArrayIndexOutOfBoundsException异常
2.  返回索引位置处的元素

#### remove(int index) ####

删除指定索引位置的元素，时间复杂度为O(n)。

/**
     * 删除指定索引位置的元素，时间复杂度为O(n)。
     * @param index 指定索引位置
     * @return
     */
    public E remove(int index) {
        
        // 检查是否越界
        rangeCheck(index);
        modCount++;
    
        //获取index位置的元素
        E oldValue = elementData(index);
        //如果index不是最后一位，则将index之后的元素往前移一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        //将最后一个元素删除，帮助GC
        elementData[--size] = null; // clear to let GC do its work
        //返回删除的值
        return oldValue;
    }

整个流程：

1.  检查索引是否越界
2.  获取指定索引位置的元素
3.  如果删除的不是最后一位，则其它元素往前移一位
4.  将最后一位置为null，方便GC回收
5.  返回删除的元素

可以看到，ArrayList删除元素的时候并没有缩容。

#### remove(Object o) ####

删除指定元素值的元素，时间复杂度为O(n)。

/**
     * 删除指定元素值的元素，时间复杂度为O(n)。
     * @param o
     * @return
     */
    public boolean remove(Object o) {
        
        if (o == null) {
        
            //遍历整个数组，找到元素第一次出现的位置，并将其快速删除
            for (int index = 0; index < size; index++)
                //如果要删除的元素为null，则以null进行比较，使用==
                if (elementData[index] == null) {
        
                    fastRemove(index);
                    return true;
                }
        } else {
        
            //遍历整个数组，找到元素第一次出现的位置，并将其快速删除
            for (int index = 0; index < size; index++)
                //如果要删除的元素不为null，则进行比较，使用equals()方法
                if (o.equals(elementData[index])) {
        
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    /**
     * 专用的remove方法，跳过边界检查，并且不返回删除的值。
     *
     * @param index
     */
    private void fastRemove(int index) {
        
        //少了一个越界的检查
        modCount++;
        //如果index不是最后一位，则将index之后的元素往前移一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index,
                             numMoved);
        //将最后一位元素删除，帮助GC
        elementData[--size] = null; // clear to let GC do its work
    }

整个流程：

1.  找到第一个等于指定元素值的元素
2.  快速删除

`fastRemove(int index)`相对于`remove(int index)`少了检查索引越界的操作，可见jdk将性能优化到极致。

#### retainAll(Collection c) ####

求两个集合的交集。

/**
     * 批量删除元素
     * complement为true表示删除c中不包含的元素
     * complement为false表示删除c中包含的元素
     *
     * @param c
     * @param complement
     * @return
     */
    private boolean batchRemove(Collection<?> c, boolean complement) {
        
        final Object[] elementData = this.elementData;
        //使用读写两个指针同时遍历数组
        //读指针每次自增1，写指针放入元素的时候才加一
        //这样不需要额外的空间，只需要在原有的数组上操作就可以了
        int r = 0, w = 0;
        boolean modified = false;
        try {
        
            //遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
        
            //正常来说r最后是等于size的，除非c.contains()抛出了异常
            if (r != size) {
        
                // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
                System.arraycopy(elementData, r,
                        elementData, w,
                        size - r);
                w += size - r;
            }
            if (w != size) {
        
                // 将写指针之后的元素置为空，帮助GC
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）
                size = w;
                modified = true;
            }
        }
        // 有修改返回true
        return modified;
    }

整个流程：

1.  遍历elementData数组
2.  如果元素在c中，则把这个元素添加到elementData数组的w位置并将w位置往后移一位
3.  遍历完之后，w之前的元素都是两者共有的，w之后（包含）的元素不是两者共有的
4.  将w之后（包含）的元素置为null，方便GC回收；

#### removeAll(Collection c) ####

求两个集合的单方向差集，只保留当前集合中不在c中的元素，不保留在c中不在当前集体中的元素。

public boolean removeAll(Collection<?> c) {
        
        //集合c不能为空
        Objects.requireNonNull(c);
        //同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素
        return batchRemove(c, false);
    }

与`retainAll(Collection c)`方法类似，只是这里保留的是不在c中的元素。

### 5.总结 ###

1.  ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容
2.  ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)
3.  ArrayList添加元素到尾部极快，平均时间复杂度为O(1)
4.  ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)
5.  ArrayList从尾部删除元素极快，时间复杂度为O(1)
6.  ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)
7.  ArrayList支持求并集，调用addAll(Collection c)方法即可
8.  ArrayList支持求交集，调用retainAll(Collection c)方法即可
9.  ArrayList支持求单向差集，调用removeAll(Collection c)方法即可

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[img-Be1GBvYx-1641040712338_ArrayList _.assets_image-20211228094028357.png]: https://img-blog.csdnimg.cn/e57a0eb283af4e4cbac6b2886f2dc888.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/dc8eaf6c7b3c4fc0b2efea93e9d09f7e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16