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

Apabila tatasusunan hampir melimpah, tambahkan 1/2 daripada tatasusunan, dan kemudian bandingkan dengan pemalar terbesar tatasusunan Jika ia melebihi saiz maksimum tatasusunan, gunakan tatasusunan baharu Integer.MAX_VALUE , dan kemudian tambah yang lama Salin tatasusunan.
Perkara yang paling sukar untuk difahami ialah >>1, yang sebenarnya bersamaan dengan pembahagian dengan 2.

Answer 2

Tulis contoh mudah dan anda akan tahu selepas menyahpepijatnya

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;
}

Jika

int newCapacity = oldCapacity + (oldCapacity >> 1); melebihi nilai maksimum int selepas melaksanakan ayat ini, maka newCapacity akan menjadi nombor negatif Ini memerlukan pemahaman prinsip penambahan dan penolakan perduaan digital.

Empat ayat berikut adalah untuk pengendalian apabila newCapacitylimpahan menjadi nombor negatif

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

Answer 3

Saya rasa anda bercakap tentang mengendalikan senarai tatasusunan yang sama dalam berbilang utas Pada masa ini, masalah limpahan panjang berlaku. serentak. CopyOnWriteArrayList