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을 추가한 후 배열의 가장 큰 상수와 비교하여 배열의 최대 크기를 초과하는 경우 Integer.MAX_VALUE의 새로운 배열을 신청하세요. , 이전 배열을 추가합니다.
가장 이해하기 어려운 것은 >>1인데, 실제로는 2로 나누는 것과 같습니다.

Answer 2

간단한 예제를 작성하고 디버깅해 보면 알 수 있습니다

으아악 이 문장을 실행한 후

int newCapacity = oldCapacity + (oldCapacity >> 1);이 int의 최대값을 초과하면 newCapacity은 음수가 됩니다. 이를 위해서는 디지털 이진법의 덧셈과 뺄셈의 원리를 이해해야 합니다.

다음 네 문장은 newCapacityoverflow가 음수가 되는 경우

를 처리하기 위한 것입니다. 으아악

Answer 3

동일한 arraylist를 여러 스레드에서 운영한다고 말씀하시는 것 같은데, 이때 길이 오버플로 문제가 발생했습니다. 문제는 arraylist가 스레드로부터 안전하지 않다는 것입니다. java.util을 사용하는 것이 올바른 방법입니다. 동시.CopyOnWriteArrayList