Detaillierte Erläuterung des Prinzips und der Implementierung der sperrfreien Java-Hashmap

Beim Anwenden von HashMap in einer Java-Multithread-Umgebung gibt es hauptsächlich die folgenden Optionen: Verwenden Sie alternativ die threadsichere Methode java.util.Hashtable. Verwenden Sie die Methode java.util.Collections.synchronizedMap, um die vorhandene HashMap zu umschließen Objekt als Thread-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.

Atomoperationen in Java

Im Paket java.util.concurrent.atomic stellt uns Java viele praktische atomare Typen zur Verfügung, die im Grunde vollständig auf CAS-Operationen basieren.

Wenn wir beispielsweise einen globalen öffentlichen Zähler implementieren möchten, können wir:

privateAtomicInteger counter =newAtomicInteger(3); 

publicvoidaddCounter() { 

    for(;;) { 

        intoldValue = counter.get(); 

        intnewValue = oldValue +1; 

        if(counter.compareAndSet(oldValue, newValue)) 

            return; 

    } 

}

Unter anderem prüft die Methode „compareAndSet“, ob der vorhandene Wert des Zählers „oldValue“ ist und ob Legen Sie ihn also fest. Wenn es sich um den neuen Wert newValue handelt, ist die Operation erfolgreich und es wird „true“ zurückgegeben. Andernfalls schlägt die Operation fehl und es wird „false“ 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 incrementAndGet und decrementAndGet für häufig verwendete +1/-1-Operationen definiert. Wir müssen sie in Zukunft nur noch einfach aufrufen.)

Zusätzlich zu AtomicInteger auch java.util.concurrent Das .atomic-Paket bietet außerdem die Einführung der Typen AtomicReference und AtomicReferenceArray, die atomare Referenzen bzw. atomare Referenzarrays (Arrays von Referenzen) darstellen.

Implementierung einer sperrenfreien verknüpften Liste
Bevor wir die sperrenfreie HashMap implementieren, werfen wir zunächst einen Blick auf die relativ einfache Implementierungsmethode einer sperrenfreien verknüpften Liste.

Nehmen Sie den Einfügevorgang als Beispiel:

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)

Aber mitten im Vorgang ist es möglich, dass andere Threads direkt einige Knoten in A und B (angenommen D) eingefügt haben, wenn Wir führen keine Beurteilung durch, da dies zum Verlust von Knoten führen kann, 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:

privatevoidlistInsert(Node head, Node c) { 

 
    for(;;) { 

 
        Node a = findInsertionPlace(head), b = a.next.get(); 

 
        c.next.set(b); 

        if(a.next.compareAndSwap(b,c)) 

            return; 
    } 
}

(Das nächste Feld der Node-Klasse ist vom Typ AtomicReference, was eine atomare Referenz ist, die auf den Node-Typ zeigt)

Das Suchvorgang der sperrenfreien verknüpften Liste und der gewöhnlichen verknüpften Liste Es gibt keinen Unterschied. 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 bei sperrenfreiem 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 dann hinzuzufügen it In neue Tabelle verschieben. Während dieser Zeit müssen wir Zeiger dreimal manipulieren:

nächster Zeiger von Punkt A auf D
nächster Zeiger von Punkt B auf C
nächster Zeiger von Punkt C auf E
und diese drei Zeigeroperationen Muss Gleichzeitig abgeschlossen werden, kann die Atomizität des Verschiebevorgangs gewährleistet werden. 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.

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).

如图5，我们将所有节点按照Hash值的翻转位序（如1101->1011）由小到大排列。当数组大小为8时，2、18在一个组内；3、 11、27在另一个组内。每组的开始，插入一个哨兵节点，以方便后续操作。为了使哨兵节点正确排在组的最前方，我们将正常节点Hash的最高位（翻转后变为最低位）置为1，而哨兵节点不设置这一位。

当数组扩容至16时（见图6），第二组分裂为一个只含3的组和一个含有11、27的组，但节点之间的相对顺序并未改变。这样在ReHash时，我们就不需要移动节点了。

实现细节

由于扩容时数组的复制会占用大量的时间，这里我们采用了将整个数组分块，懒惰建立的方法。这样，当访问到某下标时，仅需判断此下标所在块是否已建立完毕（如果没有则建立）。

另外定义size为当前已使用的下标范围，其初始值为2，数组扩容时仅需将size加倍即可；定义count代表目前HashMap中包含的总节点个数（不算哨兵节点）。

初始时，数组中除第0项外，所有项都为null。第0项指向一个仅有一个哨兵节点的链表，代表整条链的起点。初始时全貌见图7，其中浅绿色代表当前未使用的下标范围，虚线箭头代表逻辑上存在，但实际未建立的块。

初始化下标操作

数组中为null的项都认为处于未初始化状态，初始化某个下标即代表建立其对应的哨兵节点。初始化是递归进行的，即若其父下标未初始化，则先初始化其父下标。（一个下标的父下标是其移除最高二进制位后得到的下标）大致代码如下：

privatevoidinitializeBucket(intbucketIdx) { 

    intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx); 

    if(getBucket(parentIdx) ==null) 

        initializeBucket(parentIdx); 

    Node dummy =newNode(); 

    dummy.hash = Integer.reverse(bucketIdx); 

    dummy.next =newAtomicReference<>(); 

    setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy)); 

 
}

其中getBucket即封装过的获取数组某下标内容的方法，setBucket同理。listInsert将从指定位置开始查找适合插入的位置插入给定的节点，若链表中已存在hash相同的节点则返回那个已存在的节点；否则返回新插入的节点。

插入操作

首先用HashMap的size对键的hashCode取模，得到应插入的数组下标。
然后判断该下标处是否为null，如果为null则初始化此下标。
构造一个新的节点，并插入到适当位置，注意节点中的hash值应为原hashCode经过位翻转并将最低位置1之后的值。
将节点个数计数器加1，若加1后节点过多，则仅需将size改为size*2，代表对数组扩容（ReHash）。

查找操作

找出待查找节点在数组中的下标。
判断该下标处是否为null，如果为null则返回查找失败。
从相应位置进入链表，顺次寻找，直至找出待查找节点或超出本组节点范围。

删除操作

找出应删除节点在数组中的下标。
判断该下标处是否为null，如果为null则初始化此下标。
找到待删除节点，并从链表中删除。（注意由于哨兵节点的存在，任何正常元素只被其唯一的前驱节点所引用，不存在被前驱节点与数组中指针同时引用的情况，从而不会出现需要同时修改多个指针的情况）
将节点个数计数器减1。

更多Detaillierte Erläuterung des Prinzips und der Implementierung der sperrfreien Java-Hashmap相关文章请关注PHP中文网！