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

Lorsque le tableau est sur le point de déborder, ajoutez la moitié du tableau, puis comparez-le avec la plus grande constante du tableau. Si elle dépasse la taille maximale du tableau, demandez un nouveau tableau de Integer.MAX_VALUE. , puis ajoutez l'ancienne copie du tableau.
La chose la plus difficile à comprendre est >>1, qui équivaut en fait à diviser par 2.

Answer 2

Écrivez un exemple simple et vous le saurez après l'avoir débogué

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

Si

int newCapacity = oldCapacity + (oldCapacity >> 1); dépasse la valeur maximale de int après l'exécution de cette phrase, alors newCapacity sera un nombre négatif. Cela nécessite de comprendre le principe d'addition et de soustraction du binaire numérique.

Les quatre phrases suivantes servent à gérer lorsque newCapacityle débordement devient un nombre négatif

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

Answer 3

Je pense que vous parlez d'utiliser la même liste de tableaux dans plusieurs threads. À ce moment-là, un problème de dépassement de longueur s'est produit. Le problème est que la liste de tableaux n'est pas thread-safe. simultané. CopyOnWriteArrayList