Lors de l'application de HashMap dans un environnement multithread Java, il existe principalement les options suivantes : Utilisez java.util.Hashtable thread-safe comme alternative. Utilisez la méthode java.util.Collections.synchronizedMap pour envelopper l'objet HashMap existant en tant que thread. -sûr. Utilisez la classe java.util.concurrent.ConcurrentHashMap comme alternative, qui 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, entièrement basés sur les opérations CAS.
Par exemple, si l’on souhaite mettre en place un compteur public global, on peut :
Copiez le code comme suit :
compteur privateAtomicInteger =newAtomicInteger(3);
publicvoidddCounter() {
pour(;;) {
intoldValue = compteur.get();
intnewValue = oldValue +1 ;
si (counter.compareAndSet (oldValue, newValue))
retour;
}
}
Parmi eux, la méthode compareAndSet vérifie si la valeur existante du compteur est oldValue. Si tel est le cas, elle est définie sur 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 réussir à augmenter la valeur du compteur de 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. Il nous suffira simplement de les appeler à l'avenir)
En plus d'AtomicInteger, le package java.util.concurrent.atomic 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).
Mise en œuvre d'une liste chaînée sans verrouillage
Avant d'implémenter une 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 la figure 1)
Enfin, faites pointer le pointeur suivant du nœud A vers le nœud C. (Voir Figure 2)
Cependant, lors de l'opération, il est possible que d'autres threads aient directement inséré certains nœuds dans A et B (supposés être D). Si nous ne portons aucun 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 :
Copiez le code comme suit :
privatevoidlistInsert (Tête de nœud, nœud c) {
pour(;;) {
Nœud a = findInsertionPlace(head), b = a.next.get();
c.next.set(b);
si (a.next.compareAndSwap(b,c))
retour;
}
}
(Le champ suivant de la classe Node est de type AtomicReference<Node>, qui est une référence atomique pointant vers le type Node)
L'opération de recherche d'une liste chaînée sans verrouillage n'est pas différente de celle d'une liste chaînée ordinaire. 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 : insertion, suppression, recherche et 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 à le déplacer vers la nouvelle table. Pendant cette période, nous devons manipuler le pointeur trois fois :
Le prochain pointeur du point A vers D
Le prochain pointeur du point B vers C
Le prochain pointeur du point C vers E
Ces trois opérations de pointeur doivent être effectuées en même temps pour garantir l'atomicité de l'opération de déplacement. 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 maintenir 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+2i-ème. élément dans le nouveau tableau, et leur La seule différence réside dans le i+1ème 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+2ème élément).
Comme le montre la figure 5, nous organisons tous les nœuds par ordre croissant selon l'ordre inversé de la valeur de hachage (par exemple 1101->1011). Lorsque la taille du tableau est de 8, 2 et 18 sont dans un groupe ; 3, 11 et 27 sont dans un autre groupe. Au début de chaque groupe, un nœud sentinelle est inséré pour faciliter les opérations ultérieures. Afin de disposer correctement le nœud sentinelle à l'avant du groupe, nous définissons le bit le plus élevé du hachage du nœud normal (qui devient le bit le plus bas après retournement) à 1, tandis que le nœud sentinelle ne définit pas ce bit.
Lorsque le tableau est étendu à 16 (voir Figure 6), le deuxième groupe est divisé en un groupe contenant seulement 3 et un groupe contenant 11 et 27, mais l'ordre relatif entre les nœuds n'a pas changé. De cette façon, nous n'avons pas besoin de déplacer les nœuds pendant le ReHash.
Détails de mise en œuvre
Étant donné que la copie d'un tableau prend beaucoup de temps lors de l'expansion, nous adoptons ici la méthode consistant à diviser l'ensemble du tableau en blocs et à le créer paresseusement. De cette façon, lorsqu'on accède à un certain indice, il suffit de juger si le bloc où se trouve l'indice a été établi (sinon, créez-le).
De plus, la taille est définie comme la plage d'indices actuellement utilisée et sa valeur initiale est 2. Lorsque le tableau est développé, il suffit de doubler la taille ; le nombre est défini pour représenter le nombre total de nœuds actuellement inclus dans le HashMap ( sans compter les nœuds sentinelles).
Initialement, tous les éléments du tableau, à l'exception du 0ème élément, sont nuls. L'élément 0 pointe vers une liste chaînée avec un seul nœud sentinelle, représentant le point de départ de toute la chaîne. L'image complète initiale est présentée dans la figure 7, dans laquelle le vert clair représente la plage d'indices actuellement inutilisée, et les flèches en pointillés représentent des blocs qui existent logiquement mais ne sont pas réellement établis.
Opération d'initialisation de l'indice
Les éléments nuls du tableau sont considérés comme étant dans un état non initialisé. Initialiser un certain indice signifie établir son nœud sentinelle correspondant. L'initialisation est effectuée de manière récursive, c'est-à-dire que si son indice parent n'est pas initialisé, son indice parent est initialisé en premier. (L'indice parent d'un indice est l'indice obtenu en supprimant le bit binaire le plus élevé.) Le code approximatif est le suivant :
Copiez le code comme suit :
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
si (getBucket (parentIdx) ==null)
initializeBucket(parentIdx);
Nœud factice =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
Parmi eux, getBucket est une méthode encapsulée pour obtenir le contenu d'un certain indice dans le tableau, et setBucket est la même. listInsert insérera le nœud donné dans une position appropriée à partir de la position spécifiée. Si un nœud avec le même hachage existe déjà dans la liste chaînée, il renverra le nœud existant sinon, il renverra le nœud nouvellement inséré.
opération d'insertion
Tout d’abord, utilisez la taille du HashMap pour modulo le hashCode de la clé afin d’obtenir l’indice du tableau qui doit être inséré.
Déterminez ensuite si l'indice est nul, et s'il est nul, initialisez l'indice.
Construisez un nouveau nœud et insérez-le dans la position appropriée. Notez que la valeur de hachage dans le nœud doit être la valeur du hashCode d'origine après avoir retourné le bit et défini la position la plus basse sur 1.
Ajoutez 1 au compteur de numéros de nœuds. S'il y a trop de nœuds après avoir ajouté 1, il vous suffit de changer la taille en taille*2, ce qui signifie étendre le tableau (ReHash).
Rechercher une opération
Recherchez l'index du nœud à trouver dans le tableau.
Déterminez si l'indice est nul. S'il est nul, l'échec de la recherche sera renvoyé.
Entrez la liste chaînée à partir de la position correspondante et recherchez séquentiellement jusqu'à ce que le nœud à trouver soit trouvé ou dépasse la plage de ce groupe de nœuds.
opération de suppression
Recherchez l'index du nœud dans le tableau qui doit être supprimé.
Déterminez si l'indice est nul et, s'il est nul, initialisez l'indice.
Recherchez le nœud à supprimer et supprimez-le de la liste chaînée. (Notez qu'en raison de l'existence du nœud sentinelle, tout élément normal n'est référencé que par son seul nœud prédécesseur. Il n'y a aucune situation où il est référencé par le nœud prédécesseur et le pointeur dans le tableau en même temps, il y a donc pas besoin de modifier plusieurs pointeurs en même temps.)
Décrémentez le compteur du numéro de nœud de 1.