java - ArrayList 中 ensureCapacity 方法中使用的逻辑

Question

我正在浏览 ArrayList 的源代码。我遇到了 ensureCapacity() 方法，它增加了内部使用的数据数组的容量。其中，数据数组的新容量根据逻辑 int newCapacity = (oldCapacity * 3)/2 + 1; 增加，其中旧容量是当前数据数组的大小。选择 (oldCapacity * 3)/2 + 1 作为新的数组大小有什么特别的原因吗？如果是的话是什么？

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

提前致谢...

Answer 1

JavaDoc 中唯一的保证是添加新元素具有恒定的摊销时间。这意味着向数组添加新元素的平均时间是恒定的。有时可能需要更长的时间(例如尝试调整数组大小时)，但总的来说，这些情况很少见，不会对平均值产生太大影响。

因此，为了让他们能够尊重这一保证，他们需要确保调整大小发生的频率足够低，以免影响平均添加时间。出于这个原因，他们将当前容量的百分比用于新容量。如果调整大小类似于 oldCapacity + 50，则数组对于小型 arrayLists 来说太大了，但是如果您想添加几千个元素，则每 50 个元素调整一次大小会降低性能。通过这种方式，容量呈指数级增长(如果您已经添加了很多元素，您很可能会添加更多元素，因此它们会增加更多容量)，因此不会过多地降低性能。

至于他们为什么选择 50%，也许他们觉得将容量加倍(或更多)可能有点矫枉过正(对于非常大的 ArrayLists 会消耗太多额外的内存)，而且容量太低(比如 10-25%)会大大降低性能(通过进行过多的重新分配)，因此可能 +50% 提供了足够好的性能，而不会占用太多额外内存。我猜他们在决定值(value)之前做了一些性能测试。