ArrayList 源码解析和设计思路

一、继承体系

• ArrayList 继承自 AbstractList,AbstractList 实现了 List 接口的部分方法,为 List 的具体实现类提供了方便。
• AbstractList 是一个抽象类,它实现了 Collection 接口,也就间接实现了 Iterable 接口。

二、接口继承

• List 接口继承自 Collection 接口,Collection 继承自 Iterable 接口。
• List 接口代表有序的队列

三、标记接口

• RandomAccess 是一个标记接口,标识 ArrayList 支持快速随机访问,可以通过索引直接访问元素。
• Cloneable 和 Serializable 也是标记接口,前者表示可复制克隆,后者表示可序列化。

四、设计目的

• Java 集合框架的设计目的是为了更好地对集合数据进行操作,统一了访问方式,增强了代码的可读性、简洁性和可扩展性。
• 使用接口和抽象类来定义规范,然后由具体实现类来实现不同的数据结构和算法。
• 标记接口则用来对类型进行标记和区分,以便采取不同的算法和优化。

五、框架总体结构

• 最顶层是 Collection接口,定义了集合的基本操作。
• 然后分为 List、Set、Queue 等子接口,分别定义了有序、无序、队列等特性。
• 再通过 AbstractList、AbstractSet 等抽象类为子接口提供部分方法实现。
• 最后是具体的实现类,如 ArrayList、LinkedList、HashMap等。

六、工作原理

ArrayList 底层是通过动态数组(可自动扩容)实现的,它的工作原理如下:

• 初始化时,为一个初始容量为0的数组
• 当添加元素时,容量不够则自动扩容(默认扩容为原来的1.5倍)
• 插入和访问元素通过索引直接操作数组,性能较高
• 删除元素需要移动其他元素以保证连续存储
• 由于自动扩容,在末尾插入元素效率很高,但在中间位置插入效率较低

ArrayList 的源码注释如下:

/**
 * 默认初始容量为 10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 用于储存元素的数组缓冲区
 */
transient Object[] elementData; 

/**
 * ArrayList 中元素的数量
 */
private int size;

// 其他方法...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看出，ArrayList 内部通过一个 Object 数组存储元素,size 变量记录当前元素数量,通过自动扩容机制来支持动态增长。这种基于动态数组的实现,决定了 ArrayList 查询快、增删慢的特点。

七、创建List对象初始化？还是add()添加元素初始化?

在 Java JDK 1.8 中,ArrayList 的默认初始容量 10 是在第一次通过无参构造函数创建 ArrayList 对象时初始化的,而不是在添加第一个元素时初始化。

ArrayList 有三种构造方式:

1. ArrayList()

   /**
    * 构造一个初始容量为10的空列表
    */
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }
   1
   2
   3
   4
   5
   6

   使用无参构造函数时,底层会初始化一个初始容量为 10 的空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

2. ArrayList(int initialCapacity)

   /**
    * 构造一个具有指定初始容量的空列表
    */
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13

   使用这个指定容量的构造函数,会根据指定的容量初始化底层数组大小。

3. ArrayList(Collection<? extends E> c)

   /**
    * 构造一个包含指定collection的元素的列表,按迭代器返回元素的顺序
    */
   public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       if ((size = elementData.length) != 0) {
           // c.toArray可能(错误地)不同时使用Object[]...
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
           // 使用空数组替换以允许缓冲区进行正常增长
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

   使用这个构造函数会根据提供的集合的大小创建底层数组。

使用无参构造函数 ArrayList() 时,底层数组的初始容量才会被初始化为 10。其他两种构造函数要么根据用户指定的容量初始化,要么根据提供的集合大小初始化。而添加元素时则不会再初始化容量,只是在容量不足时按照需求扩容。

七、add(E e)添加元素

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5

1. ensureCapacityInternal(size + 1): 这一行代码调用了ensureCapacityInternal方法，它用于确保ArrayList内部数组的容量足够来存放新增的元素。如果需要增加ArrayList的容量，它会创建一个新的更大的数组，并将原来的元素复制到新数组中。

2. elementData[size++] = e;: 这一行代码将新的元素e添加到ArrayList的内部数组elementData中，并且将size变量递增，表示列表中的元素数量增加了一个。这里使用size++是因为要先将元素添加到size所指示的位置，然后再递增size，以便下次添加元素时能够添加到正确的位置。

3. return true;: 最后，方法返回true，表示添加操作成功。

---

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
1
2
3
4
5
6
7

这段代码是ArrayList中的ensureCapacityInternal(int minCapacity)方法的部分源码

1. if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {: 这一行代码用于检查elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，该常量表示一个空数组。如果是空数组，说明当前ArrayList没有初始化容量，需要根据默认容量和需要添加的最小容量来确定实际容量。

2. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);: 如果elementData是空数组，则会根据默认容量DEFAULT_CAPACITY和需要添加的最小容量来确定实际的最小容量。DEFAULT_CAPACITY是ArrayList默认的初始容量大小。

3. ensureExplicitCapacity(minCapacity);: 接下来调用ensureExplicitCapacity(minCapacity)方法来确保ArrayList的内部数组容量能够容纳至少minCapacity个元素。这个方法会比较当前数组的容量和需要的最小容量，如果当前容量不足，则会扩大内部数组的容量以满足需求。

---

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
1
2
3
4
5
6
7

-这段代码是ArrayList中的ensureExplicitCapacity(int minCapacity)方法的部分源码

1. modCount++;: 这一行代码递增了modCount变量的值。modCount用于记录结构修改次数，主要用于在迭代过程中检测并发修改。每当进行结构性修改时（如添加或移除元素），modCount会递增，表示ArrayList的结构发生了变化。

2. if (minCapacity - elementData.length > 0) grow(minCapacity);: 这里使用了溢出安全的计算方式来判断是否需要扩容内部数组。如果当前容量不足以容纳最小容量minCapacity个元素，则需要调用grow(minCapacity)方法来扩大内部数组的容量。

3. grow(int minCapacity): 当需要扩容时，会调用grow(int minCapacity)方法来实现容量的扩充。grow()方法会根据需要的最小容量来确定新的容量大小，并将原来的元素复制到新的更大的数组中。

---

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }
1
2
3
4
5
6
7
8
9
10

