Nous savons qu'une table de hachage est une structure de données très efficace, et une excellente conception de la fonction de hachage peut rendre les opérations d'addition, de suppression, de modification et de recherche sur elle atteint le niveau O (1). Java nous fournit une structure de hachage prêt à l'emploi, c'est-à-dire la classe HashMap. Dans l'article précédent, j'ai présenté la classe HashMap et je savais que toutes ses méthodes n'étaient pas synchronisées, donc elle n'est pas sûre dans un environnement multi-thread. À cette fin, Java nous fournit une autre classe de hachage, qui est très simple et grossière dans la gestion de la synchronisation multi-thread, c'est-à-dire pour verrouiller toutes ses méthodes en utilisant le mot-clé synchronisé basé sur le hashmap. Bien que cette méthode soit simple, elle conduit à un problème, c'est-à-dire qu'un seul thread peut faire fonctionner la table de hachage en même temps. Même si ces threads ne sont que des opérations de lecture, elles doivent être en file d'attente, ce qui affecte considérablement les performances dans des environnements multi-thread très compétitifs. Le concurrenthashmap introduit dans cet article est de résoudre ce problème. Il utilise des verrous segmentés pour grainz fin les serrures, afin que plusieurs threads puissent faire fonctionner la table de hachage en même temps, ce qui améliore considérablement les performances. La figure suivante est un diagramme schématique de sa structure interne.
1. Quelles variables membre ConcurrenthashMap a-t-elle?
// Capacité d'initialisation par défaut static final int default_initial_capacity = 16; // facteur de charge par défaut static final float default_load_factor = 0.75f; // le niveau de concurrence par défaut static final intrafault_concurrency_level = 16; // définir la capacité maximale statique final final_capacity = 1 << 30; // nombre minimum de segments static static static final ininte 2; // Nombre maximum de verrouillage de segments static final int max_segments = 1 << 16; // Nombre de réseaux avant de verrouiller static final int reatries_before_lock = 2; // Valeur de masque du segment verrouillage final int segment Mask; // Array de verrouillage du segment segment final <k, v> [] segments;
Avant de lire cet article, je crois que les lecteurs ne peuvent pas comprendre la signification et la fonction spécifiques de ces variables membres, mais les lecteurs sont invités à lire patiemment. Le rôle de ces variables membre sera introduit un par un dans les scénarios spécifiques plus tard. Ici, les lecteurs n'ont qu'à laisser un regard familier sur ces variables membres. Cependant, il y a encore des variables que nous devons connaître maintenant. Par exemple, le réseau de segments représente l'ensemble des verrous du segment, le niveau de concurrence représente le nombre de verrous de segment (ce qui signifie également le nombre de threads peut fonctionner en même temps), la capacité d'initialisation représente la capacité de l'ensemble du conteneur et le facteur de charge représente le niveau de la façon dont les éléments du conteneur peuvent atteindre.
2. Quelle est la structure interne du verrouillage du segment?
// Segment Lock Segment de classe finale statique <K, V> étend ReentrantLock implémente Serializable {// Numéro de spin maximum statique final int max_scan_retrie = runtime.getRuntime (). DisponibleProcessors ()> 1? 64: 1; // Tableau de la table transitoire Hashentry volatile <k, v> [] Tableau; // Nombre total d'éléments transitoires Int Count; // Nombre de modifications transitoires int modCount; // Seuil d'élément Seuil transitoire Int; // Facteur de charge Final Float LoadFactor; // omettez le contenu suivant ...}Le segment est une classe intérieure statique de concurrenthashmap, vous pouvez voir qu'il hérite de Reentrantlock, donc c'est essentiellement une serrure. Il détient un tableau de hachentrie (table de hachage) en interne et garantit que toutes les méthodes d'ajout, de supprimer, de modifier et de rechercher le tableau sont en sécurité. La mise en œuvre spécifique sera discutée plus tard. Toutes les opérations sur l'ajout, la suppression, la modification et la vérification de ConcurrentHashMap peuvent être confiées au segment, de sorte que concurrenthashmap peut s'assurer qu'il est sûr dans un environnement multi-thread. De plus, comme différents segments sont des serrures différentes, les multitheads peuvent utiliser différents segments en même temps, ce qui signifie que les multithreads peuvent fonctionner en même temps concurrenthashmap, ce qui peut éviter les défauts de hashtable et améliorer considérablement les performances.
3. Qu'est-ce que concurrenthashmap initialisé?
// Core Constructor @SuppressWarnings ("Unchecked") public concurrenthashmap (int initialCapacity, float LoadFactor, int concurrencyLevel) {if (! (LoadFactor> 0) || InitialCapacity <0 || concurrencylevel <= 0) {lancez new illégalargumentException (); } // Assurez-vous que le niveau de concurrence n'est pas supérieur à la limite if (concurrencylevel> max_segments) {concurrencyLevel = max_segments; } int sshift = 0; int ssize = 1; // Assurez-vous que SSIZE est une puissance de 2, et est le nombre le plus proche supérieur ou égal au niveau de concurrence tandis que (ssize <concurrencyLevel) {++ sshift; ssize << = 1; } // Calculez la valeur de décalage du verrouillage du segment this.segmentshift = 32 - sshift; // Calculez la valeur du masque du verrouillage du segment ce.SegmentMask = SSIZE - 1; // La capacité initiale totale ne peut pas être supérieure à la valeur limite if (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Obtenez la capacité initiale de chaque verrouillage de segment int c = initialCapacity / ssize; // La somme de la capacité de verrouillage segmentée n'est pas inférieure à la capacité totale initiale if (c * ssize <initialCapacity) {++ c; } int cap = min_segment_table_capacity; // Assurez-vous que le capuchon est une puissance de 2, et est le nombre le plus proche supérieur ou égal à C tandis que (cap <c) {Cap << = 1; } // Créer un nouveau segment de modèle d'objet de segment <k, v> s0 = nouveau segment <k, v> (loadfactor, (int) (cap * loadfactor), (hashentry <k, v> []) new hashentry [cap]); // Créez un nouveau tableau de verrouillage de segment du segment de taille spécifié <k, v> [] ss = (segment <k, v> []) nouveau segment [ssize]; // Utiliser dangereux pour attribuer le 0ème élément du tableau dangetre.putOrderEdObject (SS, SBase, S0); this.segments = ss;}ConcurrentHashMap a plusieurs constructeurs, mais ce qui est affiché ci-dessus est son constructeur principal, et d'autres constructeurs complètent l'initialisation en l'appelant. Le constructeur central doit passer en trois paramètres, à savoir la capacité initiale, le facteur de chargement et le niveau de concurrence. Lors de l'introduction des variables membre plus tôt, nous pouvons savoir que la capacité initiale par défaut est de 16, le facteur de chargement est de 0,75F et que le niveau de concurrence est 16. Maintenant, nous voyons le code du constructeur central. Tout d'abord, nous calculons la SSIZE à travers le niveau de la concurrence entrante. SSIZE est la longueur du tableau de segment. Il doit être garanti d'être une puissance de 2. De cette manière, l'indice du segment verrouillé dans le tableau peut être calculé par Hash & ssize-1. Étant donné que le niveau de la concurrence entrant ne peut être garanti comme une puissance de 2, il ne peut pas être utilisé directement comme longueur du tableau du segment. Par conséquent, nous devons trouver une puissance de 2 le plus proche du niveau de concurrence et l'utiliser comme longueur du tableau. Si la concurrencyLevel = 15 est réalisée maintenant, le code ci-dessus peut calculer SSIZE = 16 et SShift = 4. Ensuite, vous pouvez immédiatement calculer segmentshift = 16 et segmentMask = 15. Notez que segmentshift ici est la valeur de décalage du verrouillage du segment, et le masque de segment est la valeur du masque du verrouillage du segment. Ces deux valeurs sont utilisées pour calculer l'indice de verrouillage du segment dans le tableau, dont nous parlerons ci-dessous. Après avoir calculé le nombre de verrous du segment SSIZE, la capacité de chaque verrouillage de segment peut être calculée en fonction de la capacité totale entrante et de sa valeur C = InitialCapacity / SSize. La capacité du verrouillage du segment est la longueur du réseau de hachat, et elle doit également être garantie d'être une puissance de 2. La valeur de C calculée ci-dessus ne peut pas garantir cela, donc C ne peut pas être utilisé directement comme la longueur du réseau de hachat. Vous devez trouver une autre puissance de 2 les plus proches de C, attribuer cette valeur au plafond, puis utiliser le capuchon comme longueur du tableau de hachentrie. Maintenant que nous avons SSIZE et CAP, nous pouvons créer un nouveau segment de tableau de verrouillage de segment [] et un hashentry de tableau d'éléments []. Notez que contrairement à JDK1.6, seul le tableau de segment a été créé dans JDK1.7 et il n'a pas été initialisé. Le fonctionnement de l'initialisation du segment a été laissé à l'opération d'insertion.
4. Comment localiser les verrous et localiser les éléments?
// Obtenez des verrous du segment basés sur le code de hachage @SuppressWarnings ("Unchecked") Segment privé <k, v> segmentforhash (int h) {long u = (((h >>> segmentshift) & segmentMask) << sshift) + sbase; return (segment <k, v>) unsetafe.getObjectVolatile (segments, u);} // obtenez un élément basé sur le code de hachage @SuppressWarnings ("Unchecked") Final statique <k, v> hashentry <k, v> entryforhash (segment <k, v> seg, int h) {hashentry <k, v> [] onglet; return (seg == null || (tab = seg.Table) == null)? null: (Hashentry <k, v>) unsetafe.getObjectVolatile (tab, ((long) ((tab.length - 1) & h)) << tshift) + tbase);} Dans JDK1.7, dangereuse est utilisée pour obtenir des éléments de tableau, voici quelques codes supplémentaires pour calculer les décalages des éléments de tableau que JDK1.6. Nous ne prêterons pas attention à ces codes pour le moment. Maintenant, nous avons seulement besoin de connaître les deux points suivants:
un. Calculez l'indice du segment verrouillé dans le tableau via le code de hachage: (h >>> segmentshift) & segmentMask.
né Calculez l'indice d'éléments dans le tableau par code de hachage: (tab.length - 1) & h.
Supposons maintenant que les deux paramètres transmis au constructeur sont InitialCapacity = 128, concurrencyLevel = 16. Selon le calcul, nous pouvons obtenir SSIZE = 16, SSHIFT = 4, segmentshift = 28, segmentMask = 15. De même, la longueur du tableau de hachentrie dans chaque verrouillage du segment est calculée à 8, donc tab.length-1 = 7. Sur la base de ces valeurs, nous expliquons comment localiser les verrous et les éléments du segment en fonction du même code de hachage via la figure ci-dessous.
On peut voir que le verrouillage du segment et le positionnement de l'élément sont déterminés par le code de hachage de l'élément. Le verrouillage du segment de positionnement est la valeur élevée du code de hachage (à partir de 32 bits), et l'élément de positionnement est la faible valeur du code de hachage. Maintenant, il y a une question. Ils commencent de l'extrémité gauche du 32 bits et de l'extrémité droite du 32 bits. Y aura-t-il des conflits à un moment donné? Nous pouvons trouver maximum_capacity = 1 << 30, max_segments = 1 << 16 dans la variable membre, ce qui signifie que le nombre total de bits utilisés pour le positionnement des verrous du segment et les éléments de positionnement ne dépasse donc pas 30, et le nombre de bits utilisés pour le positionnement des verrous du segment ne dépasse pas 16, il n'y a donc pas au moins 2 bits, donc il n'y aura pas de conflit.
5. Comment trouver des éléments spécifiquement?
// Get ValuePublic v get (clé d'objet) {segment <k, v> s; Hashentry <k, v> [] onglet; // Calculez le code de hachage à l'aide de la fonction de hachage int h = hash (clé); // Calculez l'index du verrouillage du segment en fonction du code de hachage long u = (((h >>> segmentshift) & segmentMask) << sshift) + sbase; // obtient le verrouillage du segment et la table de hachage correspondante if ((s = (segment <k, v>) unsetafe.getObjectVolatile (segments, u))! = Null && (tab = s.Table)! = Null) {// Obtenez le nœud d'en-tête de la liste liée selon le code hash, puis la liste liée pour (hashenting <k, v> e = e = (Hashentry <k, v>) unset. // Suivez la valeur de l'élément correspondant en fonction de la clé et du hachage et renvoyez la valeur if ((k = e.key) == key || (e.hash == h && key.equals (k))) {return e.Value; }}} retourner null;}Dans JDK1.6, la méthode GET de verrouillage des segments accède aux éléments du tableau via les indices, tandis que dans JDK1.7, les éléments du tableau sont lus par la méthode GetObjectVolatile de UnsAve. Pourquoi faire ça? Nous savons que bien que la référence du tableau de hachentrie maintenue par l'objet segment soit de type volatile, les références d'élément dans le tableau ne sont pas de type volatile, donc les modifications multithreadistes des éléments du tableau sont dangereuses et peuvent lire des objets qui n'ont pas encore été construits dans le tableau. Dans JDK1.6, la deuxième lecture de verrouillage est garantie pour être sûre, et dans JDK1.7, la méthode GetObjectVolatile de la lecture est également pour l'assurer. Les éléments de tableau de lecture utilisant la méthode GetObjectVolatile nécessitent d'abord d'obtenir le décalage de l'élément dans le tableau. Ici, selon le code de hachage, le décalage du verrouillage du segment dans le tableau est U, puis le décalage U est utilisé pour essayer de lire le verrouillage du segment. Étant donné que le tableau de verrouillage du segment n'est pas initialisé pendant la construction, une valeur nulle peut être lue, donc un jugement est requis en premier. Après avoir confirmé que le verrouillage du segment et sa table de hachage interne ne sont pas vides, les éléments du tableau de hachentrie sont lus par le code de hachage. Selon le diagramme de structure ci-dessus, vous pouvez voir que le nœud d'en-tête de la liste liée est obtenu pour le moment. Ensuite, traversez et recherchez la liste liée du début à la fin. Si la valeur correspondante est trouvée, elle sera retournée, sinon elle sera renvoyée nul. Ce qui précède est l'ensemble du processus de recherche d'éléments.
6. Comment implémenter l'élément d'insertion?
// Ajouter des paires de valeurs clés à l'ensemble (remplacer s'il y a) @SuppressWarnings ("Unchecked") public v put (k key, v valeur) {segment <k, v> s; // La valeur passée ne peut pas être vide si (valeur == null) lance un nouveau nullpointerException (); // Calculez le code de hachage à l'aide de la fonction de hash int hash = hash (key); // Calculez l'indice du verrouillage du segment en fonction du code de hash int j = (hash >>> segmentshift) & segmentMask; // Essayez d'obtenir le verrouillage du segment en fonction de l'indice if ((s = (segment <k, v>) disfe.getObject (segments, (j << sshift) + sbase)) == null) {// Si le verrouillage du segment obtenu est vide, construire un s = assureResegment (j); } // Appelez la méthode de put du verrouillage du segment return s.put (key, hash, valeur, false);} // ajouter une paire de valeurs de clé à l'ensemble (ajouter si elle n'existe pas) @SuppressWarnings ("non cochée") public v putifabsent (k key, v valeur) {segment <k, v> s; // La valeur passée ne peut pas être vide si (valeur == null) lance un nouveau nullpointerException (); // Calculez le code de hachage avec hash = hash (key); // Calculez l'indice du verrouillage du segment en fonction du code de hash int j = (hash >>> segmentshift) & segmentMask; // Essayez d'obtenir le verrouillage du segment en fonction de l'indice if ((s = (segment <k, v>) unsetafe.getObject (segments, (j << sshift) + sbase)) == null) {// Construire un s = assuresegment (j); } // Calendrier La méthode de put du verrouillage du segment renvoie S.put (clé, hachage, valeur, vrai);}Il existe deux méthodes dans ConcurrentHashMap pour ajouter des paires de valeurs clés. S'il existe, il sera écrasé lorsqu'il sera ajouté via la méthode de put. La méthode IFABSENT est ajoutée via la méthode IFABSENT PUT, elle ne sera pas écrasée. Les deux méthodes appellent la méthode de put de verrouillage du segment pour terminer l'opération, mais le dernier paramètre passé est différent. Dans le code ci-dessus, nous pouvons voir que nous calculons d'abord l'indice du verrouillage du segment dans le tableau en fonction du code de hachage de la clé, puis utilisons la méthode GetObject de classe dangereuse pour lire le verrouillage du segment selon l'indice. Étant donné que les éléments du tableau de segment ne sont pas initialisés lors de la construction du concurrenthashmap, une valeur nulle peut être lue et un nouveau verrouillage de segment sera créé via la méthode EnsureSegment. Après avoir obtenu le verrouillage du segment, appelez sa méthode de put pour terminer l'opération d'addition. Jetons un œil à la façon de le faire fonctionner.
// Ajouter des paires de valeurs de clé final v put (k key, int hash, V valeur, booléen uniquementIfabsent) {// Essayez d'acquérir le verrou, s'il échoue, spin hashentry <k, v> node = trylock ()? NULL: ScanAndLockForput (clé, hachage, valeur); V OldValue; essayez {hashentry <k, v> [] tab = table; // Calculez l'indice de l'indice de l'élément index = (tab.length - 1) & hash; // Obtenez le nœud d'en-tête de la liste liée en fonction de l'indice Hashentry <k, v> first = entryat (tab, index); for (hashentry <k, v> e = premier ;;) {// transf la liste liée pour trouver l'élément, et if (e! = null) {k k; if ((k = e.key) == key || (e.hash == hash && key.equals (k)))) {oldValue = e.Value; // décidez de remplacer l'ancienne valeur en fonction des paramètres if (! Onlyifabsent) {e.Value = valeur; ++ modCount; } casser; } e = e.next; // Si vous n'êtes pas trouvé, ajoutez un nœud à la liste liée} else {// insérez le nœud de nœud dans l'en-tête de la liste liée if (node! = Null) {node.setNext (premier); } else {node = new hashentry <k, v> (hash, key, valeur, premier); } // Après avoir inséré le nœud, ajoutez toujours 1 int c = count + 1; // Si l'élément dépasse le seuil, développez la capacité if (c> threshold && tab.length <maximum_capacity) {rehash (node); // Sinon, remplacez l'indice de la table de hash spécifiée par le nœud nœud} else {setEntryat (tab, index, nœud); } ++ modCount; count = c; OldValue = null; casser; }}} enfin {unlock (); } return oldValue;}Pour garantir la sécurité des filetages, les opérations dans les serrures segmentées doivent être verrouillées, de sorte que le thread acquiert la serrure au début et continuera d'exécuter si l'acquisition est réussie. Si l'acquisition échoue, appelez la méthode ScanAndLockForput pour tourner. Pendant le processus de spin, scannez la table de hachage pour trouver la clé spécifiée. Si la clé n'existe pas, un nouveau hachentry sera créé, de sorte qu'il n'est pas nécessaire de le créer à nouveau après avoir obtenu le verrou. Afin de faire certaines choses en attendant le verrou, il ne perdra pas de temps en vain. Cela montre les bonnes intentions de l'auteur. Nous expliquerons en détail la méthode de spin spécifique plus tard. Maintenant, retirez le focus en premier. Une fois que le thread a réussi à acquérir le verrou, il obtiendra l'élément de l'indice spécifié en fonction de l'indice calculé. À l'heure actuelle, le nœud d'en-tête de la liste liée est obtenu. Si le nœud d'en-tête n'est pas vide, la liste liée sera traversée et recherchée. Après l'avoir trouvé, décidez de le remplacer en fonction de la valeur du seul paramètre soutenu. Si la traversée n'est pas trouvée, un nouveau hachentry pointera vers le nœud d'en-tête. À l'heure actuelle, si un hashentry est créé pendant le rotation, alors indiquez directement à côté du nœud d'en-tête actuel. Si le spin n'est pas créé, un nouveau hachentry sera créé ici et pointera vers le nœud d'en-tête. Après avoir ajouté des éléments à la liste liée, vérifiez si le nombre total d'éléments dépasse le seuil. S'il dépasse, appelez Rehash pour l'expansion. S'il ne le dépasse pas, reportez-vous directement à l'élément d'indice correspondant du tableau au nœud nouvellement ajouté. La méthode SETENTRYAT modifie la référence de l'élément de tableau en appelant la méthode PutOrDesterObject de DeSAper, qui garantit que d'autres threads peuvent lire la dernière valeur lors de la lecture.
7. Comment mettre en œuvre la suppression des éléments?
// Supprimer l'élément spécifié (supprimer directement après avoir trouvé l'élément correspondant) public V Suppter (clé d'objet) {// Utilisez la fonction de hachage pour calculer le code de hachage int hash = hash (key); // acquérir l'index du verrouillage du segment en fonction du segment de code de hachage <k, v> s = segmentforhash (hash); // Calendra la méthode de suppression du rendement du verrouillage du segment s == null? null: s.Remove (key, hash, null);} // supprimer l'élément spécifié (supprime la valeur égale à la valeur donnée) booléen publique supprime (clé d'objet, valeur d'objet) {// Utilisez la fonction de hachage pour calculer le code de hachage int hash = hash (key); Segment <k, v> s; // peut s'assurer que le verrouillage du segment n'est pas vide avant d'appeler la valeur de retour de la méthode de suppression! = Null && (s = segmentforhash (hash))! = Null && s.remove (key, hash, valeur)! = Null;}ConcurrentHashMap fournit deux opérations de suppression, l'une doit la supprimer directement après l'avoir trouvée, et l'autre est de la comparer d'abord, puis de la supprimer après l'avoir trouvée. Ces deux méthodes de suppression sont de trouver le verrouillage du segment correspondant en fonction du code de hachage de la clé, puis de terminer l'opération de suppression en appelant la méthode de suppression du verrouillage du segment. Jetons un coup d'œil à la méthode de suppression du verrouillage du segment.
// Supprimer l'élément spécifié final V Support (touche d'objet, hash int, valeur objet) {// Essayez d'acquérir le verrou, s'il échoue, spin if (! Trylock ()) {ScanAndLock (key, hash); } V OldValue = null; essayez {hashentry <k, v> [] tab = table; // Calculez l'indice de l'indice de l'élément index = (tab.length - 1) & hash; // Obtenez l'élément de tableau en fonction de l'indice (nœud d'en-tête de liste des liens) Hashentry <k, v> e = entryat (tab, index); Hashentry <k, v> pred = null; // Transférer la liste liée pour trouver l'élément à supprimer tandis que (e! = Null) {k k; // Suivant pointe vers le nœud successeur du nœud actuel Hashentry <k, v> suivant = e.Next; // Recherchez le nœud correspondant basé sur la clé et le hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {v V = e.Value; // ignore la valeur réalisée si ce n'est pas égal à v, et le supprimer dans d'autres cas if (value == null || value == v || value.equals (v)) {// si pred est vide, cela signifie que le nœud à supprimer est le nœud d'en-tête if (pred == null) {// Réinitialiser le nœud d'en-tête de la liste liée SETENTRYAT (TAB NULL, index, Next); } else {// Définissez la succession du nœud de pré-nœud suivant pred.setNext (suivant); } ++ modCount; --compter; // Enregistrez la valeur de la suppression de l'élément oldvalue = v; } casser; } // Si E n'est pas le nœud que vous recherchez, pointez la référence prédable à celui-ci = e; // Vérifiez le nœud suivant E = Suivant; }} enfin {unlock (); } return oldValue;}Lorsque vous supprimez des éléments dans les verrous du segment, vous devez d'abord acquérir le verrou. Si l'acquisition échoue, appelez la méthode Scanandlock pour la rotation. Si l'acquisition est réussie, exécutez l'étape suivante. Calculez d'abord l'indice du tableau, puis obtenez les éléments du tableau de hachentrie via l'indice. Ici, le nœud d'en-tête de la liste liée est obtenu. Ensuite, traversez et recherchez la liste liée. Avant cela, utilisez le pointeur suivant pour enregistrer le nœud successeur du nœud actuel, puis comparez la clé et le hachage pour voir si c'est le nœud que vous recherchez. Si c'est le cas, effectuez le suivant si le jugement. Si la valeur est vide ou si la valeur est égale à la valeur actuelle du nœud, il entrera l'instruction if pour la suppression, sinon il sera ignoré directement. Il y a deux situations lors de l'exécution d'une opération de suppression dans une instruction IF. Si le nœud actuel est un nœud d'en-tête, définissez directement le nœud suivant comme nœud d'en-tête. Si le nœud actuel n'est pas un nœud d'en-tête, définissez le successeur du nœud de pré-pré-nœud suivant. Le nœud Pred représente ici le prédécesseur du nœud actuel. Chaque fois avant de vérifier le nœud suivant, Pred est pointé vers le nœud actuel, ce qui garantit que le nœud Pred est toujours le prédécesseur du nœud actuel. Notez que contrairement à JDK1.6, dans JDK1.7, la variable suivante de l'objet Hashentry n'est pas définitive, vous pouvez donc supprimer l'élément en modifiant directement la valeur référencée par Suivant. Étant donné que la variable suivante est de type volatile, le thread de lecture peut immédiatement lire la dernière valeur.
8. Comment les éléments de remplacement sont-ils mis en œuvre spécifiquement?
// Remplacez l'élément spécifié (opération CAS) Boolean Public Boolean Remplace (K Key, V OldValue, V NewValue) {// Utilisez la fonction de hachage pour calculer le code de hachage Int Hash = Hash (clé); // Assurez-vous que OldValue et NewValue ne sont pas vides si (OldValue == null || newValue == null) lancez new nullpointerException (); // Obtenez l'index du verrouillage du segment en fonction du segment de code de hachage <k, v> s = segmentforhash (hash); // Appel de la méthode de remplacement du verrouillage du segment renvoie s! = Null && s.replace (clé, hachage, oldvalue, newValue);} // Remplacer l'opération d'élément (opération CAS) final booléen repos (k key, int hash, v oldvalue, v newValue) {// essaie d'acquérir le verrouillage, si elle défaillante, spin if (! Trylock () {scanandLock. } boolean remplacé = false; essayez {Hashentry <k, v> e; // Recherchez directement le nœud d'en-tête via le hash, puis traversez la liste liée pour (e = entryForHash (this, hash); e! = Null; e = e.next) {k k; // Recherchez le nœud à remplacer en fonction de la clé et du hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {// si la valeur de courant spécifiée est correcte, remplacer if (oldValue.equals (e.Value)) {e.Value = newValue; ++ modCount; remplacé = true; } // Sinon, si aucune opération n'est effectuée, retournez Break; }}} enfin {unlock (); } retour remplacé;}ConcurrenthashMap fournit également deux opérations de remplacement, l'une doit remplacer directement après la recherche, et l'autre est de comparer d'abord puis de remplacer (opération CAS). La mise en œuvre de ces deux opérations est à peu près la même, sauf que l'opération CAS a une couche supplémentaire d'opérations de comparaison avant de remplacer, nous n'avons donc qu'à comprendre brièvement l'une des opérations. Ici, nous utilisons les opérations CAS pour l'analyse, qui est toujours une ancienne routine. Tout d'abord, trouvez le verrouillage du segment correspondant en fonction du code de hachage de la touche, puis appelez sa méthode de remplacement. Après avoir entré la méthode de remplacement dans le verrouillage du segment, vous devez d'abord acquérir le verrou. Si l'acquisition échoue, tournez-la. Si l'acquisition est réussie, passez à l'étape suivante. Tout d'abord, obtenez le nœud d'en-tête de la liste liée en fonction du code de hachage, puis parcourez et recherchez en fonction de la clé et du hachage. Après avoir trouvé l'élément correspondant, comparez si l'ancienvalie donnée est la valeur actuelle. Sinon, renoncez à la modification et, dans l'affirmative, remplacez-la par la nouvelle valeur. Étant donné que le champ de valeur de l'objet Hashentry est de type volatile, il peut être remplacé directement.
9. Qu'avez-vous fait exactement lorsque vous tournez?
// Spin en attendant d'acquérir le verrouillage (opération de put) Hashentry privé <k, v> scanandlockForput (key k, int hash, V valeur v) {// Obtenez le nœud d'en-tête en fonction du code de hachage Hashentry <k, v> first = entryForHash (this, hash); Hashentry <k, v> e = premier; Hashentry <k, v> node = null; intatries = -1; // Spin while (! Trylock ()) {Hashentry <k, v> f; if (RETRES <0) {// Si le nœud d'en-tête est vide, créez un nouveau nœud if (e == null) {if (node == null) {node = new hashentry <k, v> (hash, key, valeur, null); } Retries = 0; // Sinon, traversez la liste liée pour localiser le nœud} else if (key.equals (e.key)) {Retries = 0; } else {e = e.next; } // Récupère Ajouter 1 ici à chaque fois et déterminer si elle dépasse la valeur maximale} else if (++ retrees> max_scan_retries) {lock (); casser; // Lorsque les rétruistes sont même des nombres, déterminez si le premier a changé} else if ((Retries & 1) == 0 && (f = entryForHash (this, hash))! = Premier) {e = first = f; Retries = -1; }} Node de retour;} // Spin en attente pour acquérir le verrouillage (Supprimer et remplacer les opérations) private void scanandlock (clé d'objet, int hash) {// Obtenez le nœud d'en-tête de la liste liée selon le Hash Code Hashentry <k, v> first = entryForHash (ce, hash); Hashentry <k, v> e = premier; intatries = -1; // Spin while (! Trylock ()) {Hashentry <k, v> f; if (Retries <0) {// Transférer la liste liée pour localiser le nœud if (e == null || key.equals (e.key)) {Retries = 0; } else {e = e.next; } // Récupère Ajouter 1 ici à chaque fois et déterminer si elle dépasse la valeur maximale} else if (++ retrees> max_scan_retries) {lock (); casser; // Lorsque les rétruistes sont même des nombres, déterminez si le premier a changé} else if ((Retries & 1) == 0 && (f = entryForHash (this, hash))! = Premier) {e = first = f; Retries = -1; }}}Comme nous l'avons mentionné plus tôt, mettez, supprimez et remplacer les opérations dans les verrous segmentés nécessitent que le verrou est acquis en premier. Ce n'est qu'après avoir réussi à obtenir la serrure que la prochaine opération peut être effectuée. Si l'acquisition échoue, Spin sera effectué. L'opération de spin est également ajoutée dans JDK1.7. Afin d'éviter la suspension et le réveil fréquents des fils, il peut améliorer les performances pendant les opérations simultanées. Le ScanandLockforput est appelé dans la méthode de put, et le ScanandLock est appelé dans les méthodes de suppression et de remplacement. Les deux méthodes de spin sont à peu près les mêmes, ici, nous analysons uniquement la méthode ScanandLockforput. Tout d'abord, vous devez obtenir le nœud d'en-tête de la liste liée en fonction du code de hachage. Ensuite, le thread entrera la boucle While pour exécuter. La seule façon de quitter la boucle est d'acquérir avec succès la serrure, et le fil ne sera pas suspendu pendant cette période. Lorsque la boucle vient d'être saisie, la valeur des tentatives est -1. À l'heure actuelle, le fil n'essaiera pas d'acquérir la serrure immédiatement. Au lieu de cela, il trouvera d'abord le nœud correspondant à la clé (s'il n'est pas trouvé, un nouveau sera créé), puis définira les tentatives sur 0. Ensuite, il essaiera d'acquérir le verrouillage encore et encore. La valeur de rétraction correspondante sera également ajoutée 1 à chaque fois jusqu'à ce que le nombre maximal de tentatives dépasse le nombre maximum de tentatives. Si le verrouillage n'a pas été obtenu, la méthode de verrouillage sera appelée pour le blocage et l'obtention. Au cours de la tentative d'acquérir le verrou, il vérifiera si le nœud d'en-tête a été modifié tous les deux (les tentatives sont égales). S'il est modifié, réinitialisez les Retries à -1, puis répétez le processus tout à l'heure. C'est ce que fait le fil lors de la rotation. Il convient de noter que si le nœud de tête a été détecté pour être modifié pendant le rotation, le temps de spin du fil sera étendu.
10. Quelles opérations sont effectuées lors de l'élargissement de la table de hachage?
// hachage à nouveau @SuppressWarnings ("non coché") private void rehash (hashentry <k, v> nœud) {// Obtenez la référence à l'ancien hachage de hachage Hashentry <k, v> [] oldTable = table; // Obtenez la capacité de l'ancienne table de hachage dans OldCapacity = OldTable.Length; // Calculez la capacité de la nouvelle table de hachage (2 fois l'ancienne table de hachage) int newcapacity = oldcapacity << 1; // Calculez le nouveau seuil de seuil d'élément = (int) (newCapacity * LoadFactor); // Créer un nouveau tableau de hashentry Hashentry <k, v> [] newtable = (hashentry <k, v> []) new hashentry [newcapacity]; // générer une nouvelle valeur de masque int sizemask = newCapacity - 1; // Tranquility à travers tous les éléments de l'ancienne table pour (int i = 0; i <oldcapacity; i ++) {// Obtenez le nœud d'en-tête de la liste liée Hashentry <k, v> e = OldTable [i]; if (e! = null) {hashentry <k, v> next = e.next; // Calculez l'index de l'élément dans la nouvelle table int idx = e.hash & sizemask; // Suivant est vide pour indiquer qu'il n'y a qu'un seul nœud dans la liste liée if (next == null) {// Mettez le nœud directement dans la nouvelle table newtable [idx] = e; } else {Hashentry <k, v> lastrun = e; int Lasridx = idx; // Positionnez le nœud lastrun et mettez directement le nœud après lastrun dans la nouvelle table pour (hashentry <k, v> dernier = suivant; Last! = Null; Last = Last.Next) {int k = last.hash & sizemask; if (k! = LASIDX) {LASIDX = K; lastrun = dernier; }} newtable [LASIDX] = lastrun; // Transipate les éléments avant le nœud lastrun de la liste liée, copiez-les à son tour dans la nouvelle table pour (Hashentry <k, v> p = e; p! = Lastrun; p = p.next) {v V = p.Value; int h = p.hash; int k = h & sizemask; Hashentry <k, v> n = newtable [k]; newtable [k] = new hashentry <k, v> (h, p.key, v, n); }}}}} // Calculez l'indice du nœud entrant dans la nouvelle table int nodeIndex = node.hash & sizemask; // Ajoutez le nœud entrant au nœud d'en-tête de la liste liée Node.SetNext (NewTable [NodeIndex]); // Échangez l'élément indicateur spécifié de la nouvelle table avec le nœud NEWTable entrant [NodeIndex] = Node; // pointer la référence de la table de hachage à la nouvelle table de table = newtable;}La méthode Rehash est appelée dans la méthode de put. Nous savons que lorsque la méthode de put est mise, le nouvel élément sera créé et ajouté au tableau de hachage. Plus la possibilité de conflits de hachage est grande, plus les performances de la table de hachage diminuent également. Par conséquent, chaque fois que l'opération de put, il vérifiera si le nombre total d'éléments dépasse le seuil. S'il dépasse le seuil, la méthode de rechash sera appelée pour élargir la capacité. Étant donné que la longueur du tableau ne peut plus être modifiée une fois qu'elle est déterminée, un nouveau tableau doit être créé pour remplacer le tableau d'origine. À partir du code, vous pouvez savoir que le tableau nouvellement créé est le double de la longueur du tableau d'origine (OldCapacity << 1). After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.