Die Datenliste, die häufiger im Code verwendet wird, lautet hauptsächlich Liste und sie sind alle ArrayList. Es fühlt sich so an, als wäre dieses Ding genug. ArrayList ist eine Wrapper -Tool -Klasse, die zur Implementierung dynamischer Arrays verwendet wird, sodass Sie beim Schreiben von Code ein- und ausziehen können, iterieren und durchqueren können, was sehr bequem ist.
Ich weiß nicht, wann ich anfing, Tool -Kurse wie HashMap und Hashset langsam im Code zu starten. Es sollte gesagt werden, dass Hashmap häufiger ist und auch eine klassische Interviewfrage, also werde ich im täglichen Leben mehr davon lesen. Als ich anfing, es zu verwenden, habe ich es einfach als einen entsprechenden Schlüsselwert verstanden, und es ist bequemer, Schlüssel zu verwenden, um Daten zu finden. Nach weiteren Untersuchungen fand ich es heraus
Dieses Ding hat einige Geheimnisse, insbesondere nachdem die neue Version von JDK HashMap in einen Baum ändert, ist der Code etwas kompliziert.
Ich begann weniger Set zu verwenden, aber ich fand versehentlich einen Treeset in einem Code. Ich fand, dass diese Klasse mit Glätte kommen kann. Es fühlte sich sehr interessant an. Ich stellte allmählich fest, dass dies auch ein gutes Werkzeug ist.
Wenn Sie zu viel Code schreiben, werden Sie die Wichtigkeit der Grundlagen spüren. Hier schreibe ich hier einen kurzen Artikel, um kurz Wissen über die Sammlung zu organisieren.
Ok, lass es uns kurz klären:
• Liste: Das heißt eine Liste, die die Funktionen von Arrays und verknüpften Listen unterstützt und im Allgemeinen linear ist.
• Karte: Es handelt sich um eine Zuordnungstabelle, in der die entsprechende Beziehung zwischen Schlüssel und Werten gespeichert ist.
• festgelegt: bedeutet festgelegt, hauptsächlich zum Sortieren und Sortieren von Daten und Sortieren verwendet
Schauen wir uns zuerst die Liste an
List ist ein Fenster zum Speichern linearer Daten wie: ArrayList für Arrays und LinkedList für verknüpfte Listen.
ArrayList
Dies ist eine Array -Liste, bietet jedoch eine automatische Erweiterungsfunktion, um die Listenschnittstelle zu realisieren. Auf externe Vorgänge wird durch die sicher und bequeme Schnittstellenerklärungmethode zugegriffen.
Der Schlüssel zur ArrayList ist die automatische Kapazitätserweiterung. Die anfängliche Kapazität kann festgelegt werden, wenn das Objekt initialisiert wird oder die Standardkapazität gemessen werden kann. Wenn die Arraygröße nicht besonders klar ist, kann die anfängliche Größe nicht angegeben werden. Wenn klar ist, kann eine Größe angegeben werden, wodurch die durch dynamische Expansion verursachte Verzögerung verringert wird. Apropos müssen wir darüber sprechen, wie die Erweiterung umgesetzt wird. Schauen Sie sich den folgenden Code an:
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); }Wachstum ist eine Methode, die ArrayList beim Hinzufügen von Elementen oder einige einfache Überprüfungen auslöst. Hauptprozess:
1. Holen Sie sich die Länge des Arrays und bewegen
2. Wenn diese Länge geringer ist als die Mindestkapazität, kann sie einfach direkt verwendet werden.
3. Wenn es größer als das Maximum ist, nehmen Sie einen Maximalwert. Eine Hugenkapazitätsmethode wird hier aufgerufen, hauptsächlich, um die Halsschärfe mit max_array_size zu vergleichen. Wenn die Mischung größer als max_array_size ist, nehmen Sie Integer.max_value, ansonsten max_array_size. Interessanterweise nimmt Max_array_size Integer.max_Value - 8; Ich weiß nicht, was die Bedeutung dafür ist
4. Rufen Sie schließlich eine Kopiermethode an, um die vorhandene Nummer in ein neues Array zu kopieren.
Aufgrund dieses Kopiervorgangs wird die Ausdehnung sicherlich eine Verzögerung verursachen, wenn das Array relativ groß ist. Wenn Sie also den Maximalwert von Anfang an kennen und es einfach ist, diesen Wert zu wachsen, hat die Angabe der Größe beim Beginn der Initialisierung einen bestimmten Effekt.
LinkedList
Dies ist eine Werkzeugkurs für verknüpfte Listen. Die Vorteile von verknüpften Listen sind, dass sie die Dinge schneller hinzufügen und löschen, aber sie werden sie langsamer finden.
Was den Code betrifft, so scheint es, dass nichts Besonderes ist, dass es von einer Reihe von Zeigern miteinander verbunden ist. Natürlich verwendet Java Objekte stattdessen, um ein Knotenobjekt zu erstellen. Der Knoten selbst zeigt auf den vorherigen Knoten und den nächsten Knoten. Dies ist die Struktur der verknüpften Liste:
private statische Klassenknoten <e> {e item; Node <e> als nächstes; Knoten <e> pre; Knoten (Knoten <e> prev, e Element, Knoten <e> next) {this.Item = Element; this.Next = Weiter; this.prev = prev; }}Verwenden Sie dann zwei Knoten, um auf Kopf und Schwanz zu zeigen, und es ist erledigt. Der folgende Code:
/*** Zeiger auf den ersten Knoten. * Invariante: (first == null && last == null) || * (first.prev == null && first.item! = null) */ transient node <e> zuerst; /*** Zeiger auf den letzten Knoten. * Invariante: (first == null && last == null) || * (last.next == null && last.item! = null) */ transient node <e> last;
Siehe eine Operation hinzufügen:
/*** Links E als letztes Element. */ void linkLast (e e) {endgültiger Knoten <e> l = zuletzt; endgültiger Knoten <E> newnode = neuer Knoten <> (l, e, null); last = newnode; if (l == null) first = newnode; sonst l.next = newnode; Größe ++; ModCount ++; }Die Vergangenheit ist:
1. Holen Sie sich den letzten Knoten und geben Sie ihn in l
2. Erstellen Sie einen neuen Knoten und holen Sie die Daten in diesen Knoten. Der Erstellungsprozess verweist die Vorgänger des neuen Knotens auf L, damit er mit der Kette verbunden ist.
3. Dann zeigen Sie den neuen Knoten zuletzt
4. Bestimmen Sie, ob L null ist. Wenn Null Null ist, bedeutet dies, dass es sich um eine leere verlinkte Liste handelt. Der neue Knoten ist das erste Element. Auf diese Weise muss der erste auch auf Newnode verweisen
5. Wenn es nicht leer ist, zeigen Sie den nächsten von L auf Newnode
6. Akkumulationszähler
Der Löschvorgang ist auch der vordere und hintere Knoten, der auf den Bewegungsvorgang dieses Knotens zeigt.
Schauen wir uns die Karte an
MAP ist eine Anwendung einer Mapping -Tabelle für Schlüssel und Werte. Die wichtigsten Implementierungsklassen: Hashmap, Hashtable, Treemap
Hashmap und Hashtable
HashMap ist derjenige, der den Hash-Algorithmus für die Schlüsselwert-Zuordnung verwendet. Hashtable ist eine thread-sichere Klasse mit Synchronisation. Dies ist der Hauptunterschied zwischen ihnen. Das Prinzip ist ähnlich und sie werden alle durch die Bucket + -Kettenkombination erreicht. Der Eimer wird verwendet, um Schlüssel zu speichern, und der Wert muss aufgrund der Hash -Kollision in einer verknüpften Liste gespeichert werden.
• Die Bedeutung des Eimers liegt in der Effizienz und kann in einem Schritt durch Hash -Berechnungen positioniert werden.
• Die Bedeutung von verknüpften Listen besteht darin, auf die Daten von wiederholten Hash zuzugreifen
Das spezifische Prinzip, das ich "Studiennotizen: Hashtable und HashMap" zuvor geschrieben habe
Aber ich habe gerade gesehen, dass Hashmap von JDK1.8 seine Lagerstruktur verändert und eine rote und schwarze Baumstruktur angewendet hat. Dies kann die Effizienz der verknüpften Listensuche lösen? Es wurde keine detaillierte Studie durchgeführt.
Treemap
Nachdem ich den Treemap -Code gelesen hatte, stellte ich fest, dass ich immer noch die Baumstruktur rote und schwarze Bäume verwende. Da die roten und schwarzen Bäume bestellt werden, haben sie natürlich die Sortierfunktion. Natürlich können Sie auch die Vergleichsmethode über den Komparator angeben, um eine spezifische Sortierung zu erreichen.
Da die Baumstruktur zum Speichern verwendet wird, ist es schwieriger, Daten hinzuzufügen und zu löschen. Schauen wir uns den Put -Code an:
public v put (k key, v Wert) {Eintrag <k, v> t = root; if (t == null) {compare (Schlüssel, Schlüssel); // type (und mögliche NULL) prüfen Root = neuer Eintrag <> (Schlüssel, Wert, NULL); Größe = 1; ModCount ++; null zurückkehren; } int cmp; Eintrag <k, v> Eltern; // Split -Komparator und vergleichbare Pfade vergleicher <? Super k> cpr = vergleicher; if (cpr! = null) {do {parent = t; CMP = CPR.comPare (Schlüssel, T.Key); if (cmp <0) t = t.left; sonst wenn (cmp> 0) t = t.right; sonst return t.setValue (Wert); } while (t! = null); } else {if (key == null) werfen neue nullpointerexception (); @SuppressWarnings ("Unbeschwert") vergleichbar <? Super k> k = (vergleichbar <? Super K>) Key; do {parent = t; cmp = k.comPareto (T.Key); if (cmp <0) t = t.left; sonst wenn (cmp> 0) t = t.right; sonst return t.setValue (Wert); } while (t! = null); } Eintrag <k, v> e = neuer Eintrag <> (Schlüssel, Wert, Eltern); if (cmp <0) parent.left = e; sonst parent.right = e; FixAfterInsertion (e); Größe ++; ModCount ++; null zurückkehren; }1. Überprüfen Sie zuerst, ob der Stammknoten existiert. Wenn es nicht existiert, bedeutet dies, dass es das erste Datenstück ist und direkt als Wurzel des Baumes verwendet wird.
2. Bestimmen Sie, ob es einen Komparator gibt. Wenn ja, verwenden Sie den Komparator, um den Speicherort der Daten zu finden. Wenn das Ergebnis der Rückgabe des Komparators weniger als 0 beträgt, nehmen Sie die linke und nehmen Sie die rechte, ansonsten den Wert des aktuellen Knotens direkt ersetzen.
3. Wenn es keinen Komparator gibt, wird der Schlüssel direkt mit dem Schlüssel des Knotens verglichen. Der Vergleich entspricht der vorherigen Methode.
4. Der nächste Schritt besteht darin, einen untergeordneten Knoten auf dem gefundenen Elternteil zu erstellen und ihn in die linken oder rechten untergeordneten Knoten zu legen.
5. FixAfterInsertion ist zu färben Knoten
6. Akkumulatorverarbeitung
Es wird auch ein bisschen problematisch sein, wenn die Daten entfernt werden. Zusätzlich zum Löschen der Daten müssen Sie auch die roten und schwarzen Bäume wieder ausführen.
Darüber hinaus implementiert Treemap die Navigablemap <K, V> -Schinschnittstelle und bietet daher auch einige Rückgabeberationen für den Datensatz.
Schauen Sie sich schließlich einen Set an
Set hauptsächlich zwei Arten von Anwendungen: Hashset und Treeset.
Hashset
Die wörtliche Bedeutung ist sehr klar und verwendet eine Sammlung von Hash. Das Merkmal dieser Sammlung besteht darin, den Hash -Algorithmus zum Speichern von Daten zu verwenden, sodass die Daten nicht dupliziert werden und der Zugriff relativ schnell ist. Wie ist es gemacht?
public boolean add (e e) {return map.put (e, vorhanden) == null; }Es stellt sich heraus, dass es ein Kartenobjekt gibt. Schauen wir uns an, was die Karte ist?
private transiente Hashmap <e, Objekt> Karte;
Es ist eine Hashmap. Diejenigen, die wissen, dass HashMap nicht mehr wiederholt wird. Da das Objekt selbst bei der Ablagerung als Schlüssel gespeichert ist, gibt es im HashMap nur eine Kopie.
Nachdem Sie dies und andere Dinge verstanden haben, werden Sie sehr gut verstehen.
Treeset
Dieser Satz wird verwendet, um das Satz zu sortieren, was bedeutet, dass es zusätzlich die Fähigkeit zur Sortierung von schwerer Sortierfunktion auch eine eigene Sortierfunktion haben kann. Nachdem ich mir den Code von Treeset angesehen hatte, stellte ich fest, dass er in den Grundlagen von Treemap implementiert wurde. Genauer gesagt sollte es eine abgeleitete Klasse von Navigablemap sein. Treeset basiert auf Treemap, ohne die Karte standardmäßig anzugeben.
public treeset () {this (New Treemap <e, Object> ()); }Also, was wir hier mehr achten können, ist, wie Treeset schwer ist? Werfen wir einen Blick auf die Methode des Addierens:
public boolean add (e e) {return m.put (e, vorhanden) == null; }Es ist Hashset etwas ähnlich, die beide auf den Merkmalen der MAP basieren, um eine starke Belastung zu erzielen. Es ist wirklich einfach und effektiv.
Das obige ist die detaillierte Erläuterung von Set, Liste und Karte in Java, die der Herausgeber Ihnen bringt. Ich hoffe, Sie können Wulin.com mehr unterstützen ~