Java中的ArrayList容量及扩容方式

   
    private static final int DEFAULT_CAPACITY = 10;

    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

// ArrayList 默认容量大小
private static final int DEFAULT_CAPACITY = 10;
// 一个共享的空数组, 在空实例时使用
private static final Object[] EMPTY_ELEMENTDATA = {};
// 一个共享的空数组, 在使用默认 size 的空实例时使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;
// ArrayList 的大小, 我们平常使用的 list.size() 底层就是记录的这个 size
private int size;
// ArrayList 最大
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

public ArrayList(Collection<? extends E> c) {
    // Collection 转换为数组 Object[] 类型 
    elementData = c.toArray();
    // 判断当前对象大小是否和 Collection 长度相等并且不等于 0, false 的话 elementData 等于空数组了
    if ((size = elementData.length) != 0) {
     // c.toArray() 可能不会正确地返回一个 Object[] 数组，所以使用 Arrays.copyOf()
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public boolean add(E e) {
 // 这一行是关键, 看下面
    ensureCapacityInternal(size + 1);
    // 将元素追加到集合的末尾 假如当前 size = 10 size++ 追加到第 11 位
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
 
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 不相等的话只有返回当前的 size + 1
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 增量, 记录修改/更新次数
    modCount++;  
    
     // 初始化: 10 - 0 > 0
     // 其他: size + 1 > 0
    if (minCapacity - elementData.length > 0)
     // 扩容操作
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 老的长度, 初始化时为 0, 
    int oldCapacity = elementData.length;
    // 新的长度此时 0 + (0 >> 1), newCapacity = 0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 初始化场景: 0 - 10 < 0 ? true newCapacity = 10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 初始化场景: 10 - 2147483639 > 0 返回 false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     // 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组中的元素, 并扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private void ensureCapacityInternal(int minCapacity) {
 
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 增量, 记录修改/更新次数
    modCount++;  
    
    // 其他: 11 - 10 > 0 true, 触发扩容, 如果当前下表是 5 的话 5 + 1 =6, 6 < 10 是, 此时不会出发扩容
    if (minCapacity - elementData.length > 0)
     // 扩容操作
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 老的长度 10
    int oldCapacity = elementData.length;
    // 新的长度此时 10 + (10 >> 1), newCapacity = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 15 - 11 < 0 ? false
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 15 - 2147483639 > 0 返回 false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     // 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组中的元素, 并扩容 newCapacity = 15
    elementData = Arrays.copyOf(elementData, newCapacity);
}

oldCapacity + (oldCapacity >> 1) 即: 10 + (10 >> 1)