java - 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

當數組要溢出的時候，就加上數組的1/2，然後和數組最大的常數進行比對，如果超出數組的最大size，就新申請一個Integer.MAX_VALUE的数组，然后把之前旧数组复制过来。
其中最难理解的是>>1,其實相當於除以2。

Answer 2

寫個簡單的例子，樓主調試一下就知道了

public static void main(String[] args) {
    int oldCapacity = Integer.MAX_VALUE - 16;
    System.out.println(oldCapacity);
    int minCapacity = Integer.MAX_VALUE - 15;
    int maxSize = Integer.MAX_VALUE - 8;
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - maxSize > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    System.out.println(newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > Integer.MAX_VALUE - 8) ?
            Integer.MAX_VALUE :
            Integer.MAX_VALUE - 8;
}

int newCapacity = oldCapacity + (oldCapacity >> 1);这句执行后如果超过int的最大值那么newCapacity會是一個負數，這個需要了解數字二進位的加減原理。

下面這四句就是針對newCapacity溢位變成負數的時候的處理

if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
if (newCapacity - maxSize > 0)
    newCapacity = hugeCapacity(minCapacity);

Answer 3

我想你是說在多線程操作同一個arraylist吧，這時候剛好湊巧出現了長度溢出問題，問題是arraylist本來就不是線程安全的，正確的做法是去用 java.util.concurrent 裡的 CopyOnWriteArrayList