ArrayList源码解析

本文是基于JDK8进行分析的，其他版本会有些不同，请以具体版本为准。

ArrayList简介

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

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

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




  }

• List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。

• RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。

• Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。

• Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

ArrayList的字段

public class ArrayList {


    private static final long serialVersionUID = 8683452581122892189L;



    /**
     * 默认的初始容量，当使用空参构造器时，大小即为10。
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 存储数据的容器（用于空实例），区分下面的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};


    /**

     * 用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来，以便知道添加第一个元素时要扩容多少。
     * 这个是当使用空参构造器时，默认的存储容器。
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList数据的数组。
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 数组列表的大小(包含的元素数量)。
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;


    /**
     * 要分配的数组的最大大小。
     * 减去8是因为数组中存放了一些头部信息。
     * The maximum size of array to allocate. Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in OutOfMemoryError: Requested array size exceeds VM limit.
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

ArrayList的构造器

public class ArrayList {


    private static final long serialVersionUID = 8683452581122892189L;


    /**

     * 空参（默认）构造器，构造的实例便是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，它的初始化大小就是 10.
     * Constructs an empty list with an initial capacity of ten.
     */

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 指定容量大小（非负）的构造器。
     * Constructs an empty list with the specified initial capacity.
     *
     * @param initialCapacity the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 构造指定大小的实例。
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 空容量/空集合构造的实例便是 EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 容量为负数
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
    }


    /**
     * 按照指定集合（非空）的迭代器返回的顺序，构造一个包含指定集合元素的列表。
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */

    public ArrayList(Collection<? extends E> c) {
        // 集合转数组
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            // 数组容量不为空
            if (c.getClass() == java.util.ArrayList.class) {
                // 如果指定的集合也是 ArrayList，则可以直接赋值。
                elementData = a;
            } else {
                // 反之，调用Arrays.copyOf进行拷贝。
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // 空容量/空集合构造的实例便是 EMPTY_ELEMENTDATA
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }
}

ArrayList中一些方法

public class ArrayList {


    private static final long serialVersionUID = 8683452581122892189L;


    /**

     * 将这个ArrayList实例的容量调整为列表的当前大小。
     * 应用程序可以使用此操作来最小化ArrayList实例的存储空间。
     */

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
        }
    }


    /**

     * 返回此列表中的元素数。
     */
    public int size() {
        return size;
    }

    /**
     * 如果此列表不包含元素，则返回 true 。
     */
    public boolean isEmpty() {
        //注意=和==的区别
        return size == 0;
    }

    /**
     * 如果此列表包含指定的元素，则返回true。
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }


    /**
     * 返回指定元素在此列表中第一次出现的索引，如果此列表不包含该元素，则返回-1。
     * 还有个 lastIndexOf, 遍历顺序是相反的。
     */

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * 返回该ArrayList实例的浅拷贝。(元素本身不会被复制。)
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    /**
     * 返回列表中指定位置的元素。
     */
    public E get(int index) {
        // 边界检查 index >= size
        rangeCheck(index);

        return elementData(index);
    }
    
    /**
     * 将此列表中指定位置的元素替换为指定元素。
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    
    // 核心方法下面分析。
}

ArrayList扩容机制（重要）

在日常开发中，我们使用ArrayList最多的方式就是如下：

package sort;

import sort.impl.CountingSort;




import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author WanJie
 * @since 2023-03-19 20:57
 */
public class Test {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
    }
}

那我就从以上用法开始分析它的构造扩容过程。其他情况也是类似的，只是在个别判断上有出入。

构造

首先调用空参构造器，将elementData初始化为一个空数组。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

调用add方法

/**
 * 将指定的元素追加到此列表的末尾。
 */
public boolean add(E e) {
    // 计算所需最小容量 minCapacity，并根据计算出来的所需容量进行扩容。
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 存入数据，size增加
    elementData[size++] = e;
    return true;
}

扩容流程

按照方法顺序阅读。

private void ensureCapacityInternal(int minCapacity) {
    // 交给 ensureExplicitCapacity 来处理。
    // calculateCapacity 来计算实际的 minCapacity
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}


