ArrayList的数组扩容是如何考虑溢出的?

Question

这段代码是java1.8种util.ArrayList中关于数组扩容的一段代码, 上面有一行//overflow-conscious code. 说明下面的代码是对溢出进行考虑的代码 ,但是我花了好多时间在上面仍没有想清楚他是如何避免溢出的, 以及如何在newCapacity溢出的情况下工作的, 望指点迷津

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;

}

Answer 1

写个简单的例子，楼主调试一下就知道了public static void main(String[] args) {&nbsp; &nbsp; int oldCapacity = Integer.MAX_VALUE - 16;&nbsp; &nbsp; System.out.println(oldCapacity);&nbsp; &nbsp; int minCapacity = Integer.MAX_VALUE - 15;&nbsp; &nbsp; int maxSize = Integer.MAX_VALUE - 8;&nbsp; &nbsp; int newCapacity = oldCapacity + (oldCapacity >> 1);&nbsp; &nbsp; if (newCapacity - minCapacity < 0)&nbsp; &nbsp; &nbsp; &nbsp; newCapacity = minCapacity;&nbsp; &nbsp; if (newCapacity - maxSize > 0)&nbsp; &nbsp; &nbsp; &nbsp; newCapacity = hugeCapacity(minCapacity);&nbsp; &nbsp; // minCapacity is usually close to size, so this is a win:&nbsp; &nbsp; System.out.println(newCapacity);}private static int hugeCapacity(int minCapacity) {&nbsp; &nbsp; if (minCapacity < 0) // overflow&nbsp; &nbsp; &nbsp; &nbsp; throw new OutOfMemoryError();&nbsp; &nbsp; return (minCapacity > Integer.MAX_VALUE - 8) ?&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer.MAX_VALUE :&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer.MAX_VALUE - 8;}int newCapacity = oldCapacity + (oldCapacity >> 1);这句执行后如果超过int的最大值那么newCapacity会是一个负数，这个需要了解一下数字二进制的加减原理。下面这四句就是针对newCapacity溢出变成负数的时候的处理if (newCapacity - minCapacity < 0)&nbsp; &nbsp; newCapacity = minCapacity;if (newCapacity - maxSize > 0)&nbsp; &nbsp; newCapacity = hugeCapacity(minCapacity);

Answer 2

oldCapacity等于(Integer.MAX_VALUE-7)/1.5的时候，也就是newCapacity等于Integer.MAX_VALUE-7,执行hugeCapacity最后得到的newCapacity是Integer.MAX_VALUE,已经是数组支持的上限了，下次扩容就会抛OutOfMemoryError&nbsp;了，楼上你的newCapacity=minCapacity是怎么得出来的

Answer 3

当数组要溢出的时候，就加上数组的1/2，然后和数组最大的常量进行比对，如果超出数组的最大size，就新申请一个Integer.MAX_VALUE的数组，然后把之前旧数组复制过来。其中最难理解的是>>1,其实相当于除以2。

Answer 4

我想你是说在多线程操作同一个arraylist吧，这时候刚好凑巧出现了长度溢出问题，问题是arraylist本来就不是线程安全的，正确的做法是去用 java.util.concurrent 里的 CopyOnWriteArrayList

Answer 5

检测是否需要扩容的函数是 ensureCapacityInternal() ensureExplicitCapacity()，grow()是最后执行的，你在打开元那么看看add()之前是不是每一次都调用检测一遍。

Answer 6

我陷入的问题有点钻牛角尖了，或者是理解能力不够。总结：数组size值发生溢出，发生在第二个判断 if (newCapacity - maxArraySize > 0) = true时，即size要足够大，我才考虑数组会溢出的问题。正常情况下，每次size扩容1.5倍。当size扩大1.5倍发生int的溢出时，就每次进行最小扩容(+1)就可以了。第一个判断 if (newCapacity - minCapacity < 0) 这个就是为这个溢出准备的。还有一个问题：为什么扩容的倍数为1.5 而不选择其他倍数？//抛异常的情况：&nbsp;//数组原大小oldCapacity 已经为int的最大值，此时再次调用grow()扩容minCapacity发生溢出，进入hugeCapacity() 抛出异常。&nbsp; &nbsp;这是size会溢出的情况，只有size大于nteger.MAX_VALUE - 8 时，才开始考虑是不是抛出溢出异常public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; int maxArraySize = Integer.MAX_VALUE - 8;&nbsp; &nbsp; &nbsp; &nbsp; int oldCapacity = Integer.MAX_VALUE;&nbsp; &nbsp; &nbsp; &nbsp; int minCapacity = oldCapacity + 1;&nbsp; &nbsp; &nbsp; &nbsp; // overflow-conscious code&nbsp; &nbsp; &nbsp; &nbsp; int newCapacity = oldCapacity + (oldCapacity >> 1);&nbsp; &nbsp; &nbsp; &nbsp; // 1.5倍扩容大小&nbsp; -&nbsp; &nbsp;元素个数&nbsp; &nbsp; &nbsp; &nbsp; // 正常情况下，1.5倍的扩容 肯定大于 元素个数，肯定不需要频繁的扩容，所以一次来大一点，至于为什么是1.5倍，这个就不知道了。&nbsp; &nbsp; &nbsp; &nbsp; // 当 1.5倍扩容发生int的溢出时，就每次进行最小扩容(+1)就可以了。&nbsp; &nbsp; &nbsp; &nbsp; if (newCapacity - minCapacity < 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newCapacity = minCapacity;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; //newCapacity大于maxArraySize 才考虑进入这个方法&nbsp; &nbsp; &nbsp; &nbsp; if (newCapacity - maxArraySize > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newCapacity = hugeCapacity(minCapacity);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(newCapacity);&nbsp; &nbsp; }&nbsp; &nbsp; private static int hugeCapacity(int minCapacity) {&nbsp; &nbsp; &nbsp; &nbsp; if (minCapacity < 0) // overflow&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; throw new OutOfMemoryError();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return (minCapacity > Integer.MAX_VALUE - 8) ?&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer.MAX_VALUE :&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer.MAX_VALUE - 8;&nbsp; &nbsp; }}