Geekly articles weekly

Interne HashMap in Java

[Anmerkung des Autors der Übersetzung] Die Übersetzung wurde für die eigenen Bedürfnisse angefertigt, aber wenn sich herausstellt, dass sie für jemanden nützlich ist, ist die Welt zumindest ein wenig, aber besser geworden! Originalartikel - Interne Arbeitsweise von HashMap in Java


In diesem Artikel werden wir sehen, wie die get- und put-Methoden in der HashMap-Auflistung intern funktionieren. Welche Operationen werden ausgeführt? Wie Hashing passiert. Wie der Wert per Schlüssel abgerufen wird. Wie werden Schlüssel-Wert-Paare gespeichert?


Wie im vorherigen Artikel enthält HashMap ein Array von Node und Node kann eine Klasse darstellen, die die folgenden Objekte enthält:


  1. int - hash
  2. K ist der Schlüssel
  3. V ist der Wert
  4. Knoten - nächster Punkt

Jetzt werden wir sehen, wie alles funktioniert. Zunächst betrachten wir den Hashing-Prozess.


Hashing


Beim Hashing wird ein Objekt in eine Ganzzahlform konvertiert, die mit der Methode hashCode () ausgeführt wird. Es ist sehr wichtig, die hashCode () -Methode korrekt zu implementieren, um die beste Leistung der HashMap-Klasse sicherzustellen.


Hier verwende ich meine eigene Schlüsselklasse und kann auf diese Weise die hashCode () -Methode überschreiben, um verschiedene Skripte zu demonstrieren. Meine Schlüsselklasse:


//   Key    hashCode() //  equals() class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public boolean equals(Object obj) { return key.equals((String)obj); } }

Hier gibt die überschriebene hashCode () -Methode den ASCII-Code des ersten Zeichens der Zeichenfolge zurück. Wenn also die ersten Zeichen der Zeichenfolge identisch sind, sind die Hash-Codes identisch. Verwenden Sie in Ihren Programmen keine ähnliche Logik.


Dieser Code dient nur zu Demonstrationszwecken. Da der HashCode einen Nullschlüssel akzeptiert, ist der Null-Hash-Code immer 0.


HashCode () -Methode


Die hashCode () -Methode wird verwendet, um den Hash-Code des Objekts abzurufen. Die hashCode () -Methode der Object-Klasse gibt eine Ganzzahlspeicherreferenz (Identity-Hash-Code ) zurück. Die Signatur der public native hashCode() -Methode. Dies deutet darauf hin, dass die Methode als native implementiert ist, da es in Java keine Methode gibt, um einen Verweis auf das Objekt abzurufen. Sie können Ihre eigene Implementierung der hashCode () -Methode definieren. In der HashMap-Klasse wird die hashCode () -Methode verwendet, um den Bucket und damit den Index zu berechnen.


Equals () -Methode


Die Methode equals wird verwendet, um zwei Objekte auf Gleichheit zu testen. Die Methode ist in der Object-Klasse implementiert. Sie können es in Ihrer eigenen Klasse überschreiben. In der HashMap-Klasse wird die Methode equals () verwendet, um die Schlüsselgleichheit zu überprüfen. Wenn die Schlüssel gleich sind, gibt die Methode equals () true zurück, andernfalls false.


Körbe


Bucket ist das einzige Element des HashMap-Arrays. Es wird zum Speichern von Knoten (Nodes) verwendet. Zwei oder mehr Knoten können denselben Bucket haben. In diesem Fall wird eine verknüpfte Listendatenstruktur verwendet, um Knoten zu verknüpfen. Die Kapazität der Schaufeln ist unterschiedlich (Kapazitätseigenschaft). Die Beziehung zwischen Schaufel und Kapazität ist wie folgt:


 capacity = number of buckets * load factor

Ein Bucket kann mehr als einen Knoten haben, dies hängt von der Implementierung der hashCode () -Methode ab. Je besser Ihre hashCode () -Methode implementiert ist, desto besser wird Ihr Bucket verwendet.


HashMap-Indexberechnung


Der Schlüssel-Hash-Code kann groß genug sein, um ein Array zu erstellen. Der generierte Hash-Code kann im Bereich eines Integer-Typs liegen. Wenn wir ein Array dieser Größe erstellen, können wir leicht eine outOfMemoryException erhalten. Daher generieren wir einen Index, um die Größe des Arrays zu minimieren. Im Wesentlichen wird die folgende Operation ausgeführt, um den Index zu berechnen:


 index = hashCode(key) & (n-1).

Dabei ist n gleich der Anzahl der Buckets oder dem Wert der Länge des Arrays. In unserem Beispiel betrachte ich n als Standardwert von 16.


  • anfänglich hashMap leer: hier ist die Hashmap- Größe 16:

 HashMap map = new HashMap();

HashMap:


  • Paare einfügen Schlüsselwert: Fügen Sie am Ende der HashMap einen Paarschlüsselwert hinzu

 map.put(new Key("vishal"), 20);

Schritte:


  1. Berechnen Sie den Schlüsselwert {"vishal"}. Es wird als 118 generiert.


  2. Berechnen Sie den Index mit der index 6.


  3. Erstellen Sie ein Knotenobjekt.


     { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null }

  4. Platzieren Sie das Objekt in Position mit Index 6, wenn der Platz frei ist.



HashMap sieht jetzt ungefähr so ​​aus:



  • Hinzufügen eines weiteren Schlüssel-Wert-Paares: Fügen Sie nun ein weiteres Paar hinzu

 map.put(new Key("sachin"), 30);

