ArrayList: Wie vergrößert sich die Größe?

Ich habe eine grundlegende Frage zu Java ArrayList.

Wenn ArrayListmit dem Standardkonstruktor deklariert und initialisiert wird, wird Speicherplatz für 10 Elemente erstellt. Was passiert nun, wenn ich ein elftes Element hinzufüge? Wird neuer Speicherplatz mit einer Kapazität von 20 (oder mehr) Elementen erstellt (dies erfordert das Kopieren von Elementen vom ersten Speicherort an einen neuen Speicherort) ODER etwas anderes?

Ich habe hier nachgesehen . Aber ich habe keine Antwort gefunden.

Bitte teilen Sie das Wissen. Vielen Dank.

Ein neues Array wird erstellt und der Inhalt des alten wird kopiert. Das ist alles, was Sie auf API-Ebene wissen. Zitat aus den Dokumenten (mein Schwerpunkt):

Jede ArrayListInstanz hat eine Kapazität. Die Kapazität ist die Größe des Arrays, in dem die Elemente in der Liste gespeichert werden. Es ist immer mindestens so groß wie die Listengröße. Wenn Elemente zu einer ArrayList hinzugefügt werden, wächst ihre Kapazität automatisch. Die Details der Wachstumspolitik werden nicht über die Tatsache hinaus spezifiziert, dass das Hinzufügen eines Elements konstante amortisierte Zeitkosten verursacht.

In Bezug darauf, wie es tatsächlich mit einer bestimmten Implementierung von ArrayList(wie z. B. Suns) passiert , können Sie in diesem Fall die blutigen Details in der Quelle sehen. Aber natürlich ist es normalerweise keine gute Idee, sich auf die Details einer bestimmten Implementierung zu verlassen ...

Suns JDK6:

Ich glaube, dass es auf 15 Elemente wächst. Nicht codieren, sondern den Grow () - Code im JDK betrachten.

int newCapacity dann = 10 + (10 >> 1) = 15.

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

Aus dem Javadoc geht hervor, dass dies aus Java 2 und höher stammt, daher ist es eine sichere Sache im Sun JDK.

EDIT : für diejenigen, die nicht verstanden haben, was der Zusammenhang zwischen Multiplikationsfaktor 1.5undint newCapacity = oldCapacity + (oldCapacity >> 1);

>>ist ein Rechtsschaltoperator, der eine Zahl auf die Hälfte reduziert. Also
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=>int newCapacity = 1.5*oldCapacity ;

Dies hängt von der Implementierung ab, jedoch vom Sun Java 6-Quellcode:

int newCapacity = (oldCapacity * 3)/2 + 1;

Das liegt in der ensureCapacityMethode. Andere JDK-Implementierungen können variieren.

Wenn wir versuchen, der Arrayliste ein Objekt hinzuzufügen,

Java überprüft , ob im vorhandenen Array genügend Kapazität vorhanden ist, um das neue Objekt aufzunehmen. Wenn nicht, wird ein neues Array mit einer größeren Größe erstellt , das alte Array wird mit Arrays.copyOf in ein neues Array kopiert und das neue Array wird dem vorhandenen Array zugewiesen.

Schauen Sie sich den folgenden Code an (entnommen aus Java ArrayList Code bei GrepCode.com).

Bearbeiten:

public ArrayList () Erstellt eine leere Liste mit einer Anfangskapazität von zehn.

public ArrayList (int initialCapacity) können wir die Anfangskapazität angeben.

public ArrayList (Collection c) Erstellt eine Liste mit den Elementen der angegebenen Collection in der Reihenfolge, in der sie vom Iterator der Collection zurückgegeben werden.

Wenn wir jetzt den Konstruktor ArrayList () verwenden, erhalten wir eine ArrayList mit Größe = 10. Beim Hinzufügen des 11. Elements zur Liste wird eine neue Arraylist in der Methode verifyCapacity () erstellt.

Mit folgender Formel:

  int newCapacity= (oldCapacity * 3)/2 +1;

Bis zu JDK 6 wächst die Kapazität mit der Formel newCapacity = (oldCapacity * 3/2) + 1.

In JDK 7 und höher ändert sich die Formel in newCapacity = oldCapacity + (oldCapacity >> 1).

Also , wenn anfängliche Kapazität ist 10dann neue Kapazität ist 16 in JDK6und15 in above JDK7