这段代码是ArrayList中的grow(int minCapacity)方法的部分源码

1. int oldCapacity = elementData.length;: 获取当前内部数组的容量，即原来的容量大小。

2. int newCapacity = oldCapacity + (oldCapacity >> 1);: 原来的容量大小计算出新的容量大小。新的容量大小会是原来容量的1.5倍，通过右移一位实现了除以2的操作。原来容量大小 + 容量大小的一半

3. if (newCapacity - minCapacity < 0) newCapacity = minCapacity;: 如果新的容量仍然小于需要的最小容量minCapacity，则将新的容量调整为minCapacity，确保容量能够满足需求。

4. if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);: 检查新的容量是否超出了最大数组大小MAX_ARRAY_SIZE，如果超出则调用hugeCapacity()方法来确定合适的容量大小，这是为了避免数组大小超出Java虚拟机的限制。

5. elementData = Arrays.copyOf(elementData, newCapacity);: 最后，使用Arrays.copyOf()方法将原来的元素复制到新的更大的数组中，完成了内部数组的扩容过程。

grow()方法主要负责处理ArrayList内部数组的扩容问题。它会根据旧的容量大小计算出新的容量大小，并根据需要调整为满足最小容量要求的合适大小。然后将原来的元素复制到新的更大的数组中，完成数组的扩容操作。这样可以确保在需要添加大量元素时，ArrayList内部数组能够容纳足够多的元素。

八、remove（int index）删除元素

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这段代码是ArrayList中的remove(int index)方法的部分源码

1. rangeCheck(index): 这一行代码调用了rangeCheck方法来检查索引是否越界，确保要移除的元素在有效范围内。如果索引不在有效范围内，会抛出IndexOutOfBoundsException。

2. modCount++: 这里递增了modCount变量的值。modCount用于记录结构修改次数，主要用于在迭代过程中检测并发修改。每当进行结构性修改时（如添加或移除元素），modCount会递增，表示ArrayList的结构发生了变化。

3. E oldValue = elementData(index): 这一行代码获取要移除的元素，并将其保存为oldValue。

4. int numMoved = size - index - 1;: 计算需要向前移动的元素个数，即原始数组中位于被删除元素后面的元素个数。

5. System.arraycopy(elementData, index+1, elementData, index, numMoved): 如果存在需要向前移动的元素，则使用System.arraycopy方法将这些元素向前移动，以填补被删除元素的位置。

6. elementData[--size] = null: 将列表中最后一个元素置空，以便让GC进行清理工作。

7. 返回oldValue：返回被删除的元素的值。

通过以上步骤，remove()方法实现了在指定位置上删除元素的功能。它首先进行了参数的合法性检查，然后递增了modCount，接着移动需要向前移动的元素，将列表中最后一个元素置空，并返回被删除的元素的值。

---

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这段代码是ArrayList中的remove(Object o)方法的部分源码

1. 如果传入的对象 o 为空（null）：

   • 通过 for 循环遍历 elementData 数组，寻找为 null 的元素。
   • 当找到第一个为 null 的元素后，调用 fastRemove(index) 方法进行删除，并返回 true。

2. 如果传入的对象 o 不为空（non-null）：

   • 通过 for 循环遍历 elementData 数组，寻找与传入对象相等的元素。
   • 当找到第一个与传入对象相等的元素后，调用 fastRemove(index) 方法进行删除，并返回 true。

3. 如果未找到符合条件的元素，则直接返回 false。

fastRemove(index) 方法用于快速删除指定索引位置的元素。通过这种方式，remove(Object o) 方法能够在列表中移除满足特定条件的第一个元素，并返回是否成功移除的布尔值。

八、线程安全问题

ArrayList存在线程安全问题的本质在于其内部的elementData、size和modCount等变量，在进行各种操作时没有加锁，并且这些变量的类型也不是volatile的。因此，如果多个线程对这些变量进行操作，则可能出现值被覆盖的情况。需要强调的是，只有当ArrayList作为共享变量时，才会出现线程安全问题；当ArrayList是方法内的局部变量时，则不存在线程安全问题。