Schritte:


  1. Berechnen Sie den Schlüsselwert {"sachin"}. Es wird als 115 generiert.


  2. Berechnen Sie den Index mit der index 3.


  3. Erstellen Sie ein Knotenobjekt.


     { int hash = 115 Key key = {"sachin"} Integer value = 30 Node next = null }

  4. Platzieren Sie das Objekt mit Index 3, wenn der Platz frei ist.



HashMap sieht jetzt ungefähr so ​​aus:



  • Bei Kollisionen: Fügen Sie jetzt ein weiteres Paar hinzu

 map.put(new Key("vaibhav"), 40);

Schritte:


  1. Berechnen Sie den Schlüsselwert {"vaibhav"}. Es wird als 118 generiert.


  2. Berechnen Sie den Index mit der index 6.


  3. Erstellen Sie ein Knotenobjekt.


     { int hash = 118 Key key = {"vaibhav"} Integer value = 20 Node next = null }

  4. Platzieren Sie das Objekt in Position mit Index 6, wenn der Platz frei ist.


  5. In diesem Fall existiert bereits ein anderes Objekt an der Position mit Index 6, dieser Fall wird als Kollision bezeichnet.


  6. In diesem Fall wird mit den Methoden hashCode () und equals () überprüft, ob beide Schlüssel identisch sind.


  7. Wenn die Schlüssel identisch sind, ersetzen Sie den aktuellen Wert durch einen neuen.


  8. Andernfalls verknüpfen Sie das neue und das alte Objekt mithilfe der Datenstruktur "Verknüpfte Liste", indem Sie einen Link zum nächsten Objekt im aktuellen Objekt angeben und beide unter Index 6 speichern.



HashMap sieht jetzt ungefähr so ​​aus:



[Anmerkung des Autors der Übersetzung] Das Bild stammt aus dem Originalartikel und enthält zunächst einen Fehler. Der Verweis auf das nächste Objekt im vishalen Objekt mit Index 6 ist nicht null, sondern enthält einen Zeiger auf das Vaibhav-Objekt.


  • Wir erhalten den Wert durch den Sachin-Schlüssel:

 map.get(new Key("sachin"));

Schritte:


  1. Berechnen Sie den Hash-Code des {{sachin »} -Objekts. Es wurde als 115 generiert.


  2. Berechnen Sie den Index mit der index 3.


  3. Gehen Sie zu Index 3 und vergleichen Sie den Schlüssel des ersten Elements mit dem vorhandenen Wert. Wenn sie gleich sind, drehen Sie den Wert, andernfalls prüfen Sie, ob das nächste Element vorhanden ist.


  4. In unserem Fall wird das Element gefunden und der Rückgabewert beträgt 30.



  • Wir erhalten den Wert durch den Schlüssel vaibahv:

 map.get(new Key("vaibhav"));

Schritte:


  1. Berechnen Sie den Hash-Code des Objekts {"vaibhav"}. Es wurde als 118 generiert.


  2. Berechnen Sie den Index mit der index 6.


  3. Gehen Sie zu Index 6 und vergleichen Sie den Schlüssel des ersten Elements mit dem vorhandenen Wert. Wenn sie gleich sind, drehen Sie den Wert, andernfalls prüfen Sie, ob das nächste Element vorhanden ist.


  4. In diesem Fall wurde es nicht gefunden und das nächste Knotenobjekt ist nicht null.


  5. Wenn das nächste Knotenobjekt null ist, geben Sie null zurück.


  6. Wenn das nächste Knotenobjekt nicht null ist, gehen Sie zu ihm und wiederholen Sie die ersten drei Schritte, bis das Element gefunden wird oder das nächste Knotenobjekt null ist.



 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } }

Fazit:


 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Änderungen in Java 8


Wie wir bereits bei Kollisionen wissen, wird das Knotenobjekt in der Datenstruktur „Verknüpfte Liste“ gespeichert und die Methode equals () zum Vergleichen von Schlüsseln verwendet. Dies sind Vergleiche, um den richtigen Schlüssel in einer verknüpften Liste zu finden - eine lineare Operation, und im schlimmsten Fall ist die Komplexität O (n) .


Um dieses Problem in Java 8 zu beheben, werden nach Erreichen eines bestimmten Schwellenwerts ausgeglichene Bäume anstelle von verknüpften Listen verwendet. Dies bedeutet, dass die HashMap zu Beginn die Objekte in einer verknüpften Liste speichert. Nachdem jedoch die Anzahl der Elemente im Hash einen bestimmten Schwellenwert erreicht hat, erfolgt ein Übergang zu ausgeglichenen Bäumen. Dies verbessert die Leistung im schlimmsten Fall von O (n) auf O (log n).


Wichtiger Punkt


  1. Die Komplexität der Operationen get () und put () ist nahezu konstant, bis ein erneutes Hashing durchgeführt wird.
  2. Wenn bei Kollisionen die Indizes von zwei oder mehr Knotenobjekten gleich sind, werden die Knotenobjekte unter Verwendung einer verknüpften Liste verbunden, d. H. Die Verknüpfung zum zweiten Knotenobjekt wird im ersten, zum dritten im zweiten usw. gespeichert.
  3. Wenn der angegebene Schlüssel bereits in der HashMap vorhanden ist, wird der Wert überschrieben.
  4. Der Null-Hash-Code ist 0.
  5. Wenn ein Objekt durch den Schlüssel erhalten wird, treten Übergänge durch die verknüpfte Liste auf, bis das Objekt gefunden wird oder die Verknüpfung zum nächsten Objekt null ist.

Source: https://habr.com/ru/post/de421179/

More articles:


All Articles