在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数组对于小数组列表来说太大了,但是如果你想添加几千个元素,那么每50个元素调整大小会降低性能.这样容量会成倍增加(如果你已经添加了很多元素,你可能会增加更多元素,因此它们会增加容量)所以它不会过多地降低性能.

至于为什么他们选择了50%,也许他们觉得容量翻倍(或更多)可能是过度杀戮(会为非常大的ArrayLists消耗太多的额外内存),而且过低(比如10-25%)可能会降低性能太高(通过做太多的重新分配),所以可能+ 50%提供足够好的性能,而不需要额外的内存.我猜他们在决定价值之前做了一些性能测试.

Answer 2

每次调用时它都会使列表增加50%,以防止过早分配世界.这+ 1是为了捕获列表初始化的大小为1的情况:)