HashMap und Hashset sind zwei wichtige Mitglieder des Java -Sammlungsrahmens. HashMap ist eine gemeinsame Implementierungsklasse für die Kartenschnittstelle, und Hashset ist eine gemeinsame Implementierungsklasse für die festgelegte Schnittstelle. Obwohl die von HashMap und Hashset implementierten Schnittstellenspezifikationen unterschiedlich sind, ist ihr zugrunde liegender Hash -Speichermechanismus genau der gleiche und sogar Hashset selbst verwendet HashMap, um es zu implementieren.
Tatsächlich gibt es viele Ähnlichkeiten zwischen Hashset und HashMap. Für Hashset verwendet das System den Hash -Algorithmus, um den Speicherort der Sammelelemente zu bestimmen, um sicherzustellen, dass die Sammelelemente schnell gespeichert und abgerufen werden können. Für HashMap wird der Systemschlüsselwert als Ganzes verarbeitet, und das System berechnet immer den Speicherort des Schlüsselwerts basierend auf dem Hash-Algorithmus, so dass die Schlüsselwertpaare der Karte schnell gespeichert und abgerufen werden können.
Vor der Einführung des Sammlungsspeichers sollte darauf hingewiesen werden, dass eine Sammlung jedoch behauptet, Java -Objekte zu speichern, Java -Objekte jedoch nicht in die SET -Sammlung eingebracht, sondern nur Verweise auf diese Objekte in der SET -Sammlung. Das heißt, eine Java -Sammlung ist tatsächlich eine Sammlung mehrerer Referenzvariablen, die auf das tatsächliche Java -Objekt hinweisen.
1. Grundfunktionen von HashMap
Nachdem Sie die Kommentare in der JDK -Quellcode -Hashmap.Class gelesen haben, können Sie viele HashMap -Funktionen zusammenfassen.
Mit HashMap können sowohl Schlüssel als auch Wert null sein, während Hashtable dies nicht tut.
HashMap ist Thread-Discover, während Hashtable Thread-Safe ist
Die Reihenfolge der Elemente in HashMap ist nicht immer gleich, und die Position desselben Elements kann sich auch im Laufe der Zeit ändern (der Fall der Größe)
Die zeitliche Komplexität des Durchquerens eines HashMap ist proportional zu seiner Kapazität und der Anzahl der vorhandenen Elemente. Wenn Sie die Effizienz des Durchgangs sicherstellen möchten, kann die anfängliche Kapazität nicht zu hoch eingestellt oder der Gleichgewichtsfaktor kann nicht zu niedrig eingestellt werden.
Ähnlich wie bei der vorherigen verwandten Liste wird HashMap Thread-Curse-Absicherung erzeugt, wenn der Iterator versucht, die Containerstruktur während des Iterationsprozesses zu ändern. Eine synchronisierte HashMap kann über Sammelstoffe erhalten werden. SynchronisierteMap (HashMap)
2. Hash -Tabellendatenstrukturanalyse
Die Hash -Tabelle (Hash -Tabelle, Hash -Tabelle) ist eine Datenstruktur, die auf Basis von Schlüsselwörtern direkt auf Speicherspeicherorte zugreift. Das heißt, in der Hash -Tabelle wird eine direkte Zuordnung zwischen Schlüsselwörtern und Speicheradressen festgelegt
Wie in der folgenden Abbildung gezeigt, erhält der Schlüssel eine Indexposition von Eimer durch die Hash -Funktion.
Das Erhalten von Index durch Hash -Funktion erfolgt unweigerlich in der gleichen Situation, dh Konflikt. Hier sind einige Möglichkeiten, Konflikte zu lösen:
Offene Adressierung: Die grundlegende Idee dieser Methode besteht darin, bei der Begegnung von Konflikten die N -Positionen unter der Tabelle nacheinander zu scannen und bei einer freien Ausgabe zu füllen. Der spezifische Algorithmus wird nicht mehr erklärt, das Folgende ist ein schematisches Diagramm:
Separate Verkettung: Die grundlegende Idee dieser Methode besteht darin, den Eintrag mit demselben Indexwert in einer verknüpften Liste bei Konflikten mit demselben Indexwert zu streiten. Der spezifische Algorithmus wird nicht mehr erklärt, das Folgende ist ein schematisches Diagramm:
Die Methode zur Lösung von Konflikten in HashMap in JDK besteht darin, die separate Kettenmethode zu verwenden.
3. HashMap -Quellcodeanalyse (JDK1.7)
1. Hashmap lesen und schreiben Elemente
Eintrag
Die in HashMap gespeicherten Elemente sind vom Typ Eingangstyp. Der Quellcode des Eintrags im Quellcode ist unten angegeben:
statischer Klasseneintrag <k, v> implementiert map.Entry <k, v> {endgültig k key; V Wert; Eintrag <k, v> Weiter; int Hash; Eintrag (int H, k k, v v, Eintrag <k, v> n) {value = v; Weiter = n; Key = k; Hash = H; } // Die Get and Set -Methoden des Schlüssels, der Wert werden weggelassen, Get and Set -Operationen werden in den nachfolgenden Iteratoren verwendet ... Public Final Boolean Equals (Objekt o) {if (! (Oinformof map.Entry)) return false; MAP.Entry e = (map.Entry) o; Objekt K1 = getKey (); Objekt k2 = e.getkey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {Objekt v1 = getValue (); Objekt v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2)) return true; } return false; } // hier, tun oder betreiben Sie den HashCode von Key und den HashCode von Wert, um den HashCode des Eintrags öffentlich zu erhalten. } public Final String toString () {return getKey () + "=" + getValue (); } /** * Diese Methode wird aufgerufen, wenn der Wert in einem Eintrag durch eine Aufruf von Put (k, v) für einen Schlüssel k überschrieben wird, der bereits * in der HashMap ist. * / void recordAccess (Hashmap <k, v> m) {} / ** * Diese Methode wird aufgerufen, wenn der Eintrag aus der Tabelle entfernt wird. */ void recordReMoval (HashMap <k, v> m) {}}Ein Eintrag enthält Schlüssel, Wert, Hash und einen Verweis auf den nächsten Eintrag. Es ist offensichtlich, dass dies eine einzige verknüpfte Liste ist, die die MAP.Entry -Schnittstelle implementiert.
Recordacess (Hashmap <K, V> und RecordReMoval (Hashmap <k, v>) werden in HashMap nicht implementiert. Die beiden Methoden von LinkedHasMap werden jedoch zur Implementierung des LRU -Algorithmus verwendet.
Holen Sie sich: Lesen Sie Elemente, um den entsprechenden Eintrag von HashMap zu erhalten. Das Folgende ist der Quellcode von GET:
public v Get (Objektschlüssel) {// Die Situation, in der der Schlüssel null ist, wenn (key == null) return getFornullKey (); // Eintrag basierend auf dem Schlüsseleintrag <K, v> Eintrag = getEntry (Schlüssel); NULL zurückgeben == Eintrag? NULL: Eintrag.getValue (); }GetFornullKey -Quellcode
private v getFornullkey () {if (size == 0) {return null; } // transprahergen die Konfliktkette für (Eintrag <k, v> e = table [0]; e! = Null; e = e.Next) {if (e.Key == null) return e.Value; } return null; }Der Eintritt mit einem Schlüsselnull wird in Tabelle [0] gespeichert, aber die Konfliktkette in Tabelle [0] hat nicht unbedingt einen Schlüssel als Null, sodass sie durchquert werden muss.
Erhalten Sie den Eintrag nach Schlüssel:
Final Eintrag <k, v> GetEntry (Objektschlüssel) {if (size == 0) {return null; } int Hash = (key == null)? 0: Hash (Schlüssel); // Die Indexposition in der Tabelle über Hash erhalten und dann die widersprüchliche verlinkte Liste durchqueren, um den Schlüssel für (Eintrag <k, v> e = table [indexFor (Hash, Tabelle.Length)]; e! = Null; e = e = e.Next) {Objekt k; if (e.hash == Hash && ((k = E.Key) == Key || (Schlüssel! = NULL && key.equals (k)))) return e; } return null; }Das obige ist der Prozess von Hashmap, der einen Eintrag und seinen Quellcode liest. Zeitkomplexität O (1)
Put: Schreiben Sie Elemente
Der Put -Betrieb in HashMap ist relativ kompliziert, da während des Put -Betriebs einen HashMap -Expansionsvorgang vorliegt.
Wenn ein neues Element geschrieben wird und ein Schlüssel zum Schreiben des Elements in HashMap besteht, wird der Betrieb des Wertes durchgeführt, was dem Aktualisieren entspricht. Hier ist der Quellcode Put:
public v put (k key, v value) {// Wenn die Tabelle leer ist, füllen Sie if (table == lese_table) gemäß dem Schwellenwert der Größe {inblatetable (Schwellenwert); } // Füllen Sie den Eintrag mit dem Schlüssel als NULL, wenn (key == null) putfornUllKey (Wert) zurückgeben; // Hash generieren, um die Zuordnung des Indexindex int Hash = Hash (Schlüssel) zu erhalten. int i = indexFor (Hash, Tabelle.length); // Die Konfliktkette des aktuellen Index transulieren, um festzustellen, ob es einen entsprechenden Schlüssel für (Eintrag <k, v> e = Tabelle [i]; e! = Null; e = e.Next) {Objekt k; // Wenn der entsprechende Schlüssel vorhanden ist, ersetzen Sie OldValue und geben Sie OldValue zurück, wenn (e.hash == Hash && ((k = e.Key) == Key || key.equals (k))) {v oldValue = e.value; E. value = Wert; E. recordaccess (this); kehren Sie OldValue zurück; }} // Der Schlüssel des neu geschriebenen Eintrags existiert nicht in der Konfliktkette ModCount ++; // Fügen Sie eine neue Eintragszusatzei (Hash, Schlüssel, Wert, i) ein; null zurückkehren; }AddEntry- und CreateEntry -Quellcode:
void addentry (int Hash, K -Schlüssel, V -Wert, int bucketindex) {// Bevor Sie einen neuen Eintrag einfügen, beurteilen Sie zuerst die Größe des aktuellen Hashmaps und deren Schwellenwertgröße, und ob Sie erweitern möchten, wenn ((Größe> = Schwelle) && (Null! Hash = (null! = Schlüssel)? Hash (Schlüssel): 0; bucketIndex = indexFor (Hash, Tabelle.length); } createEntry (Hash, Schlüssel, Wert, BucketIndex); } void createEntry (int Hash, K -Schlüssel, V -Wert, int bucketIndex) {Eintrag <k, v> e = table [bucketIndex]; // Kopfeinfügungsmethode, der neu geschriebene Eintrag wird in die Vorderseite des ersten Eintrags in der Konfliktkette an der aktuellen Indexposition eingefügt. Tabelle [bucketIndex] = neuer Eintrag <> (Hash, Schlüssel, Wert, e); Größe ++; }Das obige ist der Prozess des Schreibens eines Eintrags in einen HashMap und seinen Quellcode. Zeitkomplexität O (1)
Element entfernen:
Final Eintrag <k, v> remedEentryForkey (Objektschlüssel) {if (size == 0) {return null; } // Berechnen Sie den Hash -Wert gemäß dem Schlüssel und erhalten Sie den Index int Hash = (key == null)? 0: Hash (Schlüssel); int i = indexFor (Hash, Tabelle.length); // Löschen Sie die verknüpfte Liste, definieren Sie zwei Zeiger, PREVERREPENS DER Vorgängereintrag <k, v> prep = table [i]; Eintrag <k, v> e = prev; // transplaIGHT Die Konfliktkette und löschen Sie alle Schlüssel, während (e! = Null) {Eintrag <k, v> next = e.Next; Objekt k; // Wenn gefunden (e.hash == Hash && ((k = e.Key) == Key || (Schlüssel! = Null && key.equals (k)))) {modcount ++; Größe--; // Der erste Knoten zu finden ist der Knoten, der gelöscht wird, wenn (prev == e) Tabelle [i] = Weiter; sonst prev.Next = Weiter; E.RecordReMoval (dies); Rückkehr e; } prew = e; E = Weiter; } return e; }Das obige ist der Prozess von Hashmap, der einen Eintrag und seinen Quellcode löscht. Zeitkomplexität O (1)
2. Hashmap -Hashing -Prinzip (Hash -Funktion)
Die Implementierung der Hash -Funktion in HashMap erfolgt über Hash (Objekt K) und Indexfor (int H, int Länge). Schauen wir uns den folgenden Quellcode an:
endgültig int Hash (Objekt k) {int H = HashSeed; if (0! } h ^= k.hashcode (); // Diese Funktion stellt sicher, dass Hashcodes, die sich nur durch // konstante Multiplikatoren an jeder Bitposition unterscheiden, eine begrenzte // Anzahl von Kollisionen (ca. 8 bei Standardlastfaktor) haben. // Um die Wahrscheinlichkeit von Konflikten zu verringern h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }Holen Sie sich den Index -Indexquellencode:
static int indexFor (int h, int länge) {// Integer assert Integer.bitCount (Länge) == 1: "Länge muss eine Leistung von 2" ungleich Null sein "; Return H & (Länge-1); }Hashmap kartiert Schlüssel zu Indizes innerhalb des Intervalls von [0, Tabelle.Length] durch eine Hash -Funktion. Es gibt im Allgemeinen zwei Arten von Indizierungsmethoden:
Hash (Schlüssel) % Tabelle.Length, wobei die Länge eine Primzahl sein muss. Hashtable verwendet diese Implementierung in JDK.
Aus bestimmten Gründen für die Verwendung von Primzahlen finden Sie relevante Algorithmusdatennachweise, die hier nicht angegeben werden.
Hash (Schlüssel) & (Tabelle.Length - 1), wobei die Länge bis zur 2 exponentiellen Leistung ausgesetzt sein muss. HashMap in JDK verwendet diese Implementierungsmethode.
Da die Größe der Länge 2 exponentielle Zeiten beträgt, liegt Hash (Schlüssel) und (Tabelle.Length - 1) immer zwischen [0, Länge - 1]. Wenn Sie dies jedoch alleine tun, wird es ein großes Problem mit Konflikten geben, da der Wert von Hashcode in Java 32 Bit beträgt. Wenn die Kapazität von Hashmap beispielsweise bei 16, wenn er XOR -Operation durchführt, ist das hohe Bit immer verworfen, aber nach dem niedrigen Bitoperation tritt die Wahrscheinlichkeit von Konflikten auf.
Um die Wahrscheinlichkeit des Auftretens von Konflikten zu verringern, werden daher viele Bit -Operationen und ausschließliche oder Operationen im Code durchgeführt.
3.. Hashmap -Speicherzuweisungsstrategie
Element variable Kapazität und Lastfaktor
Die erforderliche Kapazitätskapazität ist ein exponentielles Vielfaches von 2 in HashMap, und die Standardkapazität beträgt 1 << 4 = 16. Es gibt auch einen Gleichgewichtsfaktor (Lastfaktor) in HashMap. Übermäßig hohe Faktoren verringern den Speicherplatz, aber die Zeit für die Suche (Suche, einschließlich Put- und Erhalten von Methoden in HashMap) wird zunehmen. Der Standardwert des Lastfaktors beträgt 0,75, was der optimale Wert ist, der durch Abwägung der zeitlichen Komplexität und Raumkomplexität angegeben ist.
statische endgültige int default_initial_capacity = 1 << 4; // aka 16 statische endgültige int maximum_capacity = 1 << 30; static Final Float default_load_factor = 0,75f;
Hashmap -Konstruktor
Der Bau von HashMap besteht darin, die Kapazität und den Anfangswert des Lastfaktors festzulegen
public hashmap (int initialCapacity, float loadfactor) {if (initialCapacity <0) neue illegalArgumentException ("illegale Anfangskapazität:" + initialCapacity); if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; if (loadFactor <= 0 || float.isnan (loadFactor)) werfen neue illegalArgumentException ("illegaler Lastfaktor:" + loadfactor); this.loadfactor = loadFactor; Schwelle = initialCapacity; init (); } Ich habe bereits gesagt, dass diese Kapazität in HashMap exponentielle Zeiten von 2 sein muss, und es gibt keine Grenze im Konstruktor. Wie kann man sicherstellen, dass der Kapazitätswert exponentielle Zeiten von 2 beträgt?
Während des Einsatzbetriebs bestimmt der Quellcode, ob es sich bei der aktuellen Hash -Tabelle um eine leere Tabelle handelt. Wenn ja, rufen Sie aufblaser an (int toze)
private void aufblasetable (int toze) {// finde eine Leistung von 2> = toze int capacity = Rounduptopowerof2 (toze); threshold = (int) math.min (Kapazität * loadfactor, maximum_capacity + 1); Tabelle = neuer Eintrag [Kapazität]; inithashseedasNeeded (Kapazität); }wobei Rounduptopower von2 die N -Leistung von 2 größer oder gleich dem gegebenen Parameter erhalten soll
private statische Int Rounduptopowerof2 (int-Nummer) {// Assert-Nummer> = 0: "Nummer muss nicht negativ sein"; Rückgabezahl> = Maximum_Capacity? Maximum_Capacity: (Nummer> 1)? Integer.HighestonBeBit ((Nummer - 1) << 1): 1; }Integer.hightestonBit (int) ist eine Operation, die das höchste Bit eines bestimmten Parameters beibehält und die verbleibenden 0 ändert. Einfach ausgedrückt wird der Parameter INT in N -Potenzen weniger als oder gleich sein maximal 2.
Wenn die Zahl N -Leistung von 2 ist, liegt das höchste Bit nach Decrement 1 am ursprünglichen zweiten Hoch und dann 1 Bit, um immer noch auf die höchste Bitposition positioniert zu werden. Wenn die Zahl nicht N -Leistung von 2 ist, ist das höchste Bit immer noch das ursprüngliche höchste Bit nach Dekrement
Kapazität erweitern:
HashMap wird beim Einsetzen von Einstellungen ein Verhalten von Größen haben. Der spezifische Quellcode lautet wie folgt:
void -Größe (int NewCapacity) {Eintrag [] oldTable = Tabelle; int oldCapacity = oldTable.length; // Die Hash -Tabelle hat ihre maximale Kapazität erreicht. zurückkehren; } Eintrag [] newtable = neuer Eintrag [NewCapacity]; // Übertragen Sie den Eintrag in den alten Table auf den Neutisch // Der Rückgabewert von InithashSeedasNeded bestimmt, ob die Hash -Werttransfer (Newtable, InithashSeedasNeed (NewCapacity)) neu berechnet werden soll. Tabelle = newtable; // Schwellenwert neu berechnen. } void Transfer (Eintrag [] newtable, boolean rehash) {int newcapacity = newtable.length; // transweep altertable für (Eintrag <k, v> e: table) {// Transweep -Konfliktkette, während (null! = E) {Eintrag <k, v> next = e.next; if (rehash) {// berechnen den Hash -Wert e.hash = null == E.Key? 0: Hash (E.Key); } int i = indexFor (e.hash, newcapacity); // das Element in den Kopf einfügen, die Header -Einfügungsmethode e.Next = newtable [i]; newtable [i] = e; E = Weiter; }}}Das obige ist der gesamte Prozess der HashMap -Speicherzuweisung. Zusammenfassend wird die aktuelle Kapazität und Schwellengröße überprüft, ob HashMap einen Eintrag eingeht, um auszuwählen, ob die Kapazität erweitert werden soll. Die Größe jeder Expansion beträgt 2 * Tabelle. Während der Expansionszeit wird festgestellt, ob der Hash -Wert auf der Grundlage von InithashSeedasNeded neu berechnet werden muss.
4. Hashmap Iterator
Iteratoren wie ValueIterator, Keyiterator, EntryInator und andere in HashMap basieren alle auf Hashiterator. Schauen wir uns den Quellcode an:
Private Abstract Class Hashiterator <E> implementiert Iterator <E> {Eintrag <k, v> Weiter; // Nächster Eintrag zur Rückgabe int erweitertModcount; // für Fast-Fail Int Index; // Stromschlitz, Tabellenindexeintrag <k, v> Strom; // aktueller Eintragshiterator () {erwartungsgemodcount = modcount; // den ersten Eintrag in der Hash -Tabelle finden, wenn (Größe> 0) {Eintrag [] t = Tabelle; while (index <t.length && (next = t [index ++]) == null); }} public Final Boolean HasNext () {return next! = null; } Endeintrag <k, v> NextEntry () {// HashMap ist nicht thread-safe und bestimmen beim Durchlaufen immer noch, ob die Tabellenstruktur geändert wird, wenn (modcount! Eintrag <k, v> e = Weiter; if (e == null) werfen neue noSuchelementException (); if ((next = e.Next) == null) {// finde den nächsten Eintrag [] t = Tabelle; while (index <t.length && (next = t [index ++]) == null); } current = e; Rückkehr e; } public void remove () {if (current == null) werfen neue illegaleStateException (); if (modcount! = erwartungsModcount) werfen neue ConcurrentModificationException (); Objekt k = Strom.Key; Strom = null; HashMap.This.RemoveEentryForKey (k); erweitertModcount = modcount; }}Die drei Iteratoren, Schlüssel, Wert und Eintrag, werden eingekapselt und werden zu drei Sammelperspektiven: Keyset, Werte und Einstieg. Diese drei Sammelperspektiven unterstützen die Operationen von HashMap entfernen, removeall und klare Operationen von HashMap und unterstützen keine Addall -Operationen.