MENU

Java集合类 - 扩容机制(一)ArrayList

June 15, 2018 • Code

前言:通过源码分析 ArrayList 的扩容机制。

ArrayList 扩容源码

  • Java 版本:1.8

调用过程图

方法源码

  • add 方法

调用 ensureCapacityInternal 方法确保数组容量足够完成这次增加操作。

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    // 确保当前数组容量足够,不足则进行扩容操作
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
  • ensureCapacityInternal 方法

该方法先调用 calculateCapacity 方法,主要判断此次添加是否为第一次添加,因 ArrayList 的内置数组是懒加载(即在第一次使用时初始化),所以如果是第一次加载,则将数组扩大为默认初始大小 10 而不是所需最小容量 1;如果不是,则直接返回 minCapacity。

接着调用 ensureExplicitCapacity 方法,判断是否需要扩容

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
  • calculateCapacity 方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
  • ensureExplicitCapacity 方法
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
  • grow 方法
/**
 * 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
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    
    // 扩大为原数组的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果是初次扩容分配数组,则直接以 minCapacity(默认是 10)为新数组大小
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
        
    // 如果计算的新数组容量超过规定的数组最大容量,则调用 hugeCapacity 方不进行调整。
    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);
}
  • hugeCapacity 方法
private static int hugeCapacity(int minCapacity) {

    // 如果数组所需最小容量小于 0,则代表溢出,报错
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果数组所需最小容量大于规定数组最大容量,则返回 int 最大值,返回最大容量
    // Integer.MAX_VALUE = 0x7fffffff = 2147483647
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2147483639
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

扩容 1.5 倍 只是扩大对象引用数组大小,并没有实际分配内存。举个栗子:对象数组 Object[] os = new Object[10] 只声明了 10 个对象引用,每个元素都为 null。

小结

通过源码了解 ArrayList 的扩容机制,同时理解扩容与实际分配内存之间的区别。

Last Modified: July 12, 2018
Archives QR Code
QR Code for this page
Tipping QR Code