Wenn eine ArrayList mit dem Standardkonstruktor deklariert und initialisiert wird, wird Speicherplatz für 10 Elemente erstellt. Wenn ich nun das 11. Element hinzufüge, passiert Folgendes

ArrayList erstellt ein neues Objekt mit der folgenden Größe

dh OldCapacity * 3/2 + 1 = 10 * 3/2 + 1 = 16

In der Regel wird der Speicher für Container vom Typ ArrayList durch Verdoppeln vergrößert. Wenn Sie also anfangs Platz für 10 Elemente hatten und 10 hinzugefügt haben, wird das elfte Element einem neuen (internen) Array von 20 Elementen hinzugefügt. Der Grund dafür ist, dass die zusätzlichen Kosten für das Hinzufügen von Elementen von O (n ^ 2) reduziert werden, wenn das Array in Schritten mit fester Größe auf ein schönes O (n) erhöht wurde, wenn die Größe jedes Mal verdoppelt wird, wenn das interne Array voll ist.

Schauen wir uns diesen Code an (jdk1.8)

@Test
    public void testArraySize() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("last");
    }

1) Setzen Sie einen Haltepunkt auf die Linie, wenn "last" eingefügt wird

2) Gehen Sie zur Add-Methode von ArrayList Sie werden sehen

ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;

3) Gehen Sie zur Methode sureCapacityInternal, die diese Methode aufruft ensureExplicitCapacity

4)

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
            return true;

In unserem Beispiel ist minCapacity gleich 11, 11-10 > 0daher benötigen Sie eine growMethode

5)

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

Beschreiben wir jeden Schritt:

1) oldCapacity= 10, da wir diesen Parameter nicht gesetzt haben, als ArrayListinit war, wird daher die Standardkapazität verwendet (10)

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Hier ist newCapacity gleich oldCapacity plus oldCapacity mit einer Verschiebung nach rechts um eins ( oldCapacity is 10dies ist die binäre Darstellung, die 00001010sich um ein Bit nach rechts bewegt, 00000101was 5 in Dezimalzahl newCapacityist 10 + 5 = 15).

3)

if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;

Zum Beispiel ist Ihre Init-Kapazität 1, wenn Sie das zweite Element zu arrayList hinzufügen newCapacity, ist gleich. 1(oldCapacity) + 0 (moved to right by one bit) = 1 In diesem Fall ist newCapacity kleiner als minCapacity und elementData(Array-Objekt in arrayList) kann kein neues Element enthalten, daher ist newCapacity gleich minCapacity

4)

if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

Überprüfen Sie, ob die Arraygröße MAX_ARRAY_SIZE (Integer.MAX - 8) erreicht. Warum ist die maximale Arraygröße von ArrayList Integer.MAX_VALUE - 8?

5) Schließlich werden alte Werte mit der Länge 15 in das newArray kopiert

Kontext Java 8

Ich gebe meine Antwort hier im Kontext der Implementierung von Oracle Java 8, da ich nach dem Lesen aller Antworten festgestellt habe, dass gmgmiller eine Antwort im Kontext von Java 6 gegeben hat und eine andere Antwort im Kontext von Java 7. Es wurde jedoch nicht angegeben, wie Java 8 die Vergrößerung implementiert.

In Java 8 ist das Verhalten zur Vergrößerung der Größe dasselbe wie in Java 6, siehe die growMethode von ArrayList:

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

Der Schlüsselcode ist diese Zeile:

int newCapacity = oldCapacity + (oldCapacity >> 1);

Der Wachstumsfaktor beträgt also eindeutig 1,5, genau wie bei Java 6.

Wenn ArrayList mit dem Standardkonstruktor deklariert und initialisiert wird, wird Speicherplatz für 10 Elemente erstellt.

NEIN. Wenn ArrayList initialisiert wird, wird die Speicherzuordnung für ein leeres Array vorgenommen. Die Speicherzuweisung für die Standardkapazität (10) erfolgt nur nach Hinzufügen des ersten Elements zu ArrayList.

 /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
private transient Object[] elementData;

PS: Ich habe nicht genug Ruf, um eine Frage zu kommentieren, deshalb setze ich dies als Antwort, da niemand zuvor auf diese falsche Annahme hingewiesen hat.

ArrayList erhöht den Lastfaktor in folgenden Fällen:

• Anfangskapazität: 10
• Lastfaktor: 1 (dh wenn die Liste voll ist)
• Wachstumsrate: current_size + current_size / 2

Kontext: JDK 7

Beim Hinzufügen eines Elements zum ArrayListwerden die folgenden public ensureCapacityInternalAufrufe und die anderen privaten Methodenaufrufe intern ausgeführt, um die Größe zu erhöhen. Dies ist es, was die Größe von dynamisch erhöht ArrayList. Während Sie den Code anzeigen, können Sie die Logik verstehen, indem Sie Konventionen benennen. Aus diesem Grund füge ich keine explizite Beschreibung hinzu

public boolean add(E paramE) {
        ensureCapacityInternal(this.size + 1);
        this.elementData[(this.size++)] = paramE;
        return true;
    }

private void ensureCapacityInternal(int paramInt) {
        if (this.elementData == EMPTY_ELEMENTDATA)
            paramInt = Math.max(10, paramInt);
        ensureExplicitCapacity(paramInt);
    }
private void ensureExplicitCapacity(int paramInt) {
        this.modCount += 1;
        if (paramInt - this.elementData.length <= 0)
            return;
        grow(paramInt);
    }

private void grow(int paramInt) {
    int i = this.elementData.length;
    int j = i + (i >> 1);
    if (j - paramInt < 0)
        j = paramInt;
    if (j - 2147483639 > 0)
        j = hugeCapacity(paramInt);
    this.elementData = Arrays.copyOf(this.elementData, j);
}

Aus dem JDK-Quellcode habe ich den folgenden Code gefunden

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

Was passiert ist, dass ein neues Array mit n * 2 Leerzeichen erstellt wird, dann werden alle Elemente im alten Array kopiert und das neue Element in das erste freie Leerzeichen eingefügt. Alles in allem führt dies dazu, dass O (N) Zeit für die ArrayList hinzufügt.

Wenn Sie Eclipse verwenden, installieren Sie Jad und Jadclipse , um die in der Bibliothek enthaltenen JARs zu dekompilieren. Ich habe dies getan, um den ursprünglichen Quellcode zu lesen.

Größe ArrayListnimmt mit n+n/2+1immer zu.

Die Standardkapazität von ArrayList ist 10. Sobald die Kapazität ihre maximale Kapazität erreicht hat, beträgt die Größe der ArrayList 16, sobald die Kapazität ihre maximale Kapazität von 16 erreicht hat, beträgt die Größe der ArrayList 25 und nimmt basierend auf der Datengröße weiter zu. ...

Wie? Hier ist die Antwort und Formel

New capacity = (Current Capacity * 3/2) + 1

Wenn also die Standardkapazität 10 ist, dann

Current Capacity = 10
New capacity = (10 * 3/2) + 1
Output is 16

static int getCapacity(ArrayList<?> list) throws Exception {
            Field dataField = ArrayList.class.getDeclaredField("elementData");
            dataField.setAccessible(true);
            return ((Object[]) dataField.get(list)).length;
    }

Verwenden Sie die oben beschriebene Methode, um die Größe zu überprüfen, wenn die Arrayliste geändert wird.

In Jdk 1.6: Neue Kapazität = (aktuelle Kapazität * 3/2) + 1;

In Jdk 1.7:

int j = i + (i >> 1); Dies ist dasselbe wie Neue Kapazität = (Aktuelle Kapazität * 1/2) + Aktuelle Kapazität;

Beispiel: Die Größe nimmt zu wie: 10 -> 15 -> 22 -> 33

(oldSize * 3) / 2 + 1

Wenn Sie den Standardkonstruktor verwenden, ist die Anfangsgröße von ArrayList, 10andernfalls können Sie die Anfangsgröße des Arrays beim Erstellen des Objekts von übergeben ArrayList.

Beispiel: Falls Standardkonstruktor

List<String> list = new ArrayList<>();
list.size()

Beispiel: Bei parametrisiertem Konstruktor

List<String> list = new ArrayList<>(5);
list.size()

Die Standardgröße der Arrayliste ist 10. Wenn wir die 11. hinzufügen ... Arrayliste erhöht die Größe (n * 2). Die in der alten Arrayliste gespeicherten Werte werden in die neue Arrayliste mit einer Größe von 20 kopiert.