Est-ce qu'un thread-safe HashMap convient à différentes clés?

Question

Si deux threads multiples accèdent à une carte de hachage, mais que je garantis qu'ils ne pourront jamais accéder à la même clé en même temps, cela peut-il néanmoins conduire à une situation de concurrence critique?

Answer 1

Dans @dotsid de la réponse qu'il dit ceci:

Si vous modifiez une table de hachage de toute façon alors votre code est tout simplement cassé.

Il est correct. Une table de hachage qui est mis à jour sans synchronisation pause , même si les filets à l'aide d'ensembles disjoints de touches. Voici certaines des choses qui peuvent mal se passer.

• Si un thread fait un put, puis un autre thread peut voir un état de la valeur de la table de hachage de taille.

• Lorsqu'un thread fait un put qui déclenche une reconstruction de la table, un autre thread peut voir transitoire ou obsolètes versions de la table de hachage de référence tableau, sa taille, son contenu ou les chaînes de hachage. Le Chaos peut s'ensuivre.

• Lorsqu'un thread fait un put pour une clé qui entre en collision avec certains des principaux utilisés par un autre thread, et le dernier thread fait un put de sa clé, alors ce dernier pourrait voir un rassis copie de hachage de la chaîne de référence. Le Chaos peut s'ensuivre.

• Lorsqu'un thread sondes de la table avec une clé qui entre en collision avec l'un d'un autre thread de clés, il peut rencontrer cette touche sur la chaîne. Il va appeler égaux sur cette touche, et si les fils ne sont pas synchronisés, la méthode equals peut rencontrer vicié de l'état dans cette clé.

Et si vous avez deux threads simultanément faire put ou remove des demandes, il y a de nombreuses possibilités pour les conditions de course.

Je peux penser à trois solutions:

1. Utiliser un ConcurrentHashMap.
2. Utilisez un régulier, HashMap mais synchroniser sur l'extérieur.
3. Utiliser un autre HashMap pour chaque thread. Si les fils ont vraiment un disjoints d'un ensemble de touches, alors il ne devrait pas être nécessaire (à partir d'un point de vue algorithmique) pour eux de partager une seule Carte. En effet, si votre algorithmes d'impliquer les fils de l'itération les clés, les valeurs ou les entrées de la carte à un certain point, le fractionnement de la même carte dans plusieurs cartes peuvent donner une accélération significative pour la partie du traitement.

Answer 2

Il suffit d'utiliser un ConcurrentHashMap. Le ConcurrentHashMap utilise plusieurs verrous qui couvrent un éventail de hachage seaux pour réduire les risques d'une serrure contestée. Il y a un rendement marginal de l'impact de l'acquisition d'une créance incontestée de verrouillage.

Pour répondre à votre question de départ: en Fonction de la javadoc, tant que la structure de la carte ne change pas, vous êtes beaux. Cela signifie pas la suppression d'éléments à tous et pas de l'ajout de nouvelles clés qui ne sont pas déjà dans la carte. En remplaçant la valeur associée avec les clés est très bien.

Si plusieurs threads accèdent à une carte de hachage simultanément, et au moins l'un des threads modifie la carte structurellement, il doit être synchronisé à l'extérieur. (Une modification structurelle est une opération qui ajoute ou supprime un ou plusieurs mappages, il suffit de modifier la valeur associée à une clé qu'une instance contient déjà n'est pas une modification structurelle.)

Bien qu'il ne donne aucune garantie quant à la visibilité. Donc, vous devez être prêt à accepter la récupération rassis associations à l'occasion.

Answer 3

Cela dépend de ce que tu veux dire, en vertu de "l'accès". Si vous venez de lire, vous pouvez lire même les même clés tant que la visibilité de données garanti en vertu de la "passe-avant" les règles. Cela signifie qu' HashMap ne devrait pas changer et que toutes les modifications (constructions initiales) devrait être achevée avant tout lecteur de commencer à accéder HashMap.

Si vous modifiez un HashMap de toute façon alors votre code est tout simplement cassé. @Stephen C offre une très bonne explication pourquoi.

EDIT: Si le premier cas est votre situation, je vous recommande d'utiliser Collections.unmodifiableMap() à assurez-vous que votre table de hachage est jamais modifiée. Les objets qui sont pointés par HashMap ne devrait pas changer aussi, de manière agressive à l'aide de final de mots clés peut vous aider.

Et comme @Lars Andren dit, ConcurrentHashMap est le meilleur choix dans la plupart des cas.

Answer 4

La modification d'une table de hachage sans synchronisation appropriée à partir de deux threads peuvent facilement conduire à une race condition.

• Lorsqu'un put() conduit à un redimensionnement de la table interne, cela prend un certain temps et l'autre thread continue à écrire à l'ancienne table.
• Deux put() pour les différentes touches de conduire à une mise à jour de la même seau si les touches' hashcodes sont égaux modulo la taille du tableau. (En fait, la relation entre hashcode et d'un seau d'index est plus compliqué, mais les collisions peuvent encore se produire.)