Bei der Anwendung von HashMap in einer Java-Multithread-Umgebung gibt es hauptsächlich die folgenden Optionen: Verwenden Sie alternativ die threadsichere java.util.Hashtable. Verwenden Sie die Methode java.util.Collections.synchronizedMap, um das vorhandene HashMap-Objekt als Thread zu umschließen -sicher. Verwenden Sie alternativ die Klasse java.util.concurrent.ConcurrentHashMap, die eine sehr gute Leistung bietet.
Die oben genannten Methoden verwenden alle mehr oder weniger Mutex-Sperren in den spezifischen Details der Implementierung. Mutex-Sperren verursachen Thread-Blockierungen, verringern die Betriebseffizienz und können eine Reihe von Problemen wie Deadlocks und Prioritätsumkehr verursachen.
CAS (Compare And Swap) ist eine von der zugrunde liegenden Hardware bereitgestellte Funktion, die den Vorgang der Beurteilung und Änderung eines Werts atomisieren kann.
Atomare Operationen in Java
Im Paket java.util.concurrent.atomic stellt uns Java viele praktische atomare Typen zur Verfügung, die vollständig auf CAS-Operationen basieren.
Wenn wir beispielsweise einen globalen öffentlichen Zähler implementieren möchten, können wir:
Kopieren Sie den Codecode wie folgt:
privateAtomicInteger counter =newAtomicInteger(3);
publicvoidaddCounter() {
für(;;) {
intoldValue = counter.get();
intnewValue = oldValue +1;
if(counter.compareAndSet(oldValue, newValue))
zurückkehren;
}
}
Unter anderem prüft die Methode „compareAndSet“, ob der vorhandene Wert des Zählers „oldValue“ ist. Wenn dies der Fall ist, wird der Vorgang auf den neuen Wert „newValue“ gesetzt, andernfalls wird „true“ zurückgegeben.
Wenn bei der Berechnung des neuen Zählerwerts andere Threads den Zählerwert ändern, schlägt CompareAndSwap fehl. An diesem Punkt müssen wir nur noch eine Schleife außerhalb hinzufügen und diesen Vorgang weiter versuchen, dann werden wir den Zählerwert schließlich erfolgreich um 1 erhöhen. (Tatsächlich hat AtomicInteger bereits die Methoden inkrementAndGet und dekrementAndGet für die häufig verwendeten +1/-1-Operationen definiert. Wir müssen sie in Zukunft nur noch einfach aufrufen.)
Zusätzlich zu AtomicInteger stellt das Paket java.util.concurrent.atomic auch die Typen AtomicReference und AtomicReferenceArray bereit, die atomare Referenzen bzw. atomare Referenzarrays (Arrays von Referenzen) darstellen.
Implementierung einer sperrenfreien verknüpften Liste
Bevor wir eine sperrenfreie HashMap implementieren, werfen wir zunächst einen Blick auf die relativ einfache Implementierungsmethode einer sperrenfreien verknüpften Liste.
Nehmen Sie als Beispiel die Einfügeoperation:
Zuerst müssen wir den Knoten A vor der einzufügenden Position und den Knoten B dahinter finden.
Erstellen Sie dann einen neuen Knoten C und lassen Sie seinen nächsten Zeiger auf Knoten B zeigen. (Siehe Abbildung 1)
Lassen Sie schließlich den nächsten Zeiger von Knoten A auf Knoten C zeigen. (Siehe Abbildung 2)
Während des Vorgangs ist es jedoch möglich, dass andere Threads einige Knoten direkt in A und B eingefügt haben (angenommen, es handelt sich um D). Wenn wir kein Urteil fällen, kann dies zum Verlust von Knoten führen, die von anderen Threads eingefügt wurden. (Siehe Abbildung 3) Mit der CAS-Operation können wir feststellen, ob der nächste Zeiger von Knoten A beim Zuweisen eines Werts immer noch auf B zeigt. Wenn sich der nächste Zeiger von Knoten A ändert, wiederholen Sie den gesamten Einfügevorgang. Der ungefähre Code lautet wie folgt:
Kopieren Sie den Codecode wie folgt:
privatevoidlistInsert(Knotenkopf, Knoten c) {
für(;;) {
Knoten a = findInsertionPlace(head), b = a.next.get();
c.next.set(b);
if(a.next.compareAndSwap(b,c))
zurückkehren;
}
}
(Das nächste Feld der Node-Klasse ist vom Typ AtomicReference<Node>, was eine atomare Referenz ist, die auf den Node-Typ zeigt)
Der Suchvorgang einer sperrfreien verknüpften Liste unterscheidet sich nicht von dem einer gewöhnlichen verknüpften Liste. Für den Löschvorgang ist es erforderlich, den Knoten A vor dem zu löschenden Knoten und den Knoten B dahinter zu finden und mithilfe der CAS-Operation den nächsten Zeiger von Knoten A zu überprüfen und zu aktualisieren, sodass er auf Knoten B zeigt.
Schwierigkeiten und Durchbrüche der sperrenfreien HashMap
HashMap verfügt hauptsächlich über vier Grundoperationen: Einfügen, Löschen, Suchen und ReHash. Eine typische HashMap-Implementierung verwendet ein Array und jedes Element des Arrays ist eine verknüpfte Liste von Knoten. Für diese verknüpfte Liste können wir die oben genannten Operationsmethoden verwenden, um Einfügungs-, Lösch- und Suchoperationen durchzuführen, die ReHash-Operation ist jedoch schwieriger.
Wie in Abbildung 4 dargestellt, besteht eine typische Operation während des ReHash-Prozesses darin, jeden Knoten in der alten Tabelle zu durchlaufen, seine Position in der neuen Tabelle zu berechnen und ihn dann in die neue Tabelle zu verschieben. Während dieser Zeit müssen wir den Zeiger dreimal manipulieren:
Der nächste Zeiger von Punkt A auf D
Der nächste Zeiger von Punkt B auf C
Der nächste Zeiger von Punkt C auf E
Diese drei Zeigeroperationen müssen gleichzeitig ausgeführt werden, um die Atomizität der Verschiebungsoperation sicherzustellen. Es ist jedoch nicht schwer zu erkennen, dass die CAS-Operation nur sicherstellen kann, dass der Wert einer Variablen jeweils atomar überprüft und aktualisiert wird, und nicht die Notwendigkeit erfüllen kann, drei Zeiger gleichzeitig zu überprüfen und zu aktualisieren.
Wir können also genauso gut unsere Denkweise ändern. Da das Verschieben von Knoten so schwierig ist, können wir alle Knoten jederzeit in einem geordneten Zustand halten und so das Verschieben vermeiden. In einer typischen HashMap-Implementierung bleibt die Länge des Arrays immer 2i, und der Prozess der Zuordnung des Hash-Werts zum Array-Index führt einfach eine Modulo-Operation für die Array-Länge durch (d. h. nur die letzten i Bits der Hash-Binärdatei sind vorhanden). beibehalten). Bei ReHash wird die Array-Länge auf 2i+1 verdoppelt und jeder Knoten in der j-ten Halskettenliste des alten Arrays wird entweder zum j-ten Element im neuen Array oder zum j+2i-ten verschoben Element im neuen Array und deren Der einzige Unterschied liegt im i+1-ten Bit des Hash-Werts (wenn das i+1-te Bit 0 ist, ist es immer noch das j-te Element, andernfalls ist es das j+2-te Element).
Wie in Abbildung 5 gezeigt, ordnen wir alle Knoten in aufsteigender Reihenfolge entsprechend der umgekehrten Reihenfolge des Hash-Werts an (z. B. 1101 -> 1011). Bei einer Array-Größe von 8 befinden sich 2 und 18 in einer Gruppe; 3, 11 und 27 befinden sich in einer anderen Gruppe. Am Anfang jeder Gruppe wird ein Sentinel-Knoten eingefügt, um nachfolgende Vorgänge zu erleichtern. Um den Sentinel-Knoten korrekt an der Spitze der Gruppe anzuordnen, setzen wir das höchste Bit des normalen Knoten-Hash (das nach dem Umdrehen zum niedrigsten Bit wird) auf 1, während der Sentinel-Knoten dieses Bit nicht setzt.
Wenn das Array auf 16 erweitert wird (siehe Abbildung 6), wird die zweite Gruppe in eine Gruppe mit nur 3 und eine Gruppe mit 11 und 27 aufgeteilt, die relative Reihenfolge zwischen den Knoten hat sich jedoch nicht geändert. Auf diese Weise müssen wir während ReHash keine Knoten verschieben.
Details zur Implementierung
Da das Kopieren eines Arrays während der Erweiterung viel Zeit in Anspruch nimmt, verwenden wir hier die Methode, das gesamte Array in Blöcke zu unterteilen und es langsam zu erstellen. Auf diese Weise muss beim Zugriff auf einen bestimmten Index nur beurteilt werden, ob der Block, in dem sich der Index befindet, eingerichtet wurde (wenn nicht, erstellen Sie ihn).
Darüber hinaus wird die Größe als der aktuell verwendete Indexbereich definiert und sein Anfangswert ist 2. Wenn das Array erweitert wird, muss die Größe nur verdoppelt werden, um die Gesamtzahl der derzeit in der HashMap enthaltenen Knoten darzustellen ( Sentinel-Knoten nicht mitgezählt).
Anfänglich sind alle Elemente im Array außer dem 0. Element null. Element 0 zeigt auf eine verknüpfte Liste mit nur einem Sentinel-Knoten, der den Ausgangspunkt der gesamten Kette darstellt. Das anfängliche Gesamtbild ist in Abbildung 7 dargestellt, in der das Hellgrün den derzeit ungenutzten Indexbereich darstellt und die gepunkteten Pfeile Blöcke darstellen, die logisch existieren, aber nicht tatsächlich eingerichtet sind.
Initialisieren Sie den Indexvorgang
Nullelemente im Array gelten als in einem nicht initialisierten Zustand. Das Initialisieren eines bestimmten Index bedeutet die Einrichtung seines entsprechenden Sentinel-Knotens. Die Initialisierung erfolgt rekursiv. Das heißt, wenn der übergeordnete Index nicht initialisiert ist, wird zuerst der übergeordnete Index initialisiert. (Der übergeordnete Index eines Index ist der Index, der durch Entfernen des höchsten Binärbits erhalten wird.) Der ungefähre Code lautet wie folgt:
Kopieren Sie den Codecode wie folgt:
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = BucketIdx ^ Integer.highestOneBit(bucketIdx);
if(getBucket(parentIdx) ==null)
initializeBucket(parentIdx);
Knotendummy =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
Unter diesen ist getBucket eine gekapselte Methode, um den Inhalt eines bestimmten Index im Array abzurufen, und setBucket ist dasselbe. listInsert fügt den angegebenen Knoten ab der angegebenen Position an einer geeigneten Position ein. Wenn in der verknüpften Liste bereits ein Knoten mit demselben Hash vorhanden ist, wird der vorhandene Knoten zurückgegeben.
Einfügevorgang
Verwenden Sie zunächst die Größe der HashMap, um den HashCode des Schlüssels zu modulieren und den Array-Index zu erhalten, der eingefügt werden soll.
Bestimmen Sie dann, ob der Index null ist, und initialisieren Sie den Index, wenn er null ist.
Erstellen Sie einen neuen Knoten und fügen Sie ihn an der entsprechenden Position ein. Beachten Sie, dass der Hash-Wert im Knoten der Wert des ursprünglichen HashCodes sein sollte, nachdem das Bit umgedreht und die niedrigste Position auf 1 gesetzt wurde.
Addieren Sie 1 zum Knotenanzahlzähler, wenn nach dem Hinzufügen von 1 zu viele Knoten vorhanden sind, müssen Sie nur die Größe auf Größe * 2 ändern, was bedeutet, dass das Array erweitert wird (ReHash).
Betrieb finden
Suchen Sie den Index des Knotens, der im Array gefunden werden soll.
Stellen Sie fest, ob der Index null ist. Wenn er null ist, wird ein Suchfehler zurückgegeben.
Geben Sie die verknüpfte Liste an der entsprechenden Position ein und suchen Sie nacheinander, bis der zu findende Knoten gefunden wird oder den Bereich dieser Knotengruppe überschreitet.
Löschvorgang
Suchen Sie den Index des Knotens im Array, der gelöscht werden soll.
Bestimmen Sie, ob der Index null ist, und initialisieren Sie den Index, wenn er null ist.
Suchen Sie den zu löschenden Knoten und löschen Sie ihn aus der verknüpften Liste. (Beachten Sie, dass aufgrund der Existenz des Sentinel-Knotens jedes normale Element nur von seinem einzigen Vorgängerknoten referenziert wird. Es gibt keine Situation, in der es gleichzeitig vom Vorgängerknoten und dem Zeiger im Array referenziert wird, also gibt es eine solche Es ist nicht erforderlich, mehrere Zeiger gleichzeitig zu ändern.)
Dekrementieren Sie den Knotennummernzähler um 1.