一行一行读Java源码——ArrayList

2022-03-01 20:22:32

ArrayList可能是日常开发中使用频率最高的集合类型之一（另一个是HashMap），但是有些细节不细究、不常回顾的话总是会慢慢模糊，比如有一语句List<Object> objects = new ArrayList<>(); ，试问此时objects 的容量（capacity）是多大？
尽管类似这样的细节对代码质量的影响可能不大，但作为Java程序员我们还是有必要去熟悉这些细节并挖掘隐含在这些细节背后的设计奥秘。鉴于此，我觉得有必要再次细度Java ArrayList源码。
首先列举一下本文所涉及的知识点：
1、ArrayList内部如何实现？适合什么样的操作场景？
2、new ArrayList<>()方法调用后所提供的ArrayList容量是多大？
3、未提供容量值，但是调用add方法后ArrayList容量值是多大？
4、ArrayList什么时候扩容？如何扩容？扩多大？
5、ArrayList是否线程安全？
6、ArrayList如何序列化？
7、ArrayList最大容量是多大？

别废话，请开始你的表演

// 类的定义，ArrayList继承自AbstractList
// AbstractList中声明了List该有的一些方法，同时实现了迭代器
// ArrayList具有随机访问、克隆以及序列化的能力
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable,java.io.Serializable

ArrayList的一些静态变量

// ArrayList的默认的容量大小是10
private static final int DEFAULT_CAPACITY = 10;

// 空list
private static final Object[] EMPTY_ELEMENTDATA = {};

// 创建ArrayList实例时，如果未提供capacity，那ArrayList内部将会是这个数组，其capacity是0，然后在add第一个元素的时候进行扩容。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList内部实现

// ArrayList内部实现就是这个数组，其length就是ArrayList的capacity
// transient关键字意味着elementData将不会序列化，那么ArrayList又将如何序列化？
transient Object[] elementData;

数组是顺序表，这意味着ArrayList不适合在非尾部插入和删除

new ArrayList<>()方法

// 这里说明new ArrayList<>()时，ArrayList是空的，capacity为0
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

再来看add方法

// add首先会就行容量校验
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal方法

// 当elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，会将list的capacity设置为Math.max(DEFAULT_CAPACITY, minCapacity)，所以capacity至少会是10
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)
    }

    ensureExplicitCapacity(minCapacity);
}

ArrayList最大容量

// ArrayList的最大容量是Integer.MAX_VALUE - 8，减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扩容

// 至少会扩容 1/2 oldCapacity（向下取整）
// 如果newCapacity小于最少需要的容量minCapacity，那newCapacity=minCapacity
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);
}

// 取MAX_ARRAY_SIZE或者抛出OutOfMemoryError异常
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方法，即当前需要的容量要比当前ArrayList的capacity大时进行扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

ArrayList序列化

为什么ArrayList会采用这两个方法来完成序列化与反序列化，见Java集合序列化

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

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

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

总结

1、ArrayList内部如何实现？适合什么样的操作场景？
数组实现，适合随机存取、不适合非尾部的增删操作。

2、new ArrayList<>()方法调用后所提供的ArrayList容量是多大？
0

3、未提供容量值，但是调用add方法后ArrayList容量值是多大？
至少是10，或者实际需要值（大于10）

4、ArrayList什么时候扩容？如何扩容？扩多大？
当前需要的容量要比当前ArrayList的capacity大时进行扩容；扩容的操作是重新分配数组；至少会扩容 1/2 oldCapacity（向下取整），如果newCapacity小于最少需要的容量minCapacity，那将扩大至最少需要容量。

5、ArrayList是否线程安全？
不是，没有任何synchronized方法。

6、ArrayList如何序列化？
通过readObject和writeObject，详见集合序列化

7、ArrayList最大容量是多大？
Integer.MAX_VALUE - 8，部分虚拟机在数组中预留了8位存储头部信息。

码农公寓