private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是空参默认构造的，则大小初始化为10。
        // 当数据越来越多，容量则以实际的 minCapacity 为准。
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果是其他方式构造的，比如指定容量/集合方式，则以指定的 minCapacity 为准。
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    // 实际所需最小容量 - 当前实际容量 > 0：容量不够了，该扩容了！。
    if (minCapacity - elementData.length > 0)
        // 扩容核心方法
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
 *
 * @param minCapacity 需的最小容量
 */
private void grow(int minCapacity) {
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;


    // (oldCapacity >> 1，位运算，等同于 oldCapacity / 2，位运算的效率更高。
    // 首先扩容为原来的 1.5 倍。
    int newCapacity = oldCapacity + (oldCapacity >> 1);


    // 如果扩容后依旧不满足最小需求大小（minCapacity），则直接扩容成最小需求大小。
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 到这里扩容后的容量（newCapacity）就满足最小需求了。
    // 但是这里继续判断扩容后的容量（newCapacity）与数组最大容量大小（MAX_ARRAY_SIZE）；
    // 如果 newCapacity 超出了 MAX_ARRAY_SIZE，则对其作进一步约束：
    //      1.最小需求容量都已经超过了 MAX_ARRAY_SIZE，则最后扩容后的容量就是 Integer.MAX_VALUE。
    //      2.最小需求容量没有超过，则最后扩容后的容量就是 MAX_ARRAY_SIZE。
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    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;
}

快速失败机制&失败安全机制

不知道大家在查看以上代码时，有没有发现一些方法会对一个变量操作 modCount 。

它就是Java集合中实现快速失败机制的作用点。

private void ensureExplicitCapacity(int minCapacity) {

    // 添加时会修改modCount

    modCount++;





    if (minCapacity - elementData.length > 0)

        // 扩容核心方法

        grow(minCapacity);

}

什么是快速失败机制&失败安全机制？

概念：系统运行中，如果有错误发生，那么系统立即结束，这种设计就是快速失败。系统运行中，如果有错误发生，系统不会停止运行，它忽略错误（但是会有地方记录下来），继续运行，这种设计就是失败安全。

说到快速失败、失败安全时，我们首先想到的应该是这是一种机制、一种思想、一种模式，它属于系统设计范畴，其次才应该想到它的各种应用场景和具体实现。

作用场景：Java集合、Dubbo失败机制策略。

Java集合中的快速失败机制

现象：在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了增加、删除、修改操作，则会抛出ConcurrentModificationException。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出ConcurrentModificationException异常，终止遍历。类似于乐观锁的一种思想。

注意：这里异常的抛出条件是检测到 modCount！= expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

private void ensureExplicitCapacity(int minCapacity) {

    // 添加时会修改modCount

    modCount++;





    if (minCapacity - elementData.length > 0)

        // 扩容核心方法

        grow(minCapacity);

}

    public void forEachRemaining(Consumer<? super E> consumer) {
        // ...省略无关代码
        // 在使用迭代器遍历时便会对 modCount 进行检查。
        checkForComodification();
    }


    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Java集合中的失败安全机制

现象：采用失败安全机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发ConcurrentModificationException。

缺点：基于拷贝内容的优点是避免了ConcurrentModificationException，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。这也就是他的缺点，同时，由于是需要拷贝的，所以比较吃内存。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。s

Dubbo中的快速失败

参考其他文章或后续补充。

ArrayList与Vector的区别

相同点

都是基于数组实现，保证元素的有序行，可以基于下标查询，并且默认容量都是 10。

不同点

• 1、ArrayList 是线程不安全的，而 Vector 中的方法都被 synchronized 标注，是线程安全的。
• 2、在进行扩容时，ArrayList 是扩容 1.5 倍，而 Vector 是默认是扩容 2 倍，但也可以指定扩容数量。

// Vector#grow()
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // capacityIncrement指定的扩容量，未指定则扩容为原来的2倍。
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

参考

• JavaGuide
• why技术