Markieren Sie es und gleichzeitig können Sie die Methoden von Hashcode () und Equals () kombinieren. HashCode () ist nicht gleich, es muss auch anders sein, um Equals () abzuleiten;
Denn wann HashMap erhält, vergleichen Sie zuerst den HashCode und vergleiche Equals, HashCode == && Equals, beide sind wahr, daher gilt es als der gleiche Schlüssel
1. Hashmap -Übersicht:
HashMap ist eine asynchrone Implementierung der Kartenschnittstelle basierend auf der Hash -Tabelle. Diese Implementierung liefert alle optionalen Zuordnungsvorgänge und ermöglicht die Verwendung von Nullwerten und Nullschlüssel. Diese Klasse garantiert nicht die Reihenfolge der Zuordnungen, insbesondere garantiert sie nicht, dass die Bestellung anhält.
2. Die Datenstruktur von Hashmap:
In der Java -Programmiersprache gibt es zwei grundlegende Strukturen, ein Array und der andere ist ein simulierter Zeiger (Referenz). HashMap ist eigentlich eine "verknüpfte Liste Hash" -Datenstruktur, dh eine Kombination von Arrays und verknüpften Listen.
Wie aus der obigen Abbildung ersichtlich ist, ist die zugrunde liegende Schicht von HashMap eine Array -Struktur, und jedes Element im Array ist eine weitere verknüpfte Liste. Wenn eine neue Hashmap erstellt wird, wird ein Array initialisiert.
Der Quellcode lautet wie folgt:
/ ** * Die Tabelle, die bei Bedarf geändert wird. V Wert;
Es ist zu erkennen, dass Eintrag das Element im Array ist.
3.. Hashmap Access Implementierung:
1) Speicherung:
public v put (k key, v value) {// HashMap erlaubt Nullschlüssel und Nullwerte. // Wenn der Schlüssel null ist, rufen Sie die Putfornullkey -Methode an und platzieren Sie den Wert an der ersten Position des Arrays. if (key == null) return putfornullkey (Wert); int Hash = Hash (key.hashcode ()); int i = indexFor (Hash, Tabelle.Length); für (Eintrag <k, v> e = table [i]; e! = null; e = E.Next) {Objekt k; ||. Dass dies ist, gibt es noch keinen Eintrag. ModCount ++; // dem I -Index den Schlüssel und den Wert hinzufügen. Add. (Hash, Schlüssel, Wert, i); Aus dem obigen Quellcode können wir sehen, dass wir beim Einfügen von Element in HashMap den Hash -Wert zuerst basierend auf dem HashCode des Schlüssels und gemäß dem Hash -Wert die Position dieses Elements im Array (d. H. Einverlauf ) Wenn das Array ist, gibt es auch andere Elemente, die bereits an der Position gespeichert sind, sodass die Elemente an dieser Position in Form einer verknüpften Liste gespeichert werden Diejenigen sind am Ende der Kette platziert. Wenn es in dieser Position im Array kein Element gibt, legen Sie das Element direkt an dieser Position in das Array.
Die AddEntry (Hash, Schlüssel, Wert, I) platziert das Schlüsselwertpaar im I-Index der Array-Tabelle basierend auf dem berechneten Hash-Wert. AddEntry ist eine Methode für Paketzugriffsberechtigungen von HashMap. Der Code lautet wie folgt:
void addiere (int hash, k key, v -Wert, int bucketindex) {// den Eintrag am angegebenen BucketIndex -Index -Eintrag <k, v> e = Tabelle [Bucketindex]; Index und lassen Sie den neuen Einstiegspunkt in die ursprüngliche Eintragstabelle [BucketIndex] = neuer Eintrag <k, v> (Hash, Schlüssel, Wert, e); (Größe ++> = Schwelle) // Erweitern Sie die Länge des Tabellenobjekts auf doppelt so hoch wie die ursprüngliche. Größe (2 * table.Length); Wenn das System beschließt, das Schlüsselwertpaar im HashMap zu speichern, wird der Wert im Eintrag überhaupt nicht berücksichtigt und berechnet einfach den Speicherort jedes Eintrags basierend auf dem Schlüssel. Wir können den Wert in der Kartensammlung als Anhang zum Schlüssel vollständig behandeln.
Die Hash (int H) -Methode berechnet den Hash, das einmal auf dem HashCode des Schlüssels basiert. Dieser Algorithmus fügt Hochbit-Berechnungen hinzu, um Hash-Konflikte zu verhindern, wenn das niedrige Bit unverändert bleibt und sich der Hochbit ändert.
statische Int Hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); Wir können sehen, dass wir die entsprechende Position im Array basierend auf dem Hash -Wert des Schlüssels finden müssen, um ein Element in HashMap zu finden. Wie man diese Position berechnet, ist der Hash -Algorithmus. Wie bereits erwähnt, handelt es sich bei der Datenstruktur von HashMap um eine Kombination von Arrays und verknüpften Listen. Wir hoffen natürlich, dass die Elementpositionen in diesem HashMap so weit wie möglich gleichmäßig verteilt werden sollten, so dass die Anzahl der Elemente an jeder Position nur ist Wenn wir dann den Hash -Algorithmus verwenden, um ihn zu finden, wenn diese Position verwendet wird, können Sie sofort wissen, dass die Elemente in der entsprechenden Position das sind, was wir wollen, und es ist nicht erforderlich, die verknüpfte Liste mehr zu durchqueren, was die erheblich optimiert Effizienz der Abfrage.
Für ein bestimmtes Objekt, solange der HashCode () -Returnwert der gleiche ist, ist der von dem Programm berechnete Hash -Code -Wert immer gleich. Das erste, woran wir denken, ist, den Hash -Wert für die Arraylänge zu moduieren, damit die Verteilung der Elemente relativ gleichmäßig ist. Die "Modulo" -Operation verbraucht jedoch viel, und dies erfolgt in HashMap: Rufen Sie die Indexfor (int h, int Länge) auf, um zu berechnen, welcher Index das Objekt im Tabellenarray gespeichert werden soll.
Der Code der Indexfor -Methode (int h, int Länge) lautet wie folgt:
statischer Indexfor (int h, int länge) {return H & (Länge-1);Diese Methode ist sehr klug. Geschwindigkeitsbedingungen. Im HashMap -Konstruktor gibt es den folgenden Code:
int Kapazität = 1;
Dieser Code stellt sicher, dass die Kapazität von HashMap während der Initialisierung immer bei N -Leistung von 2 liegt, dh die Länge des zugrunde liegenden Arrays liegt immer bei der N -Leistung von 2.
Wenn die Länge immer mit der N-Leistung von 2 liegt, entspricht der H & (Länge-1) -Operation der Modulo Länge, dh H %Länge, aber eine höhere Effizienz als %.
Das sieht sehr einfach aus, aber es ist eigentlich ziemlich mysteriös.
Unter der Annahme, dass die Arraylängen 15 und 16 und die optimierten Hash -Codes 8 bzw. 9 betragen, ist das Ergebnis nach dem & Betrieb wie folgt:
H & (Tabelle.Length-1) Hash-Tabelle.length-1
8 & (15-1): 0100 & 1110 = 0100
9 & (15-1): 0101 & 1110 = 0100
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------ --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------
8 & (16-1): 0100 & 1111 = 0100
9 & (16-1): 0101 & 1111 = 0101
Wie aus dem obigen Beispiel hervorgeht: Wenn sie "als" mit 15-1 (1110) sind, wird das gleiche Ergebnis erzeugt, dh sie werden an derselben Position im Array positioniert, die eine Kollision erzeugt, 8, 8 und 9 wird in der gleichen Position im Array platziert, um eine verknüpfte Liste zu bilden. Gleichzeitig können wir auch feststellen, dass der Hash-Wert "mit 15-1 (1110)), wenn die Arraylänge 15 ist , 1011, 0111, 0111, 1101 kann niemals Elemente speichern, und der Raum wird ziemlich viel verschwendet. Die Wahrscheinlichkeit einer Kollision wird weiter erhöht und die langsame Abfrage -Effizienz! Wenn die Arraylänge 16 beträgt, ist der Wert an jedem Bit der durch 2N-1 erhaltenen Bit der Binärzahl 1, wenn es sich um die N-Leistung von 2 handelt, 1, wodurch das niedrige Bit der Summe des ursprünglichen Hash ausgeführt wird, wenn Es ist und auf dem niedrigen Bit, so dass das niedrige Bit des erhaltenen Summenhashs gleich ist, gepaart mit der Hash-Methode (int H) die HashCode des Schlüssel Der gleiche Hash -Wert wird an derselben Position im Array platziert, um eine verknüpfte Liste zu bilden.
Wenn die Arraylänge N -Leistungen von 2 beträgt, ist die Wahrscheinlichkeit, dass unterschiedliche Schlüssel denselben Index berechnen können Dieses Mal müssen Sie die verknüpfte Liste an einem bestimmten Ort nicht durchqueren, sodass die Abfrageeffizienz höher ist.
Gemäß dem Quellcode der obigen Put-Methode wird das Programm zunächst den Speicherort des Eintrags basierend auf dem HashCode () -Regrasswert des Schlüssel TWEI TWO -Eintrags Der HashCode () -Returnwert ist der gleiche und ihr Speicherort ist der gleiche. Wenn die Tasten dieser beiden Eintragstreue durch Equals -Vergleich zurückgeben, überschreibt der Wert des neu hinzugefügten Eintrags den Wert des ursprünglichen Eintrags in der Sammlung, der Schlüssel wird jedoch nicht überschreiben. Wenn die Schlüssel dieser beiden Einstiegsfehler durch Gleichen Vergleich falsch zurückgeben Die Beschreibung der AddEntry () -Methode.
2) Lesen Sie:
public v Get (Objektschlüssel) {if (key == null) return getFornullkey (); . Return E. value; Mit dem Hash -Algorithmus, der oben als Grundlage gespeichert ist, ist es leicht zu verstehen, dass dieser Code. Aus dem obigen Quellcode können wir sehen, dass beim Erhalten eines Elements in HashMap zuerst den HashCode des Schlüssels berechnet werden, ein Element an der entsprechenden Position im Array finden und dann das erforderliche Element in der verknüpften Liste der entsprechenden Position finden durch die gleiche Methode des Schlüssels.
3) Zusammenfassend verarbeitet HashMap den Schlüsselwert als Ganzes unten, und dieses Ganze ist ein Eingabefiel. Die zugrunde liegende Hashmap verwendet ein Eintrag [] -Array, um alle Schlüsselwertpaare zu speichern. Die gleiche Methode.
V.
Da es im HashMap immer mehr Elemente gibt, wird die Wahrscheinlichkeit eines Hash -Konflikts immer höher, da die Länge des Arrays festgelegt ist. Um die Effizienz der Abfrage zu verbessern, muss der HashMap-Anteil erweitert werden. Es wird angezeigt: Die Daten im ursprünglichen Array müssen neu berechnet und im Neuarray platziert werden, das die Größenänderung ist.
Wann wird Hashmap erweitert? Wenn die Anzahl der Elemente in der HashMap die Array -Größe *Loadfactor überschreitet, wird das Array erweitert. Das heißt, standardmäßig beträgt die Arraygröße 16. Wenn die Anzahl der Elemente in Hashmap 16*0,75 = 12 überschreitet, wird die Größe des Arrays auf 2*16 = 32 erweitert, dh doppelt so groß wie die Größe. und dann neu berechnen. .
5. Hashmap -Leistungsparameter:
HashMap enthält die folgenden Konstruktoren:
Hashmap (): Erstellen Sie eine HashMap mit einer anfänglichen Kapazität von 16 und einem Lastfaktor von 0,75.
Hashmap (int initialCapacity): Erstellen Sie eine HashMap mit anfänglicher Kapazität und einem Lastfaktor von 0,75.
HashMap (intit initialCapacity, float lastfaktor): Erstellt eine HashMap mit der angegebenen Anfangskapazität und dem angegebenen Lastfaktor.
Der grundlegende Konstruktor von HashMap, HashMap (intit initialCapacity, Float loadFactor), hat zwei Parameter, sie sind die Anfangskapazitätsnitskapazität und der Lastfaktor -Lastfaktor.
InitialCapacity: Die maximale Kapazität von HashMap, dh die Länge des zugrunde liegenden Arrays.
LOADFACTOR: Der Lastfaktor -Lastfaktor ist definiert als: die tatsächliche Anzahl der Elemente einer Hash -Tabelle (n)/die Kapazität einer Hash -Tabelle (m).
Der Lastfaktor misst den Nutzungsgrad eines Hash -Tabellenraums. Bei Hash -Tabellen unter Verwendung der verknüpften Listenmethode ist die durchschnittliche Zeit, um ein Element zu finden, O (1+A) Der Lastfaktor ist auch, wenn es klein ist, dann sind die Daten der Hash -Tabelle zu spärlich, was zu einer schwerwiegenden Raumverschwendung führt.
Bei der Implementierung von HashMap wird die maximale Kapazität von HashMap durch das Schwellenfeldfeld bestimmt:
Die Codekopie lautet wie folgt:
Schwelle = (int) (Kapazität * loadFactor);
Basierend auf der Definitionsformel des Lastfaktors ist es zu erkennen, dass der Schwellenwert die maximale Anzahl von Elementen ist, die gemäß Lastfaktor und Kapazität zulässig sind. Der Standardlastfaktor 0,75 ist eine ausgewogene Wahl für räumliche und zeitliche Effizienz. Wenn die Kapazität diese maximale Kapazität überschreitet, beträgt die HashMap -Kapazität der Größe der Größe der Größe der Kapazität:
if (Größe ++> = Schwellenwert) Größen Sie die Größe (2 * table.Length);
6. Mechanismus für fehlgeschnittene:
Wir wissen, dass Java.util.hasmap nicht mit Thread-Sicherheit ist. Wenn also andere Threads die Karte während der Verwendung des Iterators modifizieren, wird eine ConcurrentModificationException geworfen, die sogenannte fehlschließende Strategie.
Diese Strategie wird im Quellcode über das Modcount -Feld implementiert. Iterators erwartungsvoll.
Hashiterator () {erwartungsgemäß ;}} Stellen Sie während des Iterationsprozesses fest, ob der ModCount und der erwarteteModcount gleich sind.
Beachten Sie, dass ModCount als volatil deklariert wird, was die Sichtbarkeit von Modifikationen zwischen Threads sicherstellt.
Finale Eintrag <k, v> NextEntry () {if (modcount! = erwartungsModcount) neue ConcurrentModificationException (); In Hashmaps API wird angegeben:
Die Iteratoren, die durch die "Sammlungsansichtsmethode" aller Hashmap -Klassen zurückgegeben wurden: Nachdem der Iterator erstellt wurde, wird der Iterator auf andere Weise aus der Struktur geändert Werfen Sie eine ConcurrentModificificationException, wenn die Änderung vorgenommen wird. Daher wird der Iterator angesichts gleichzeitiger Modifikationen bald vollständig scheitern, ohne ein willkürliches ungewöhnliches Verhalten zu unsicheren Zeiten in der Zukunft zu riskieren.
Beachten Sie, dass das schnelle Versagen des Iterators nicht garantiert werden kann. Fast Fail Iterator wirft eine ConcurrentModificationException aus, wenn es am besten funktioniert. Daher ist es falsch, Programme zu schreiben, die auf diese Ausnahme beruhen, und der richtige Weg ist: Das schnelle Versagenverhalten des Iterators sollte nur verwendet werden, um Programmfehler zu erkennen.