Explication détaillée du principe et de la mise en œuvre du hashmap sans verrouillage Java

Lors de l'application de HashMap dans un environnement multithread Java, il existe principalement les options suivantes : Utilisez le java.util.Hashtable thread-safe comme alternative. Utilisez la méthode java.util.Collections.synchronizedMap pour envelopper le HashMap existant. objet comme thread-safe. Utilisez la classe java.util.concurrent.ConcurrentHashMap comme alternative, elle offre de très bonnes performances.
Les méthodes ci-dessus utilisent toutes des verrous mutex plus ou moins dans les détails spécifiques de l'implémentation. Les verrous mutex provoqueront un blocage des threads, réduiront l'efficacité du fonctionnement et peuvent provoquer une série de problèmes tels qu'un blocage et un changement de priorité.

CAS (Compare And Swap) est une fonction fournie par le matériel sous-jacent, qui peut atomiser l'opération de jugement et de modification d'une valeur.

Opérations atomiques en Java

Dans le package java.util.concurrent.atomic, Java nous fournit de nombreux types atomiques pratiques, qui sont entièrement basés sur les opérations CAS en bas.

Par exemple, si nous voulons implémenter un compteur public global, nous pouvons :

privateAtomicInteger counter =newAtomicInteger(3); 

publicvoidaddCounter() { 

    for(;;) { 

        intoldValue = counter.get(); 

        intnewValue = oldValue +1; 

        if(counter.compareAndSet(oldValue, newValue)) 

            return; 

    } 

}

Parmi eux, la méthode compareAndSet vérifiera si la valeur existante du compteur est oldValue, et si alors, définissez-le S'il s'agit de la nouvelle valeur newValue, l'opération réussit et true est renvoyée, sinon l'opération échoue et false est renvoyée ;

Lors du calcul de la nouvelle valeur du compteur, si d'autres threads modifient la valeur du compteur, compareAndSwap échouera. À ce stade, il nous suffit d'ajouter une couche de boucle à l'extérieur et de continuer à essayer ce processus, puis nous finirons par définir avec succès la valeur du compteur sur 1. (En fait, AtomicInteger a déjà défini les méthodes incrémentAndGet et decrementAndGet pour les opérations 1/-1 couramment utilisées. Nous n'aurons qu'à simplement l'appeler à l'avenir)

En plus d'AtomicInteger, le java.util.concurrent. Le package atomique fournit également les types AtomicReference et AtomicReferenceArray qui représentent respectivement des références atomiques et des tableaux de références atomiques (tableaux de références).

Implémentation d'une liste chaînée sans verrouillage
Avant d'implémenter HashMap sans verrouillage, examinons d'abord la méthode d'implémentation relativement simple d'une liste chaînée sans verrouillage.

Prenons l'exemple de l'opération d'insertion :

Nous devons d'abord trouver le nœud A devant la position à insérer et le nœud B derrière.
Créez ensuite un nouveau nœud C et faites pointer son prochain pointeur vers le nœud B. (Voir Figure 1)
Enfin, faites pointer le pointeur suivant du nœud A vers le nœud C. (Voir Figure 2)

Mais au milieu de l'opération, il est possible que d'autres threads aient directement inséré certains nœuds en A et B (supposés être D), si on ne fait rien de jugement, cela peut entraîner la perte de nœuds insérés par d'autres threads. (Voir Figure 3) Nous pouvons utiliser l'opération CAS pour déterminer si le pointeur suivant du nœud A pointe toujours vers B lors de l'attribution d'une valeur. Si le pointeur suivant du nœud A change, réessayez toute l'opération d'insertion. Le code approximatif est le suivant :

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; 
    } 
}

(Le champ suivant de la classe Node est de type AtomicReference, qui est une référence atomique pointant vers le type Node)

Le opération de recherche de la liste chaînée sans verrouillage et de la liste chaînée ordinaire Il n'y a aucune différence. L'opération de suppression nécessite de trouver le nœud A devant le nœud à supprimer et le nœud B derrière lui, et d'utiliser l'opération CAS pour vérifier et mettre à jour le pointeur suivant du nœud A afin qu'il pointe vers le nœud B.

Difficultés et avancées du HashMap sans verrouillage
HashMap comporte principalement quatre opérations de base : l'insertion, la suppression, la recherche et le ReHash. Une implémentation HashMap typique utilise un tableau et chaque élément du tableau est une liste chaînée de nœuds. Pour cette liste chaînée, nous pouvons utiliser les méthodes d'opération mentionnées ci-dessus pour effectuer des opérations d'insertion, de suppression et de recherche, mais l'opération ReHash est plus difficile.

Comme le montre la figure 4, pendant le processus ReHash, une opération typique consiste à parcourir chaque nœud de l'ancienne table, à calculer sa position dans la nouvelle table, puis à ajouter il Déplacer vers une nouvelle table. Pendant cette période, nous devons manipuler les pointeurs trois fois :

le prochain pointeur de A vers D
le prochain pointeur de B vers C
le prochain pointeur de C vers E
et ces trois opérations de pointeur Doit être terminé en même temps, l'atomicité de l'opération de déplacement peut être garantie. Mais il n'est pas difficile de voir que l'opération CAS ne peut garantir que la valeur d'une variable est vérifiée et mise à jour atomiquement à la fois, et ne peut pas répondre au besoin de vérifier et de mettre à jour trois pointeurs en même temps.

Autant changer notre façon de penser. Puisque l'opération de déplacement de nœuds est si difficile, nous pouvons garder tous les nœuds dans un état ordonné à tout moment, évitant ainsi l'opération de déplacement. Dans une implémentation HashMap typique, la longueur du tableau reste toujours 2i, et le processus de mappage de la valeur de hachage à l'indice du tableau effectue simplement une opération modulo sur la longueur du tableau (c'est-à-dire que seuls les i derniers bits du binaire de hachage sont retenu). Lors de ReHash, la longueur du tableau est doublée à 2i 1, et chaque nœud de la j-ème liste de colliers de l'ancien tableau est soit déplacé vers le j-ème élément du nouveau tableau, soit déplacé vers le j-ème élément 2i dans le nouveau tableau, et la seule différence entre eux est La différence réside dans le i 1er bit de la valeur de hachage (si le i 1ème bit est 0, c'est toujours le jème élément, sinon c'est le jème 2i élément).

如图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。

更多Explication détaillée du principe et de la mise en œuvre du hashmap sans verrouillage Java相关文章请关注PHP中文网！