1. ArrayList Quellcodeanalyse (JDK7)
ArrayList führt intern ein dynamisches Objektarray bei. Die dynamische Addition und Löschung von ArrayList ist die dynamische Addition und Löschung dieses Gruppenpaars.
1. Konstruktion und Initialisierung ArrayList
ArrayList -Instanzvariable // ArrayList Standard -Kapazität privates statisches endgültiges int default_capacity = 10; // Standard leeres Objekt -Array, verwendet, um leeres ArrayListPrivate statisches endgültiges Objekt zu definieren.
ArrayList Constructor:
Kein Parameterkonstruktor: Konstruieren Sie ein leeres Objekt []
public arrayList () {super (); this.elementData = leer_elementData;} Geben Sie das Kapazitätsgrößenkonstrukt an:
public arrayList (int initialCapacity) {super (); if (initialCapacity <0) neue IllegalArgumentException ("illegale Kapazität:"+ initialCapacity); this.elementData = neues Objekt [initialCapacity];} Geben Sie eine Sammlungsstruktur an, die die Sammelschnittstelle implementiert:
öffentliche ArrayList (Sammlung <? Erweitert E> c) {elementData = c.toarray (); size = elementData.length; // c.toarray könnte (falsch) nicht das Objekt [] zurückgeben [] (siehe 6260652) if (elementData.getClass ()! = Object []. Klasse) elementData = arrays.copyof (elementData, Größe, Objekt []. Klasse);}Dies erklärt auch die Rolle der Sammlung und den Grund, warum Java-Sammel-Framwork die Sammelschnittstelle entwirft, anstatt direkt List, Set und andere Schnittstellen zu verwenden.
2. Mechanismus der Kapazitätszuweisung von ArrayList
Kapazitätsgrenze für ArrayList: ArrayList -Kapazität ist die obere Grenze, und Theorien ermöglichen die Zuteilung von Integer.max_Value - 8 Größenkapazität. Wie viel zugewiesen werden kann, hängt jedoch von den Stapeleinstellungen ab, und VM -Parameter müssen festgelegt werden
private statische endgültige int max_array_size = integer.max_value - 8;
Erweitern Sie das Volumen beim Aufrufen der Methode hinzufügen
public boolean add (e e) {sealEcapacityInternal (Größe + 1); // Inkrementiert modcount !! ElementData [Größe ++] = e; zurückkehren; }Die sarocapacityInternale (int) -Methode bestimmt tatsächlich eine minimale Expansionsgröße.
private void sealecapacityInternal (int mincapacity) {if (elementData == leer_elementData) {mincapacity = math.max (default_capacity, mincapacity); } sorgenexplicitCapacity (mincapacity); } private void sorgenexplicitCapacity (int mincapacity) {modcount ++; // überlaufbewusster Code if (mincapacity - elementData.length> 0) wachsen (minkapazität); } Über ModCount: ModCount ist in der abstrakten AbstractList der abstrakten Klasse definiert. Die Kommentare von Quellcode erläutern im Grunde genommen die Verwendung: Wenn Sie Iterator zum Überqueren verwenden, wird dies verwendet, um zu überprüfen, ob die Elemente in der Liste strukturelle Änderungen haben (eine Anzahl der Anzahl der Listenelemente hat sich geändert). Es wird hauptsächlich in einer Umgebung mit mehreren Threads verwendet, um zu verhindern, dass ein Thread iteriert, und ein anderer Thread, der die Struktur dieser Liste modifiziert.
Die Wachstumsmethode ist eine echte Expansionsmethode
private void wachsen (int mincapacity) {// überlaufbewusster Code int OldCapacity = elementData.length; int newCapacity = OldCapacity + (OldCapacity >> 1); if (newcapacity - mincapacity <0) newCapacity = mincapacity; if (newcapacity - max_array_size> 0) newCapacity = Hugcapacity (mincapacity); // Hackigkeit liegt normalerweise nahe an der Größe, daher ist dies ein Gewinn: elementData = arrays.copyof (elementData, Newcapacity); }Es gibt auch eine Hugenkapazitätsmethode, wie viel Kapazität erweitert wird
private statische int Hugenkapazität (int mincapacity) {if (mincapacity <0) // Überlauf neue outofMemoryError (); return (mincapacity> max_array_size)? Integer.max_value: max_array_size; } Zusammenfassen:
Jede Erweiterung wird von einer Kopie des Arrays begleitet. Daher verbessert die richtige Kapazität die Leistung ein wenig.
Die folgende Abbildung ist der gesamte Expansionsprozess, den ich zusammenfasste:
3.ArrayList Iterator
Es gibt zwei wichtigste Iteratoren von ArrayList und Listitr, aber auch ein ArrayListsPliterator wird in JDK1.8 hinzugefügt. Lassen Sie uns die Quellcodeanalyse von ITR bzw. Listitr lernen.
(1) ITR: Kann nur rückwärts gehen
Private Klasse ITR implementiert Iterator <E> {int Cursor; // Index des nächsten Elements zur Rückgabe von int lastret = -1; // Index des letzten Elements zurückgegeben; -1 Wenn kein solcher // erweitertmodcount eine Kopie von ModCount Int erweitertModcount = modcount ist; public boolean hasNext () {return cursor! = size; } @SuppressWarnings ("deaktiviert") public e next () {checkforComodification (); // Die aktuelle Position int i = cursor aufzeichnen; if (i> = size) werfen neue noSuchelementException (); Object [] elementData = arrayList.this.ElementData; if (i> = elementData.length) werfen neue ConcurrentModificationException (); // die Position des nächsten Elements Cursor = i + 1; return (e) elementData [lastret = i]; } // Verwenden Sie die Iterator -Methode entfernen public void remove () {if (lastret <0). checkforComodification (); Versuchen Sie {// Beachten Sie, wie die innere Klasse die äußere Klasse ArrayList nennt. This.remove (Lastret); // Nach dem Entfernen müssen Sie die Position jedes Zeiger-Cursors = Lastret neu einstellen. Lastret = -1; erweitertModcount = modcount; } catch (indexoutOfboundSexception ex) {neue ConcurrentModificationException (); }} endgültig void checkforComodification () {if (modcount! = erwartungsModcount) werfen neue ConcurrentModificationException (); }} Aus dem Quellcode ist ersichtlich, dass der ITR -Iterator ein Vorwärts -Iterator ist, der eine nächste Methode bietet, um Elemente in der ArrayList zu erhalten.
CheckForComodification ist ein fehlgeschlagener Fehlererkennungsmechanismus bei Java-Sammel-Framwork. Der Betrieb auf demselben Set in einer Umgebung mit mehreren Threads kann den fehlgeschlagenen Mechanismus auslösen und eine Ausnahme von ConcurrentModificationException ausführen.
Der ITR -Iterator definiert eine Kopie des MODCOUNT ADGETMODCOUNT -Datensatz. Wenn ArrayList Operationen ausführt, um die Struktur zu ändern, z. B. Methoden hinzufügen, entfernen und klären, ändert sich der Wert von ModCount.
Über den ITR-Quellcode ist zu erkennen, dass das Aufrufen des nächsten und Entfernens von Methoden die fehlgefälige Überprüfung auslöst. Zu diesem Zeitpunkt, wenn eine Ausnahme auftritt, wenn andere Threads Vorgänge ausführen, die die festgelegte Struktur ändern, während Sie den Satz durchqueren.
(2) Listitr: Unterstützt Vorwärts- und Rückwärtstraversal. Schauen wir uns den Quellcode von Listitr an:
private class listitr erweitert ITR implementiert ListIterator <E> {listitr (int index) {super (); Cursor = index; } public boolean hasprevious () {return cursor! = 0; } public int nextIndex () {return cursor; } public int PrevotIndex () {Return Cursor - 1; } @SuppressWarnings ("deaktiviert") public e vorher () {CheckForComodification (); // die Position des vorherigen Elements der ArrayList int i = cursor - 1; Wenn (i <0) neue NoSuchelementException () werfen; Object [] elementData = arrayList.this.ElementData; if (i> = elementData.length) werfen neue ConcurrentModificationException (); Cursor = i; return (e) elementData [lastret = i]; } // Die festgelegte Methode wird diesem Iterator Public void set (e e) {if (lastret <0) abwerfen neu illegalStateException (); checkforComodification (); try {arrayList.this.set (lastret, e); } catch (indexoutOfboundSexception ex) {neue ConcurrentModificationException (); }} // Dieser Iterator fügt die add add method public void add (e e) {techeforComodification () hinzu; Versuchen Sie {int i = cursor; ArrayList.this.Add (i, e); // Bemerken Sie den Zeigerposition Cursor = i + 1; Lastret = -1; erweitertModcount = modcount; } catch (indexoutOfboundSexception ex) {neue ConcurrentModificationException (); }}}Die Implementierung von Listitr ist im Grunde genommen derselbe wie ITR und fügt Methoden hinzu, die zuvor durchquert werden können sowie Methoden hinzufügen und festlegen können.
(3) verwenden
CopyonWriteArrayList ist Thread-Safe. Weitere Informationen finden Sie in den Quellcode für Hinzufügen von Methodenquellen:
public boolean add (e e) {Final Reentrantlock lock = this.lock; lock.lock (); try {Object [] Elements = getArray (); int len = elements.length; Object [] NewElements = Arrays.copyof (Elemente, Len + 1); NewElements [len] = e; setArray (NewElements); zurückkehren; } endlich {lock.unlock (); }} CopyonWriteArrayList ist eine ArrayList, die auf Schreiben kopiert wird. Bei Beginn des Betriebs von Schreibdaten ist Arrays.copyof ein neues Array, das sich nicht auf den Lesevorgang auswirkt.
Diese Kosten sind, den Gedächtnis zu verlieren und Leistungsprobleme herbeizuführen. Wenn CopyonWriteArrayList geschrieben wird, wird ein Kopierobjekt im Speicher generiert und das ursprüngliche Objekt ist weiterhin vorhanden.
CopyonWriteArrayList kann die Konsistenz der Daten in Echtzeit nicht garantieren, sondern kann nur die Konsistenz der Ergebnisse garantieren. Geeignet für Szenarien wie Cache, wenn Sie mehr lesen und in gleichzeitigen Situationen weniger schreiben und weniger schreiben.
(4) andere Methoden Quellcode von ArrayList:
Eine private Methode Batchremove (Sammlung <?> C, Boolesche Komplement), dh der Batch -Entfernungsbetrieb
private boolean batchremove (Sammlung <?> C, boolean -Komplement) {// Der Grund für die Verwendung von Final wird unten erwähnt. Das endgültige Objekt [] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; Versuchen Sie {// Ruhe durch die Elemente in der Liste und verifizieren Sie (; r <size; r ++) if (c.contains (elementData [r]) == komplement) elementData [w ++] = elementData [r]; } endlich {// Wenn eine Ausnahme im Versuch auftritt, stellen Sie die Datenkonsistenz sicher und führen Sie die folgende Kopieroperation durch, wenn (r! = Größe) {System.ArrayCopy (ElementData, R, ElementData, W, Größe - R); W += Größe - R; } // Unbenutzte Elemente reinigen und GC benachrichtigen, um zu recyceln, wenn (w! = Größe) {// klare, um seine Arbeit für (int i = w; i <size; i ++) elementData [i] = null zu lassen; ModCount += Größe - W; Größe = W; modified = true; }} return modifiziert; } Die durch endgültige geänderte Variable bezieht sich auf dieselbe Referenz, um die Konsistenz der Daten später aufrechtzuerhalten.
Wenn Sie in dieser Methode Elemente in Sammlung C beibehalten möchten, ist der Komplementwert wahr. Wenn Sie Elemente in C entfernen möchten, ist der Komplementwert falsch. Dies wird zu den Retainall- bzw. RemoveAll -Methoden.
Tausch: Tauschen Sie die beiden Positionen in der ArrayList aus
2. LinkedList Quellcodeanalyse (JDK7)
LinkedList ist eine verknüpfte Liste. Im Vergleich zur Bestellentabelle muss die verknüpfte Liste keine kontinuierlichen Speichereinheiten verwenden, um Daten zu speichern. Reduziert das Problem der beweglichen Elemente, die durch Modifizierung der Containerstruktur verursacht werden, und der sequentielle Zugriff ist relativ effizient.
1. Definition des Knotens
LinkedList in JDK ist eine bidirektionale verknüpfte Liste. Jeder Knoten spielt Informationen zum vorherigen Knoten bzw. zum nächsten Knoten. Seine Definition ist wie folgt:
private statische Klassenknoten <e> {e item; Node <e> als nächstes; Knoten <e> pre; Knoten <E> (Knoten <e> prev, e Element, Knoten <e> next) {this.iTEM = Element; this.Next = Weiter; this.prev = prev; }}2. Konstruktion und Initialisierung LinkedList
Mitglied: 3 Mitgliedervariablen werden in der LinkedList verwaltet, um die Anzahl der Knoten in der verlinkten Liste, den Vorgänger und Nachfolger von Knoten aufzuzeichnen
transient int size = 0; transienter Knoten <e> zuerst; transienter Knoten <e> letztes;
Konstruktor: Der Standardkonstruktor besteht darin, eine leere LinkedList zu konstruieren
public linkedList () {}Oder basierend auf anderen Containern konstruieren, und später schreiben wir einen Konstruktor, um eine bestellte Linkliste zu erstellen.
public linkedList (Sammlung <? Erweitert E> c) {this (); Addall (c);}Hier ist ein bisschen mehr. Für den Unterschied zwischen dem generischen Modifikator? Super t und erweitert t, siehe diesen Artikel über den Unterschied zwischen Super T und Tast T in Generika.
3.. Strukturbetrieb der LinkedList
Header -Insertion -Methode: Starten Sie ein Element in den Kopfzeile der verknüpften Liste
private void linkfirst (e e) {endgültiger Knoten <e> f = zuerst; endgültiger Knoten <E> newnode = neuer Knoten <> (null, e, f); first = newnode; // Beurteilen Sie, ob es sich um eine leere verlinkte Liste handelt, wenn (f == null) last = newnode; sonst f.prev = newnode; Größe ++; ModCount ++; } Tail Insertion -Methode: Das heißt ein Element am Ende der verknüpften Liste einfügen
void linkLast (e e) {endgültiger Knoten <e> l = last; endgültiger Knoten <E> newnode = neuer Knoten <> (l, e, null); last = newnode; if (l == null) first = newnode; sonst l.next = newnode; Größe ++; ModCount ++; } Vor dem Einfügen in den aktuellen Knoten: Finden Sie den vorderen Laufwerk des aktuellen Knotens
void linkBefore (e e, Knoten <e> prof) {// Bestimmen Sie, ob der Knoten nicht leer ist. endgültiger Knoten <E> newnode = neuer Knoten <> (Pred, E, Procc); Succ.Prev = newnode; // Bestimmen Sie, ob der aktuelle Knoten der erste Knoten ist, wenn (pred == null) first = newnode; sonst pred.Next = newnode; Größe ++; ModCount ++; } Header -Löschung Methode: Löschen Sie den ersten Knoten der verknüpften Liste
private e uninkfirst (Knoten <e> f) {// Assert f == zuerst && f! = null; endgültig e Element = F.Item; endgültiger Knoten <e> next = f.Next; F.Item = null; F.Next = null; // hilf GC zuerst = Weiter; if (next == null) last = null; sonst als nächstes.prev = null; Größe--; ModCount ++; Rückgabeelement; } Schwanzdeletionsmethode: Löschen Sie den letzten Knoten der verknüpften Liste
private e Unklinast (Knoten <e> l) {// stellen Sie sicher, dass l == letztes und l! = null final e element = l.item; endgültiger Knoten <e> prew = l.prev; L.Item = null; l.prev = null; // hilf GC last = prev; if (prev == null) zuerst = null; sonst prev.Next = null; Größe--; ModCount ++; Rückgabeelement; }4. Behalten Sie die Konsistenz zwischen Listenschnittstelle und DEQUE bei
Die Listenschnittstelle ermöglicht die Verwendung von Indexs, den Zufallszugriff auf Container zu implementieren, und es ist einfach, den Zufallszugriff auf solche Arrays zu implementieren. Für verknüpfte Listen verwendet JDK auch logischerweise die Anzahl der Knoten in verknüpften Listen, um die Implementierung des Zufallszugriffs zu erhalten
Knoten <E> node (int index) {// Sicherstellen Sie die Richtigkeit des Index if (index <(Größe >> 1)) {Knoten <e> x = zuerst; für (int i = 0; i <index; i ++) x = x.Next; Rückkehr x; } else {node <e> x = last; für (int i = Größe-1; i> Index; i--) x = x.prev; Rückkehr x; }} Index ist die Anzahl der ersten Hälfte, die Suche von Anfang an. Der Index gehört zur Anzahl der zweiten Hälfte und sucht vom Ende. Nutzen Sie die Eigenschaften von zwei-Wege-verknüpften Listen vollständig.
Daher können add (int Index, T T), GET (int), Set (int) und andere Methoden einfach implementiert werden.
LinkedList implementiert die Deque-Schnittstelle, dh LinkedList implementiert die Methode der Doppel-Warteschlangenbehälter. Hier sind eine API -Zusammenfassung.
5. LinkedList Traversal
Da LinkedList eine wechselseitige Link-Liste ist, können Sie sie natürlich hin und her durchqueren. LinkedList hat ebenso wie ArrayList fehlgeschlagene Probleme, wenn es um den Multi-Threading-Containerbetrieb geht.
Das Problem des Fail-Fasts wurde im vorherigen Artikel erläutert, daher werde ich hier nicht darüber sprechen.
In Bezug auf Iteratoren verfügt LinkedList über einen bidirektionalen Iterator von Listiterator und einen Inverse -Iterator für Nachkommen. Alle sind sehr einfach. Quellcode wird nicht analysiert
Wenn Sie Elemente durchqueren, sind die Kosten für den Zufallszugriff relativ hoch.
3.. LinkedList, ArrayList, Vektorzusammenfassung
1. LinkedList und ArrayList
ArrayList implementiert eine Datenstruktur basierend auf dynamischen Arrays, und LinkedList basiert auf einer Datenstruktur, die auf einer verknüpften Liste basiert.
Für den Zufallszugriff zu GET und SET fühlt sich ArrayList besser als LinkedList, da LinkedList den Zeiger verschiebt.
Für neue und löschende Operationen hinzufügen und entfernen hat LineLedList einen besseren Vorteil, da ArrayList Daten verschieben muss. Dies hängt von der tatsächlichen Situation ab. Wenn nur ein einzelnes Datenstück eingefügt oder gelöscht wird, ist die Geschwindigkeit der ArrayList besser als die von LinkedList. Wenn Daten jedoch zufällig in Stapel eingefügt werden, ist die Geschwindigkeit der LinkedList viel besser als die von ArrayList. Denn jedes Mal, wenn eine ArrayList -Daten Daten einfügt, müssen Sie den Einfügenpunkt und alle Daten anschließend verschieben.
2. ArrayList und Vector
Der Vektor ist threadsynchron und ist auch mit Thread-Sicherheit, während ArrayList Thread-Asyn ist, was nicht sicher ist. Wenn nicht berücksichtigt werden, ist ArrayList im Allgemeinen effizienter.
Wenn die Anzahl der Elemente im Satz größer ist als die Länge des aktuellen Set -Arrays, beträgt die Vektorwachstumsrate 100% der Stromarray -Länge und die Wachstumsrate der Arraylist 50% der aktuellen Arraylänge. Wenn Sie Daten mit relativ großen Datenmengen im Satz verwenden, hat die Verwendung von Vektor bestimmte Vorteile.
Wenn Sie an einem bestimmten Ort nach Daten suchen, sind die von Vector und ArrayList verwendete Zeit gleich, sowohl 0 (1), und Sie können zu diesem Zeitpunkt Vektor- und ArrayList verwenden. Wenn die Zeit, die die Daten an einem bestimmten Ort verschoben haben, 0 (NI) N beträgt, was die Gesamtlänge ist, sollten Sie in Betracht ziehen, die LinkList verwenden, da es 0 (1) für die Verlagerung der Daten an einem bestimmten Ort benötigt, und die Zeit, die die Daten an einem bestimmten Ort abfragen, beträgt 0 (i).
ArrayList und Vektor verwenden Arrays, um Daten zu speichern. Die Anzahl der Elemente in diesem Array ist größer als die tatsächlichen gespeicherten Daten zum Hinzufügen und Einfügen von Elementen. Beide ermöglichen direkte Seriennummer -Indexelemente. Das Einfügen von Daten muss jedoch so konzipiert sein, dass Array -Elemente und andere Speichervorgänge verschoben werden. Indexdaten sind daher schnell und langsam ein Einfügen von Daten. Vektor verwendet synchronisierte Methode (Thread -Safe), sodass die Leistung schlechter ist als ArrayList. LinkedList verwendet eine bidirektionale verknüpfte Liste, um Daten zu speichern. Das Indexieren von Daten gemäß der Seriennummer erfordert Vorwärts- oder Rückwärtsfahrten. Wenn jedoch Daten eingefügt werden, werden jedoch nur die Vorder- und Rückseite dieses Elements aufgezeichnet, sodass das Einsetzen mehrerer Grad schneller ist!