ArrayList容量增长中Java 6和Java 7之间的差异

Question

我有一个问题,关于如何在Java中管理ArrayList的容量增长(不是大小,而是容量).当我们使用默认构造函数初始化ArrayList而不设置容量时,默认情况下容量设置为10.

此时,当我们向列表添加另一个元素时,Oracle文档说"当元素添加到ArrayList时,其容量会自动增长.除了添加元素具有常量这一事实之外,未指定增长策略的详细信息摊销时间成本."

如果我们看看Java内部,容量增长政策已经改变了它的功能.直到Java 6它是:

(1) int newCapacity = (oldCapacity * 3)/2 + 1;

从Java 7(和> 7)它是:

(2) int newCapacity = oldCapacity + (oldCapacity >> 1);

但这两个数学系列略有不同.从默认值(10)开始,我们有:

(1)10,16,25,38,58,88,133,200,301,452 ......

(2)10,15,22,33,49,73,109,163,244,366 ......

我认为这对ArrayList的使用没有任何影响,但为什么他们改变了这个功能呢？有任何表现原因吗？他们发现了旧的瑕疵还是虫子？

Answer 1

OpenJDK的的源代码控制历史表明它被改变了马丁·巴克霍尔兹从谷歌在变更2350修复的bug JDK-6933217:巨大的阵列,核心库处理不当.

新代码小心避免不必要的整数溢出.oldCapacity * 3即使oldCapacity * 3 / 2没有,也会溢出.新线oldCapacity + (oldCapacity >> 1)不会.如果它确实溢出并且变为负数,则需要额外的代码来将容量设置为Integer.MAX_VALUE(或接近它).

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
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;
}

错误报告的完整详细信息:

我注意到在虫子java.util.ArrayList,java.util.Hashtable而 java.io.ByteArrayOutputStream这出现在数据结构的能力达到一个特定的阈值.更多下面.

当的容量ArrayList达到(2/3)*Integer.MAX_VALUE它的大小达到其容量和附加或插入操作被调用时,容量增加仅由一个元件.请注意,在以下摘录中,ArrayList.ensureCapacity新容量设置为(3/2) * oldCapacity + 1除非此值不足以容纳所需容量,在这种情况下将其设置为所需容量.如果当前容量至少为 (2/3)*Integer.MAX_VALUE,则(oldCapacity * 3)/2 + 1溢出并解析为负数,从而将新容量设置为所需容量.这样做的主要结果是每个后续的添加/插入操作都会导致ArrayList导致性能的完全调整 大幅降低.

int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
    newCapacity = minCapacity;

...

值得注意的是,任何关于添加/插入操作的摊销时间复杂性的陈述(例如ArrayList javadoc中的一个)都会因与性能相关的错误而失效.上述情况的一种解决方案是将后备阵列的新容量设置为Integer.MAX_VALUE在调整大小期间初始大小计算结果为负数时.