文章目录

今天,来分享下 ArrayList 动态扩容机制。

基于 JDK 7 进行源码分析。

ArrayList 底层采用 Object 类型的数组实现。

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

当使用无参构造方法时,ArrayList 底层会生成一个长度为 10 的 Object 类型数组。

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

当向 ArrayList 添加对象时,计数加 1,并计算容量是否适当。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

若原数组的容量不足,就需要把原数组拷贝到指定容量为长度的新数组。

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

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

其中,新容量扩大到原容量的 1.5 倍

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新容量 = 原容量 + 0.5 倍的容量
    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);
}

总结下,ArrayList 有一个初始的容量大小 10,当存储进里面的元素个数超过容量时,就需要增加 ArrayList 存储空间。每次要增加存储空间时,ArrayList 扩容到原来的 1.5 倍,并且进行复制操作,这个是非常伤性能的。如果 ArrayList 很大,执行数百次扩容,那么就会进行更多次数的新数组分配操作,以及更多次数的旧数组回收操作。

// 糟糕
List list = new ArrayList();
// 建议
List list = new ArrayList(50000);
(完)

微信公众号

文章目录