ArrayList扩容机制

本文的出现是为了能够分享个人所学的相关知识，检验自身学习成果。内容会和其他技术存在部分关联，如有任何描述错误或者说明有误的地方，还望各位大佬指出。

1. 背景

面试的时候问到过ArrayList的扩容机制以及HashMap的扩容机制，今天来讲讲ArrayList的扩容机制。

2. 环境

JDK1.8

3.详解

3.1 默认容量

ArrayList若未指定长度默认空间长度为10，可见ArrayList中“DEFAULT_CAPACITY”属性，“size”属性为元素个数。最大长度为2^31-1-8，见ArrayList中“MAX_ARRAY_SIZE”属性。

3.2 扩容

触发扩容的对外方法都在ArrayList.add*()的几个方法中，发现长度大于空间长度时调用**”grow()”**,源码如下；

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

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

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

扩容主要操作是在代码就在grow()方法中，源码及解析如下：

private void grow(int minCapacity) {
   	// oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    // 将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    // 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 检查新计算出的容量数值和实际所需容量数值比较，若计算出的容量数值小于实际所需容量数值，则用实际容量的数值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 检查新计算出的容量数值是否超过ArrayList最大长度，如果minCapacity大于最大容量，新容量为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用copy方法
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

ArrayList扩容机制如下：

1.普遍情况下，新容量是旧容量1.5倍，同时校验新容量是否超过 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）。

2.当在扩容1.5倍后，校验新容量是否超过MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），若新容量（源码中newCapacity）大于最大容量 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）时,新容量为Integer.MAX_VALUE，否则为 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）;