Schauen wir uns zunächst eine Interviewfrage an:
Eine Reihe von Schlüsselwertpaaren, die in einem HashMap gespeichert sind, wobei der Schlüssel ein bestimmter Typ ist, den wir anpassen. Nachdem wir HashMap eingegeben haben, ändern wir die Attribute eines Schlüssels extern und verwenden diesen Schlüssel, um Elemente aus dem HashMap zu entfernen. Was wird Hashmap zu diesem Zeitpunkt zurückkehren?
In dem Artikel wurden Beispielcode und Antworten angegeben, es wird jedoch keine Erklärung zum Prinzip von HashMap gegeben.
1. Merkmale
Wir können eine Klasse als HashMap -Schlüssel verwenden, aber was sind die Einschränkungen für diese Klassen? Schauen wir uns den folgenden Code an:
public class Person {privater Zeichenfolge Name; public person (String name) {this.name = name; }} Map <Person, String> testmap = new HashMap <> (); testMap.put (neue Person ("Hallo"), "Welt"); testMap.get (neue Person ("Hallo"); // ---> nullIch wollte ursprünglich den Wert der Personklasse mit gleichen Feldwerten erhalten, aber das Ergebnis war Null. Jeder, der ein wenig Kenntnis von Hashmap hat, kann sehen, dass die Personklasse keine Überschreibungspunkt -Hashcode -Methode hat, was zu ihrer Erbe des Objekthashcode führt (Rückgabe ist seine Speicheradresse). Dies ist auch der Grund, warum invariante Klassen wie String (oder Ganzzahl usw.) häufig als Schlüssel von HashMap verwendet werden. Wie nutzt HashMap HashCode, um den Schlüssel schnell zu indizieren?
2. Prinzip
Schauen wir uns zunächst eine einfache HashMap -Implementierungslösung in "Thinking in Java" an:
//: Container/SimpleHasMap.java // Eine Demonstration Hashed Map.import Java.util. // Sie können keine physische Array von Generika haben, aber Sie können auf eine aufgerichtet sind: @SuppressWarnings ("Deaktiviert") LinkedList <MapEntry <k, v >> [] buckets = new LinkedList [Größe]; public v put (k key, v value) {v oldValue = null; int index = math.abs (key.hashCode ()) % Größe; if (buckets [index] == null) Buckets [index] = new LinkedList <mapEntry <k, v >> (); LinkedList <mapEntry <k, v >> bucket = buckets [index]; MapEntry <K, v> pair = new mapEntry <k, v> (Schlüssel, Wert); boolean found = false; ListIterator <mapEntry <k, v >> it = bucket.listiterator (); while (it.hasnext ()) {mapEntry <k, v> ipair = it.next (); if (ipair.getKey (). Equals (Schlüssel)) {oldValue = ipair.getValue (); it.set (pair); // Old mit neuer Found = true ersetzen; brechen; }} if (! gefunden) Buckets [Index] .Add (Paar); kehren Sie OldValue zurück; } public v get (Objektschlüssel) {int index = math.abs (key.hashCode ()) % Größe; if (Buckets [index] == null) return null; für (MapEntry <k, v> ipair: buckets [index]) if (ipair.getKey (). Equals (Schlüssel)) return ipair.getValue (); null zurückkehren; } public set <map.Entry <k, v >> Eintrag () {set <map.Entry <k, v >> set = new Hashset <map.Entery <k, v >> (); für (linkedList <mapEntry <k, v >> Bucket: Eimer) {if (bucket == null) Fortsetzung; für (MapEntry <k, v> mpair: bucket) set.add (mpair); } return set; } public static void main (String [] args) {simpleHasMaMap <String, String> m = new SimpleHashMap <String, String> (); M.putall (Länder.Capitals (25)); System.out.println (M); System.out.println (M.Get ("Eritrea")); System.out.println (M.EntrySet ()); }}SimpleHasMap erstellt einen Hash -Tisch, um Schlüssel zu speichern. Die Hash -Funktion ist die Modul -Operation Math.abs (KEY.HashCode ()) %Größe, und der Hash -Konflikt wird unter Verwendung der verknüpften Listenmethode gelöst. Jeder Buckets -Steckplatz speichert die Karte.
Das Implementierungsprinzip von JDKs HashMap ähnelt diesem, das die Hash -Tabelle der Kettenadresse verwendet, um MAP zu speichern.
/*** Die Tabelle, die bei Bedarf geändert wurde. Die Länge muss immer eine Kraft von zwei sein. */transienter Eintrag <k, v> [] table = (Eintrag <k, v> []) leere_table; statische Klasseneintrag <k, v> map.Entry <k, v> {endgültig k -Schlüssel; V Wert; Eintrag <k, v> Weiter; int Hash; …}Der Index von MAP.Entry wird erhalten, indem der HashCode des Schlüssels gehabt wird. Wenn Sie den dem Schlüssel entsprechenden Wert erhalten möchten, berechnen Sie seinen Index für den Schlüssel und nehmen Sie dann die Karte heraus. Einzelheiten finden Sie im Code:
public v get (Objektschlüssel) {if (key == null) return getFornullKey (); Eintrag <k, v> Eintrag = GetEntry (Schlüssel); NULL zurückgeben == Eintrag? NULL: Eintrag.getValue ();} Endeintrag <k, v> GetEntry (Objektschlüssel) {if (size == 0) {return null; } int Hash = (key == null)? 0: Hash (Schlüssel); für (Eintrag <k, v> e = table [indexFor (Hash, Tabelle.Length)]; e! = null; e = E.Next) {Objekt k; if (e.hash == Hash && ((k = E.Key) == Key || (Schlüssel! = NULL && key.equals (k)))) return e; } return null;}Es ist zu sehen, dass HashCode direkt die Effizienz der Hash -Funktion von Hashmap beeinflusst - ein guter HashCode wird Hash -Konflikte erheblich reduzieren und die Abfrageleistung verbessern. Gleichzeitig erläutert dies auch die beiden zu Beginn aufgeworfenen Fragen: Wenn eine benutzerdefinierte Klasse HashMap -Schlüssel macht, sollte die HashCode -Berechnung alle Felder des Konstruktors abdecken, andernfalls ist es möglich, Null zu erhalten.