Java ArrayList

属性

/**
 * Default initial capacity.
 * 
 * 如初始化时不指定，则默认容量为 10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] 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 = {};

/**
 * 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
 * 以后 elementData 曾经有的元素的长度，新元素会放在 elementData[size] 下
 */
private int size;

结构器

默认结构器

/**
 * 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) {
        // 新建长度为 initialCapacity 的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {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) {elementData = c.toArray();
    // 如果传入的汇合长度不为 0，则把汇合中的元素 copy 到 elementData 中
    if ((size = elementData.length) != 0) {// defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

扩容

最大长度

依据正文能够看到，有些虚拟机须要在数组中保留额定信息（保留的额定信息）须要占用肯定的空间，所以 ArrayList 的最大长度为 2^32 - 8

/**
 * The maximum size of array to allocate (unless necessary).
 * 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;

每次扩容时候，newCapacity 为 oldCapacity + (oldCapacity >> 1)，相当于旧容量的 1.5 倍

/**
 * Returns a capacity at least as large as the given minimum capacity.
 * Returns the current capacity increased by 50% if that suffices.
 * Will not return a capacity greater than MAX_ARRAY_SIZE unless
 * the given minimum capacity is greater than MAX_ARRAY_SIZE.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 依照扩容规定计算的新容量小于预期容量
    if (newCapacity - minCapacity <= 0) {
        // 当应用默认结构器进行初始化时，在此处才进行底层数组的初始化
        // 新的底层数组长度为默认容量（10）和冀望容量之间最大的值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    // 依照扩容规定计算出的容量是否超过默认最大容量？// 不超过：则间接返回
    // 超过：依据 hugeCapacity() 计算出新的长度
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

当通过默认规定扩充为原来 1.5 后如果超过默认最大容量时，则通过比拟 预期容量 和默认最大容量 来判断最大容量；
当预期容量比默认的 MAX_ARRAY_SIZE 大时，则返回 Integer.MAX_VALUE
否则返回默认的 MAX_ARRAY_SIZE

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

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 * 
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {return grow(size + 1);
}

add()

add 办法一共有两个公开办法，一个是在尾部增加元素的 add(E e) 和在任意地位插入元素的 add(int index, E element)

尾部插入 add(E e)

该公开办法调用了 add(E e, Object[] elementData, int s)

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

如果以后容量已满则进行扩容，否则间接把元素放到 s (= size) 的地位，数组元素长度 size + 1

/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
private void add(E e, Object[] elementData, int s) {if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

任意地位插入 add(int index, E element)

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 查看要插入的地位是否越界
    // 查看的范畴为 [0, size]
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    // 数组曾经放满了，须要进行扩容
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    // 把原来元素拷贝一份到新数组
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}