Detaillierte Analyse des ArrayList-Quellcodes des Java-Sammlungsframeworks (Bild)

Allgemeine Einführung

ArrayList implementiert die List-Schnittstelle, bei der es sich um einen sequentiellen Container handelt, in dem sich Elemente befinden gespeichert Die Daten befinden sich in der gleichen Reihenfolge, in der sie eingegeben werden, sodass null-Elemente eingefügt werden können. Die darunter liegende Ebene implementiert über das -Array. Abgesehen davon, dass diese Klasse keine Synchronisierung implementiert, ist der Rest ungefähr derselbe wie Vector. Jede ArrayList hat eine Kapazität, die die tatsächliche Größe des zugrunde liegenden Arrays darstellt. Die Anzahl der im Container gespeicherten Elemente darf die aktuelle Kapazität nicht überschreiten. Wenn dem Container Elemente hinzugefügt werden, vergrößert der Container automatisch die Größe des zugrunde liegenden Arrays, wenn nicht genügend Kapazität vorhanden ist. Wie bereits erwähnt, handelt es sich bei Java-Generika nur um syntaktischen Zucker, der vom Compiler bereitgestellt wird. Daher ist das Array hier ein Objekt-Array, um jede Art von Objekt aufnehmen zu können.

Die Methoden size(), isEmpty(), get() und set() können alle in konstanter Zeit ausgeführt werden. Der Zeitaufwand der Methode add() beträgt Bezogen auf die Einfügeposition ist der Zeitaufwand der addAll()-Methode proportional zur Anzahl der hinzugefügten Elemente. Die meisten anderen Methoden sind lineare Zeitmethoden.

Aus Effizienzgründen wird ArrayList nicht synchronisiert. Wenn ein gleichzeitiger Zugriff durch mehrere Threads erforderlich ist, können Benutzer manuell synchronisieren oder stattdessen Vector verwenden.

Methodenanalyse

set()

Da die unterste Ebene ein Array ist, wird die -Methode von ArrayListset() sehr einfach. Verwenden Sie einfach die Array direkt Weisen Sie einfach der angegebenen Position einen Wert zu. Die Methode

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
    return oldValue;
}

get()

get() ist ebenfalls sehr einfach. Das einzige, was zu beachten ist, ist, dass Sie <🎜 ausführen müssen, da das zugrunde liegende Array Object[] ist >Typkonvertierung< nach Erhalt der Elemente 🎜>.

add()

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

unterscheidet sich vom

vector

von C++ und verfügt nicht über eine -Methode und die entsprechende Methode ist , ArrayList hat auch keine bush_back()-Methode, die entsprechende Methode ist add(E e). Bei beiden Methoden werden dem Container neue Elemente hinzugefügt, was zu einer unzureichenden Kapazität führen kann. Daher muss vor dem Hinzufügen von Elementen der verbleibende Platz überprüft und bei Bedarf automatisch erweitert werden. Der Erweiterungsvorgang wird schließlich über die Methode insert() abgeschlossen. add(int index, E e)Da Java GC den Speicher automatisch verwaltet, besteht hier keine Notwendigkeit, das Problem der Quellarray-Freigabe zu berücksichtigen. grow()

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

Nachdem das Platzproblem gelöst ist, wird der Einfügevorgang sehr einfach.

Sie müssen zuerst das Element verschieben und dann den Einfügevorgang abschließen, was bedeutet, dass diese Methode eine lineare Zeitkomplexität aufweist. Die Methode

addAll()

add(int index, E e)

kann mehrere Elemente gleichzeitig hinzufügen. Es gibt zwei Handles, abhängig von der Position. Eines davon ist die addAll(Collection extends<h3> E> c)</h3> Methode, eine wird ab der angegebenen Position eingefügtMethode . Ähnlich wie bei der

-Methode ist vor dem Einfügen auch eine Platzprüfung erforderlich, und die Kapazität wird bei Bedarf automatisch erweitert, wenn Elemente von einer bestimmten Position eingefügt werden. Die zeitliche Komplexität von addAll()addAll(Collection <a href="http://www.php.cn/wiki/166.html" target="_blank">extends</a> E> c) hängt nicht nur von der Anzahl der eingefügten Elemente ab, sondern auch von der Einfügeposition. Die Methode addAll(int index, Collection extends E> c)add()remove()
addAll()

hat auch zwei Versionen: Eine besteht darin, das Element an der angegebenen Position zu

zu löschen, die andere darin, das erste Element zu

zu löschen das erfüllt das

-Element. Der Löschvorgang ist der umgekehrte Vorgang des remove()-Vorgangs, bei dem das Element nach dem Löschpunkt um eine Position nach vorne verschoben werden muss. Es ist zu beachten, dass der letzten Position explizit ein remove(int index)-Wert zugewiesen werden muss, damit GC funktioniert. remove(Object o)o.equals(elementData[index])

Das obige ist der detaillierte Inhalt vonDetaillierte Analyse des ArrayList-Quellcodes des Java-Sammlungsframeworks (Bild). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!