Nach meinem Verständnis denke ich:
- Es ist völlig legal, dass zwei Objekte denselben Hashcode haben.
- Wenn zwei Objekte gleich sind (mit der Methode equals ()), haben sie denselben Hashcode.
- Wenn zwei Objekte nicht gleich sind, können sie nicht denselben Hashcode haben
Hab ich recht?
Wenn das nun stimmt, habe ich folgende Frage: Der verwendet HashMap
intern den Hashcode des Objekts. Wenn also zwei Objekte denselben Hashcode haben können, wie kann dann verfolgt werden, HashMap
welchen Schlüssel sie verwenden?
Kann jemand erklären, wie der HashMap
intern den Hashcode des Objekts verwendet?
java
hashmap
hashcode
hash-function
Akshay
quelle
quelle
Antworten:
Eine Hashmap funktioniert folgendermaßen (dies ist ein wenig vereinfacht, zeigt aber den grundlegenden Mechanismus):
Es verfügt über eine Reihe von "Buckets", in denen Schlüssel-Wert-Paare gespeichert werden. Jeder Bucket hat eine eindeutige Nummer - das ist es, was den Bucket identifiziert. Wenn Sie ein Schlüssel-Wert-Paar in die Karte einfügen, zeigt die Hashmap den Hash-Code des Schlüssels an und speichert das Paar in dem Bucket, dessen Kennung der Hash-Code des Schlüssels ist. Beispiel: Der Hash-Code des Schlüssels lautet 235 -> das Paar wird in Bucket Nummer 235 gespeichert. (Beachten Sie, dass ein Bucket mehr als ein Schlüssel-Wert-Paar speichern kann.)
Wenn Sie einen Wert in der Hashmap nachschlagen, indem Sie ihm einen Schlüssel geben, wird zuerst der Hash-Code des von Ihnen angegebenen Schlüssels angezeigt. Die Hashmap untersucht dann den entsprechenden Bucket und vergleicht den von Ihnen angegebenen Schlüssel mit den Schlüsseln aller Paare im Bucket, indem Sie sie mit vergleichen
equals()
.Jetzt können Sie sehen, wie effizient dies ist, um Schlüssel-Wert-Paare in einer Karte nachzuschlagen: Durch den Hash-Code des Schlüssels weiß die Hashmap sofort, in welchem Bucket sie suchen muss, sodass sie nur testen muss, was sich in diesem Bucket befindet.
Wenn Sie sich den obigen Mechanismus ansehen, können Sie auch sehen, welche Anforderungen an die
hashCode()
undequals()
Methoden der Schlüssel erforderlich sind :Wenn zwei Schlüssel gleich (sind
equals()
Renditen ,true
wenn man sie vergleichen), ihrehashCode()
Methode müssen die gleiche Anzahl zurück. Wenn Schlüssel dagegen verstoßen, werden gleichwertige Schlüssel möglicherweise in verschiedenen Buckets gespeichert, und die Hashmap kann keine Schlüssel-Wert-Paare finden (da sie im selben Bucket angezeigt werden).Wenn zwei Schlüssel unterschiedlich sind, spielt es keine Rolle, ob ihre Hash-Codes gleich sind oder nicht. Sie werden im selben Bucket gespeichert, wenn ihre Hash-Codes identisch sind. In diesem Fall werden sie anhand der Hashmap
equals()
voneinander unterschieden.quelle
hashCode()
Methode jedoch unterschiedliche Hash-Codes zurückgibt, verstoßen die Methodenequals()
undhashCode()
der Schlüsselklasse gegen den Vertrag, und Sie erhalten seltsame Ergebnisse, wenn Sie diese Schlüssel in a verwendenHashMap
.HashMap
, den Sie in der Dateisrc.zip
in Ihrem JDK-Installationsverzeichnis finden.Ihre dritte Behauptung ist falsch.
Es ist völlig legal, dass zwei ungleiche Objekte denselben Hash-Code haben. Es wird von
HashMap
als "First-Pass-Filter" verwendet, damit die Karte mögliche Einträge mit dem angegebenen Schlüssel schnell finden kann . Die Schlüssel mit demselben Hashcode werden dann auf Gleichheit mit dem angegebenen Schlüssel getestet.Sie möchten nicht, dass zwei ungleiche Objekte nicht denselben Hash-Code haben, da Sie sonst auf 2 32 mögliche Objekte beschränkt wären . (Dies würde auch bedeuten, dass verschiedene Typen nicht einmal die Felder eines Objekts zum Generieren von Hash-Codes verwenden könnten, da andere Klassen denselben Hash generieren könnten.)
quelle
HashMap
ist ein Array vonEntry
Objekten.Betrachten Sie
HashMap
als nur ein Array von Objekten.Schauen Sie sich an, was das
Object
ist:Jedes
Entry
Objekt repräsentiert ein Schlüssel-Wert-Paar. Das Feldnext
bezieht sich auf ein anderesEntry
Objekt, wenn ein Bucket mehr als ein Objekt hatEntry
.Manchmal kann es vorkommen, dass Hash-Codes für zwei verschiedene Objekte gleich sind. In diesem Fall werden zwei Objekte in einem Bucket gespeichert und als verknüpfte Liste angezeigt. Der Einstiegspunkt ist das zuletzt hinzugefügte Objekt. Dieses Objekt bezieht sich auf ein anderes Objekt mit dem
next
Feld und so weiter. Der letzte Eintrag bezieht sich aufnull
.Wenn Sie eine
HashMap
mit dem Standardkonstruktor erstellenDas Array wird mit der Größe 16 und einem Standard-Lastausgleich von 0,75 erstellt.
Hinzufügen eines neuen Schlüssel-Wert-Paares
hash % (arrayLength-1)
an der das Element platziert werden soll (Bucket-Nummer)HashMap
, wird der Wert überschrieben.Wenn der Eimer bereits mindestens ein Element enthält, wird ein neues hinzugefügt und an der ersten Position des Eimers platziert. Sein
next
Feld bezieht sich auf das alte Element.Streichung
hash % (arrayLength-1)
Entry
. Wenn ein gewünschtes Element nicht gefunden wird, kehren Sie zurücknull
quelle
hash % (arrayLength-1)
, wäre eshash % arrayLength
. Aber es ist tatsächlich sohash & (arrayLength-1)
. Das heißt, weil es Potenzen von zwei (2^n
) für die Arraylänge verwendet undn
niedrigstwertige Bits benötigt.int
was natürlich negativ sein kann, Modulo auf einer negativen Zahl zu tun, gibt Ihnen eine negative ZahlHervorragende Informationen finden Sie unter http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html
Zusammenfassen:
HashMap arbeitet nach dem Prinzip des Hashings
put (Schlüssel, Wert): HashMap speichert sowohl Schlüssel als auch Wertobjekt als Map.Entry. Hashmap wendet Hashcode (Schlüssel) an, um den Bucket zu erhalten. Bei einer Kollision verwendet HashMap LinkedList zum Speichern des Objekts.
get (key): HashMap verwendet den Hashcode von Key Object, um die Position des Buckets zu ermitteln, und ruft dann die Methode keys.equals () auf, um den richtigen Knoten in LinkedList zu identifizieren und das zugehörige Wertobjekt für diesen Schlüssel in Java HashMap zurückzugeben.
quelle
Hier ist eine grobe Beschreibung des
HashMap
Mechanismus für dieJava 8
Version (er kann sich geringfügig von Java 6 unterscheiden) .Datenstrukturen
Hash-Wert wird über den
hash()
Schlüssel on berechnet und entscheidet, welcher Bucket der Hashtabelle für einen bestimmten Schlüssel verwendet werden soll.Wenn die Anzahl der Elemente in einem Bucket gering ist, wird eine einzeln verknüpfte Liste verwendet.
Wenn die Anzahl der Elemente in einem Eimer groß ist, wird ein Rot-Schwarz-Baum verwendet.
Klassen (intern)
Map.Entry
Stellen Sie eine einzelne Entität in der Karte dar, die Schlüssel- / Wertentität.
HashMap.Node
Verknüpfte Listenversion des Knotens.
Es könnte darstellen:
Weil es eine Hash-Eigenschaft hat.
HashMap.TreeNode
Baumversion des Knotens.
Felder (intern)
Node[] table
Die Bucket-Tabelle (Kopf der verknüpften Listen).
Wenn ein Bucket keine Elemente enthält, ist er null und nimmt daher nur Platz für eine Referenz.
Set<Map.Entry> entrySet
Satz von Entitäten.int size
Anzahl der Entitäten.
float loadFactor
Geben Sie an, wie voll die Hash-Tabelle zulässig ist, bevor Sie die Größe ändern.
int threshold
Die nächste Größe, bei der die Größe geändert werden soll.
Formel:
threshold = capacity * loadFactor
Methoden (intern)
int hash(key)
Berechnen Sie den Hash anhand des Schlüssels.
Wie ordne ich Hash dem Bucket zu?
Verwenden Sie folgende Logik:
Über die Kapazität
In der Hash-Tabelle bedeutet Kapazität die Anzahl der Buckets, von denen sie stammen könnte
table.length
.Auch könnte über
threshold
und berechnet werdenloadFactor
, so dass kein Klassenfeld definiert werden muss.Könnte die effektive Kapazität erhalten über:
capacity()
Operationen
Suchen Sie zuerst den Bucket anhand des Hashwerts und wiederholen Sie dann die verknüpfte Liste oder den sortierten Baum.
Suchen Sie zuerst den Bucket nach dem Hashwert des Schlüssels.
Versuchen Sie dann, den Wert zu finden:
Wenn
threshold
erreicht, wird die Kapazität der Hashtabelle (table.length
) verdoppelt , und anschließend werden alle Elemente erneut gehasht , um die Tabelle neu zu erstellen .Dies könnte eine teure Operation sein.
Performance
Zeitliche Komplexität ist
O(1)
, weil:O(1)
.O(1)
.O(1)
nicht angesehen werdenO(log N)
.quelle
Der Hashcode bestimmt, welcher Bucket für die Hashmap überprüft werden soll. Befindet sich mehr als ein Objekt im Bucket, wird eine lineare Suche durchgeführt, um herauszufinden, welches Element im Bucket dem gewünschten Element entspricht (unter Verwendung der
equals()
Methode).Mit anderen Worten, wenn Sie einen perfekten Hashcode haben und der Hashmap-Zugriff konstant ist, müssen Sie niemals durch einen Bucket iterieren (technisch gesehen müssten Sie auch MAX_INT-Buckets haben, die Java-Implementierung kann einige Hash-Codes im selben Bucket gemeinsam nutzen Platzbedarf reduzieren). Wenn Sie den schlechtesten Hashcode haben (gibt immer die gleiche Nummer zurück), wird Ihr Hashmap-Zugriff linear, da Sie jedes Element auf der Karte durchsuchen müssen (alle befinden sich im selben Bucket), um das zu erhalten, was Sie möchten.
Meistens ist ein gut geschriebener Hashcode nicht perfekt, aber einzigartig genug, um Ihnen mehr oder weniger konstanten Zugriff zu ermöglichen.
quelle
Sie irren sich in Punkt drei. Zwei Einträge können denselben Hashcode haben, sind jedoch nicht gleich. Schauen Sie sich die Implementierung von HashMap.get aus dem OpenJdk an . Sie können sehen, dass überprüft wird, ob die Hashes gleich und die Schlüssel gleich sind. Wäre Punkt drei wahr, wäre es nicht notwendig zu überprüfen, ob die Schlüssel gleich sind. Der Hash-Code wird vor dem Schlüssel verglichen, da ersterer ein effizienterer Vergleich ist.
Wenn Sie mehr darüber erfahren möchten, lesen Sie den Wikipedia-Artikel zur Open Addressing-Kollisionsauflösung , der meiner Meinung nach der Mechanismus ist, den die OpenJdk-Implementierung verwendet. Dieser Mechanismus unterscheidet sich geringfügig von dem "Bucket" -Ansatz, den eine der anderen Antworten erwähnt.
quelle
Hier sehen wir also, dass wenn beide Objekte S1 und S2 unterschiedliche Inhalte haben, wir ziemlich sicher sind, dass unsere überschriebene Hashcode-Methode für beide Objekte unterschiedliche Hashcodes (116232,11601) generiert. JETZT, da es verschiedene Hash-Codes gibt, wird es nicht einmal die Mühe machen, die EQUALS-Methode aufzurufen. Weil ein anderer Hashcode UNTERSCHIEDLICHE Inhalte in einem Objekt GARANTIERT.
quelle
Java 8 Update in HashMap-
Sie führen diese Operation in Ihrem Code aus -
Angenommen, Ihr Hashcode wird für beide Schlüssel zurückgegeben
"old"
und"very-old"
ist gleich. Was wird dann passieren?myHashMap
ist eine HashMap, und nehmen Sie an, dass Sie ihre Kapazität anfangs nicht angegeben haben. Die Standardkapazität gemäß Java beträgt also 16. Sobald Sie die Hashmap mit dem neuen Schlüsselwort initialisiert haben, wurden 16 Buckets erstellt. jetzt, als Sie die erste Anweisung ausgeführt haben-dann wird der Hashcode für
"old"
berechnet, und da der Hashcode auch eine sehr große Ganzzahl sein kann, hat Java dies intern getan - (Hash ist hier Hashcode und >>> ist Rechtsverschiebung)Um ein größeres Bild zu erhalten, wird ein Index zurückgegeben, der zwischen 0 und 15 liegt. Jetzt Ihr Schlüsselwertpaar
"old"
und"old-value"
würde in den Entry Schlüssel und den Wert des Objekts Instanzvariable umgewandelt werden. und dann wird dieses Eintragsobjekt im Bucket gespeichert, oder Sie können sagen, dass dieses Eintragsobjekt an einem bestimmten Index gespeichert wird.FYI-Entry ist eine Klasse in Map Interface-Map.Entry mit dieser Signatur / Definition
jetzt, wenn Sie die nächste Anweisung ausführen -
und
"very-old"
gibt denselben Hashcode wie aus"old"
, sodass dieses neue Schlüsselwertpaar erneut an denselben Index oder denselben Bucket gesendet wird. Da dieser Bucket jedoch nicht leer ist, wird dienext
Variable des Entry-Objekts zum Speichern dieses neuen Schlüsselwertpaars verwendet.und dies wird als verknüpfte Liste für jedes Objekt gespeichert, das denselben Hashcode hat, aber ein TRIEFY_THRESHOLD mit dem Wert 6 angegeben wird. Nachdem dies erreicht ist, wird die verknüpfte Liste in den ausgeglichenen Baum (rot-schwarzer Baum) mit dem ersten Element als konvertiert Wurzel.
quelle
Jedes Eintragsobjekt repräsentiert ein Schlüssel-Wert-Paar. Das nächste Feld bezieht sich auf ein anderes Eintragsobjekt, wenn ein Bucket mehr als einen Eintrag hat.
Manchmal kann es vorkommen, dass hashCodes für 2 verschiedene Objekte gleich sind. In diesem Fall werden 2 Objekte in einem Bucket gespeichert und als LinkedList dargestellt. Der Einstiegspunkt ist ein kürzlich hinzugefügtes Objekt. Dieses Objekt bezieht sich auf ein anderes Objekt mit dem nächsten Feld und damit einem. Letzter Eintrag bezieht sich auf null. Wenn Sie HashMap mit dem Standardkonstruktor erstellen
Das Array wird mit der Größe 16 und einem Standard-Lastausgleich von 0,75 erstellt.
(Quelle)
quelle
Hash Map arbeitet nach dem Prinzip des Hashings
Die HashMap-Methode get (Key k) ruft die hashCode-Methode für das Schlüsselobjekt auf und wendet den zurückgegebenen hashValue auf seine eigene statische Hash-Funktion an, um einen Bucket-Speicherort (Backing-Array) zu finden, in dem Schlüssel und Werte in Form einer verschachtelten Klasse namens Entry (Map) gespeichert sind. Eintrag). Sie haben also aus der vorherigen Zeile den Schluss gezogen, dass sowohl Schlüssel als auch Wert als eine Art Eingabeobjekt im Bucket gespeichert sind. Der Gedanke, dass nur Wert im Eimer gespeichert ist, ist also nicht korrekt und hinterlässt beim Interviewer keinen guten Eindruck.
Wenn der Schlüssel null ist, werden Nullschlüssel immer dem Hash 0 zugeordnet, also dem Index 0.
Wenn key dann nicht null ist, ruft es Hashfunktion für das Schlüsselobjekt auf, siehe Zeile 4 in der obigen Methode, dh key.hashCode (). Nachdem key.hashCode () hashValue zurückgegeben hat, sieht Zeile 4 so aus
und jetzt wendet es den zurückgegebenen hashValue auf seine eigene Hashing-Funktion an.
Wir fragen uns vielleicht, warum wir den Hashwert erneut mit Hash (hashValue) berechnen. Die Antwort lautet: Es schützt vor Hash-Funktionen von schlechter Qualität.
Jetzt wird der endgültige Hashwert verwendet, um den Bucket-Speicherort zu ermitteln, an dem das Entry-Objekt gespeichert ist. Das Eintragsobjekt wird wie folgt im Bucket gespeichert (Hash, Schlüssel, Wert, Bucketindex).
quelle
Ich werde nicht näher auf die Funktionsweise von HashMap eingehen, sondern ein Beispiel geben, damit wir uns daran erinnern können, wie HashMap funktioniert, indem wir es mit der Realität in Beziehung setzen.
Wir haben Schlüssel, Wert, HashCode und Bucket.
Für einige Zeit werden wir jeden von ihnen mit folgendem in Verbindung bringen:
Verwenden von Map.get (Schlüssel):
Stevie möchte zum Haus seines Freundes (Josse) gelangen, der in einer Villa in einer VIP-Gesellschaft lebt. Lassen Sie es die JavaLovers Society sein. Josse's Adresse ist seine SSN (die für jeden anders ist). Es wird ein Index geführt, in dem wir den Namen der Gesellschaft basierend auf SSN herausfinden. Dieser Index kann als Algorithmus zum Ermitteln des HashCodes betrachtet werden.
Verwenden von Map.put (Schlüssel, Wert)
Dies findet eine geeignete Gesellschaft für diesen Wert, indem der HashCode gefunden wird und dann der Wert gespeichert wird.
Ich hoffe das hilft und das ist offen für Änderungen.
quelle
Es wird eine lange Antwort sein, etwas trinken und weiterlesen ...
Beim Hashing geht es darum, ein Schlüssel-Wert-Paar im Speicher zu speichern, das schneller gelesen und geschrieben werden kann. Es speichert Schlüssel in einem Array und Werte in einer LinkedList.
Nehmen wir an, ich möchte 4 Schlüsselwertpaare speichern -
Um die Schlüssel zu speichern, benötigen wir ein Array mit 4 Elementen. Wie ordne ich nun einen dieser 4 Schlüssel 4 Array-Indizes (0,1,2,3) zu?
Java findet also den HashCode einzelner Schlüssel und ordnet sie einem bestimmten Array-Index zu. Hashcode-Formeln sind -
Hash und Mädchen !! Ich weiß was du denkst. Ihre Faszination für dieses wilde Duett könnte dazu führen, dass Sie eine wichtige Sache verpassen.
Warum Java multipliziert es mit 31?
Wie wird dieser Hash-Code nun einem Array-Index zugeordnet?
Antwort ist ,
Hash Code % (Array length -1)
. Ist“girl”
also(3173020 % 3) = 1
in unserem Fall abgebildet . Das ist das zweite Element des Arrays.und der Wert "ahhan" wird in einer LinkedList gespeichert, die dem Array-Index 1 zugeordnet ist.
HashCollision - Wenn Sie versuchen,
hasHCode
die Schlüssel zu finden“misused”
und“horsemints”
die oben beschriebenen Formeln zu verwenden, sehen Sie, dass beide uns dasselbe geben1069518484
. Whooaa !! Lektion gelernt -Jetzt sieht die Hash-Karte aus wie -
Wenn nun ein Körper versucht, den Wert für den Schlüssel zu finden
“horsemints”
, findet Java schnell den Hashcode des Schlüssels , moduliert ihn und beginnt mit der Suche nach seinem Wert in der entsprechenden LinkedListindex 1
. Auf diese Weise müssen wir nicht alle 4 Array-Indizes durchsuchen, um den Datenzugriff zu beschleunigen.Aber warte, eine Sekunde. Es gibt 3 Werte in dieser linkedList, die dem Array-Index 1 entsprechen. Wie wird herausgefunden, welcher der Werte für die Schlüssel-Horsemints war?
Eigentlich habe ich gelogen, als ich sagte, dass HashMap nur Werte in LinkedList speichert.
Es speichert beide Schlüsselwertpaare als Karteneintrag. Map sieht also tatsächlich so aus.
Jetzt können Sie sehen, dass beim Durchlaufen der mit ArrayIndex1 entsprechenden verknüpften Liste tatsächlich der Schlüssel jedes Eintrags mit dieser verknüpften Liste mit „Horsemints“ verglichen wird. Wenn eine gefunden wird, wird nur der Wert zurückgegeben.
Hoffe du hattest Spaß beim Lesen :)
quelle
Ein Bild sagt mehr als 1000 Worte. Ich sage: Ein Code ist besser als 1000 Wörter. Hier ist der Quellcode von HashMap. Methode abrufen:
So wird klar, dass Hash verwendet wird, um den "Bucket" zu finden, und das erste Element immer in diesem Bucket überprüft wird. Wenn nicht, wird
equals
der Schlüssel verwendet, um das tatsächliche Element in der verknüpften Liste zu finden.Schauen wir uns die
put()
Methode an:Es ist etwas komplizierter, aber es wird deutlich, dass das neue Element an der Position, die anhand des Hash berechnet wurde, in die Registerkarte eingefügt wird:
i = (n - 1) & hash
Hieri
ist der Index, in den das neue Element eingefügt wird (oder es ist der "Bucket").n
ist die Größe destab
Arrays (Array von "Buckets").Zunächst wird versucht, als erstes Element in diesen "Eimer" eingefügt zu werden. Wenn bereits ein Element vorhanden ist, fügen Sie der Liste einen neuen Knoten hinzu.
quelle