ArrayList集合源码分析

ArrayList的扩容机制

  • ArrayList中维护了一个Object类型的数组elementData

    1
    transient Object[] elementData; // 非私有，以简化嵌套类访问非私有，以简化嵌套类访问

  • 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容elementData为1.5倍。

  • 如果是使用的指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.ArrayList;

//ArrayList集合源码解读
public class ArrayListSource {

    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();	//见第1点
        for (int i = 1; i <= 15; i++) {
            arrayList.add(i);	//见第2点
        }
        System.out.println(arrayList);
    }
}
1
2
3
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

1.无参构造器，初始elementData的容量为0

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

2.add方法,add()方法内部
2.1 E e：这个方法的入参类型是一个泛型，可以是String,Student等类型
2.2 ensureCapacityInternal(size + 1) ：首先进入这个方法判断是否需要扩容
2.3 elementData[size++] = e ：将要添加的元素的值赋给数组的第size个元素，然后size自增1

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

3.ensureCapacityInternal(size + 1)方法内部
3.1 int minCapacity：字面意思 最小容量
3.2 calculateCapacity(elementData, minCapacity) ： 分析见第4点
3.3 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)) ：分析见第5点

1
2
3
4
5
6
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

4.calculateCapacity(elementData, minCapacity)方法内部
4.1 判断elementData的容量是否为0，如果为0，返回一个默认值：10；如果不为0，则直接返回传过来的最小容量

1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

5.ensureExplicitCapacity(calculateCapacity(elementData, minCapacity))方法内部
5.1 int minCapacity：将上一个方法确定的最终的容量传进来
5.2 modCount++ ：modCount自增1，modCount表示修改次数，每增加一个元素，modCount都会增加1
拓展：在这些线程不安全的集合中，在某些方法中，初始化迭代器时会给这个modCount赋值，
如果在遍历的过程中，一旦发现这个对象的modCount和迭代器存储的modCount不一样，就会报错。
5.3 minCapacity与elementData的长度进行比较，如果大于0，就会进行扩容（grow(minCapacity)方法见第6点），否则直接返回

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    // overflow-conscious code
    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);
}

6.grow(int minCapacity)方法，真正扩容的地方
6.1 定义oldCapacity、newCapacity两个容量分别表示原来的容量和最新的容量。
oldCapacity的大小为elementData的大小
newCapacity的大小为原来的1.5倍
6.2 判断最新的容量和需要的最小容量进行比较，如果最新的容量比需要的最小容量还要小，那么将最新的容量更新为所需要的最小 的容量；否则不变
6.3 判断最新的容量是否大于规定的最大容量（一般不会），hugeCapacity(minCapacity)方法暂不分析
6.4 Arrays.copyOf(elementData, newCapacity)：将elementData进行扩容，扩容至最新的大小