剖析 ArrayList

ArrayList 是 Java 中的一个动态数组实现类，可以根据需要自动调整数组的大小

1. 基本用法

ArrayList 是一个泛型容器，新建 ArrayList 需要实例化泛型参数，比如：

1
2
ArrayList<Integer> intList = new ArrayList<Integer>();
ArrayList<String> strList = new ArrayList<String>();

ArrayList 的主要方法有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean add(E e) //添加元素到末尾
public boolean isEmpty() //判断是否为空
public int size() //获取长度
public E get(int index) //访问指定位置的元素
public int indexOf(Object o) //查找元素，如果找到，返回索引位置，否则返回-1
public int lastIndexOf(Object o) //从后往前找
public boolean contains(Object o) //是否包含指定元素，依据是equals方法的返回值
public E remove(int index) //删除指定位置的元素，返回值为被删对象
//删除指定对象，只删除第一个相同的对象，返回值表示是否删除了元素
//如果o为null，则删除值为null的对象
public boolean remove(Object o)
public void clear() //删除所有元素
//在指定位置插入元素，index为0表示插入最前面，index为ArrayList的长度表示插到最后面
public void add(int index, E element)
public E set(int index, E element) //修改指定位置的元素内容

简单示例：

1
2
3
4
5
6
ArrayList<String> strList = new ArrayList<String>();
strList.add("Hello");
strList.add("ArrayList");
for(int i=0; i<strList.size(); i++){
    System.out.println(strList.get(i));
}

2. 基本原理

ArrayList 内部主要包含：

  • 一个 Object 数组 elementData 记录存入的元素；
  • 一个 int 类型的变量 size 记录实际存储的元素个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 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;

2.1 构造函数

ArrayList 的构造函数主要有三个：

1
2
3
public ArrayList();  // 无参构造函数
public ArrayList(int initialCapacity); // 指定初始容量
public ArrayList(Collection<? extends E> c)； // 传入一个集合

先看无参构造函数，无参构造函数很简单，将 elementData 数组赋值为常量 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这是一个空数组

1
2
3
4
5
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

指定初始容量的构造函数如下，如果初始容量大于 0 就创建一个 Object 类型的数组，容量为 initialCapacity 并赋值给 elementData；如果初始容量等于 0 就将 elementData 数组赋值为常量 EMPTY_ELEMENTDATA，这也是一个空数组

1
2
3
4
5
6
7
8
9
10
11
12
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);
    }
}

private static final Object[] EMPTY_ELEMENTDATA = {};

传入集合的构造函数如下，用于将一个现有的 Collection（集合）转换为一个新的 ArrayList 对象

1
2
3
4
5
6
7
8
9
10
11
12
13
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();  // 将传入的集合 'c' 转换成一个数组 'a'。
    if ((size = a.length) != 0) {  // 获取数组 'a' 的长度并赋值给 'size'，如果数组不为空，进入if块。
        if (c.getClass() == ArrayList.class) {  // 如果传入的集合 'c' 是一个 ArrayList 实例
            elementData = a;  // 直接使用传入集合的数组 'a'，没有复制数据
        } else {  // 如果传入的集合不是 ArrayList
            elementData = Arrays.copyOf(a, size, Object[].class);  // 复制 'a' 数组，创建一个新的数组 'elementData'
        }
    } else {  // 如果数组 'a' 是空的
        elementData = EMPTY_ELEMENTDATA;  // 将 'elementData' 赋值为一个空数组常量 EMPTY_ELEMENTDATA
    }
}

2.2 add 方法

add 方法用于向 ArrayList 末尾添加元素

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

首先调用 ensureCapacityInternal(int minCapacity) 方法检查容量是否足够，当前只添加一个元素，所以需要的最小容量为 size + 1​

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

该方法先调用了 calculateCapacity() 方法计算所需容量

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;
}

calculateCapacity() 方法中，如果当前 elementData 数组等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即还是个空数组，容量就取 DEFAULT_CAPACITY 和 minCapacity 中较大的一个，DEFAULT_CAPACITY 是一个常量，值为 10，否则就返回 minCapacity​

所以 ArrayList​​ 的初始容量为 0​​，添加第一个元素时才会扩容到 10​​

接着 calculateCapacity() 方法调用 ensureExplicitCapacity() 方法，判断所需最小容量是否大于当前数组的长度，如果是则调用 grow() 方法扩容，否则无需扩容直接返回

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

​modCount​ 这个变量用来记录集合被修改的次数。每当集合结构发生变化（例如添加、删除元素等），modCount 就会增加 1，在使用迭代器时，迭代器会检查 modCount 是否发生变化，如果变化了，就会抛出 ConcurrentModificationException，以防止在遍历集合时，集合被修改，导致不一致的结果。

grow() 函数正式对数组进行扩容

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);
}

newCapacity = oldCapacity + (oldCapacity >> 1); 即新的容量是原容量的 1.5 倍。

如果新容量小于所需最小容量，则将所需的最小容量赋值给新容量；

如果新容量大于 MAX_ARRAY_SIZE 需要调用 hugeCapacity() 方法，该方法将新容量设置为 Integer 类型的最大值

所以 ArrayList 的容量是有限的，最大为 Int 类型的最大值

1
2
3
4
5
6
7
8
9
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

最后 grow() 方法使用 Arrays.copyOf(elementData, newCapacity) 方法创建一个新的数组，容量为 newCapacity 并赋值给 elementData，完成扩容。

扩容完成后，add() 方法执行 elementData[size++] = e; 将元素添加到数组末尾并将 size + 1​

同时整个过程没有对 null 值做任何处理，所以 ArrayList​​ 是可以添加 null​​ 值的

2.3 remove 方法

remove() 方法用于删除指定下标处的元素并返回删除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

首先会计算需要移动的元素数量 size - index - 1，然后调用 System.arraycopy() 方法移动元素。

elementData[--size]=null； 这行代码将 size ​减 1，同时将最后一个位置设为 null，设为 null 后不再引用原来对象，如果原来对象也不再被其他对象引用，就可以被垃圾回收。

2.4 ensureCapacity 方法

ArrayList() 还有一个 ensureCapacity() 方法是提供给用户调用的，用于在向 ArrayList 添加大量元素之前对数组进行扩容，以减少增量重新分配的次数

1
2
3
4
5
6
7
8
9
10
11
12
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;
        
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

3. System.arraycopy() 和 Arrays.copyOf() 方法

ArrayList 中大量调用了这两个方法

3.1 System.arraycopy() 方法

System.arraycopy() 是一个用于快速复制数组元素的本地(native)方法，它提供了一种高效的方式来复制一个数组的部分或全部内容到另一个数组中

1
2
3
4
5
6
7
8
9
10
11
/**
* 复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

3.2 Arrays.copyOf() 方法

Arrays.copyOf() 方法用于创建一个新的类型为 T[] 的数组，长度为 newLength，并复制原始数组 original 中的元素到新数组。

1
2
3
4
5
6
7
8
9
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

首先检查要创建的新数组类型是否是 Object[]：

  • 如果是 Object[]，直接创建一个 Object ​数组
  • 如果不是，则使用反射 API 的 Array.newInstance ​方法，根据类型创建特定类型的数组

然后使用 System.arraycopy() 方法将原始数组中的数据复制到新数组

‍