Un thread HashMap est-il sûr pour différentes clés?

Si j'ai deux threads multiples accédant à un HashMap, mais garantissant qu'ils n'accéderont jamais à la même clé en même temps, cela pourrait-il encore conduire à une condition de concurrence?

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

Si vous modifiez un HashMap de quelque manière que ce soit, votre code est simplement cassé.

Il a raison. Un HashMap mis à jour sans synchronisation sera interrompu même si les threads utilisent des ensembles de clés disjoints. Voici quelques-unes des choses qui peuvent mal tourner.

• Si un thread fait un put, un autre thread peut voir une valeur périmée pour la taille de la table de hachage.

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

• Quand un thread fait un putpour une clé qui entre en collision avec une clé utilisée par un autre thread, et que ce dernier thread fait un putpour sa clé, alors ce dernier peut voir une copie périmée de la référence de la chaîne de hachage. Le chaos peut s'ensuivre.

• Lorsqu'un thread sonde la table avec une clé qui entre en collision avec l'une des clés d'un autre thread, il peut rencontrer cette clé sur la chaîne. Il appellera equals sur cette clé, et si les threads ne sont pas synchronisés, la méthode equals peut rencontrer un état périmé dans cette clé.

Et si vous avez deux threads qui font putou removedemandent simultanément , il existe de nombreuses opportunités pour les conditions de course.

Je peux penser à trois solutions:

1. Utilisez un ConcurrentHashMap.
2. Utilisez un régulier HashMapmais synchronisez à l'extérieur; par exemple en utilisant des mutex primitifs, des Lockobjets, etc.
3. Utilisez un différent HashMappour chaque fil. Si les threads ont vraiment un ensemble disjoint de clés, alors il ne devrait pas être nécessaire (d'un point de vue algorithmique) pour eux de partager une seule carte. En effet, si vos algorithmes impliquent que les threads itèrent les clés, les valeurs ou les entrées de la carte à un moment donné, diviser la carte unique en plusieurs cartes pourrait donner une accélération significative pour cette partie du traitement.

Utilisez simplement un ConcurrentHashMap. Le ConcurrentHashMap utilise plusieurs verrous qui couvrent une plage de seaux de hachage pour réduire les risques de contestation d'un verrou. L'acquisition d'un verrou incontesté a un impact marginal sur les performances.

Pour répondre à votre question initiale: selon le javadoc, tant que la structure de la carte ne change pas, tout va bien. Cela signifie qu'il n'y a pas du tout de suppression d'éléments et pas d'ajout de nouvelles clés qui ne sont pas déjà dans la carte. Le remplacement de la valeur associée aux clés existantes est très bien.

Si plusieurs threads accèdent simultanément à une mappe de hachage et qu'au moins un des threads modifie la mappe structurellement, elle doit être synchronisée en externe. (Une modification structurelle est toute opération qui ajoute ou supprime un ou plusieurs mappages; le simple fait de changer la valeur associée à une clé qu'une instance contient déjà n'est pas une modification structurelle.)

Bien que cela ne donne aucune garantie sur la visibilité. Vous devez donc être prêt à accepter de récupérer occasionnellement des associations obsolètes.

Cela dépend de ce que vous entendez sous «accès». Si vous ne faites que lire, vous pouvez lire même les mêmes clés tant que la visibilité des données est garantie par les règles « arrive avant ». Cela signifie que cela HashMapne devrait pas changer et que toutes les modifications (constructions initiales) doivent être terminées avant que tout lecteur ne commence à accéder HashMap.

Si vous modifiez un HashMapde quelque manière que ce soit, votre code est simplement cassé. @Stephen C explique très bien pourquoi.

EDIT: Si le premier cas est votre situation réelle, je vous recommande de l'utiliser Collections.unmodifiableMap()pour être sûr que votre HashMap n'est jamais modifié. Les objets pointés HashMapne doivent pas non plus changer, une utilisation agressive de finalmots-clés peut donc vous aider.

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

La modification d'un HashMap sans synchronisation appropriée à partir de deux threads peut facilement conduire à une condition de concurrence.

• Lorsqu'un a put()conduit à un redimensionnement de la table interne, cela prend un certain temps et l'autre thread continue d'écrire dans l'ancienne table.
• Deux put()pour des clés différentes conduisent à une mise à jour du même compartiment si les codes de hachage des clés sont égaux modulo à la taille de la table. (En fait, la relation entre le hashcode et l'index du compartiment est plus compliquée, mais des collisions peuvent toujours se produire.)