Gestion des collisions dans une HashMap

Bonjour,

il y a un truc qui m'échappe dans la gestion des collisions avec une HashMap.
J'y stocke des tableaux byte[] dont les emplacements sont distribués à l'aide de HashCode issu du contenu de chaque tableau.

J'ai besoin qu'en cas de collision, le nouveau tableau s'inscrit dans ma HashMap sans écraser le tableau y figurant déjà.
D'après ce que j'ai cru comprendre en lisant l'excellent ouvrage de Jean-Michel DOUDOUX: https://jmdoudoux.developpez.com/cou...#collections-5

Citation:

---

Si deux objets possèdent la même valeur de hachage, il y a une collision car les deux objets doivent être insérés dans le même bucket. Pour gérer les problèmes, le bucket contient une liste chaînée*: chaque élément (sa clé et sa valeur) est encapsulé dans une instance de type Entry.

---

Alors que si je lis la documentation:

Citation:

---

public*V*put​(K*key, V*value)

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

---

En entrant manuellement des paires <Cle, Valeur> dans une HashMap, et en provoquant des collisions, je ne vois pas de liste chaînée de paires, qui me permette de garder les éléments en collision.
Voici le bout de code que j'utilise pour explorer les éléments de la HashMap:

Code:

---

1 2 3 4 5 6 7 8

for ( Iterator iter = maHashMapSolutions.entrySet().iterator(); iter.hasNext(); ) { Entry entry = (Entry)iter.next(); System.out.println( "Clé: " + entry.getKey() + " _ Valeur: " + Arrays.toString( (byte[])entry.getValue())); }   System.out.println( "-----------------------" );

---

Si je regarde le contenu de ma HashMap en mode débogage, je vois que les nouvelles valeurs viennent écraser les anciennes...

Comment mettre en œuvre ce système de liste chainées qui permettrait de garder les différents éléments ?

Merci

Hello,

Il y a deux points à préciser :

- Point 1 : Le hashcode des tableaux byte[] n'est pas basé sur leur contenu.

En effet Java adopte la convention que le hashcode d'un objet s'obtient en appelant sa méthode hashCode().

Or toujours en Java, le choix a été fait que les tableaux sont des objets, certes, mais ils ne définissent ni redéfinissent aucune méthode.
La méthode hashCode() des tableaux est donc celle héritée de java.lang.Object, qui n'a aucun contenu spécialisé et notamment ne peut pas être au courant de contenu d'aucun tableau.

La méthode hashCode() de java.lang.Object, et donc celle des tableaux puisque c'est la même, fournit un hashcode basé sur l'identifiant unique de l'objet dans la JVM. Grosso-merdo l'adresse mémoire de l'objet, c'est plus compliqué que ça mais pas beaucoup.
Autrement dit, deux variables qui pointent vers le même objet auront le même hashcode (forcément,) mais deux objets différents auront toujours un hashcode différent, s'ils héritent du hashCode() de java.lang.Object. (Bon, pas forcément toujours, genre une JVM pourrait contenir plus de 4 milliards d'objets différents, après tout, ou quelque chose de ce genre.)

Bref, ce qu'il faut retenir c'est que deux tableaux créés chacun avec new, n'auront pas le même hashcode même s'ils ont le même contenu. Leur contenu est ignoré par leur hashcode.

- Point 2 : Il ne faut pas confondre collision de clé et collision de hashcode.

Dans une Map, et donc notamment dans HashMap, chaque clé est unique et donc associée à une seule valeur.

(Après rien n'empêche de faire en sorte que les valeurs contenues soient des List, genre Map<String, List<String>>.)

Quand on parle du sujet de la collision de hashcode, c'est parce que :

• deux clés de valeurs différentes pourraient avoir le même hashcode. C'est quelque chose que les implémentations de hashCode() doivent chercher à éviter, mais fatalement ça peut arriver quand même.
• même sans parler d'avoir le même hashcode, deux hashcode différents, mais proches, vont se retrouver dans le même bucket d'une hashtable, ce qui revient à la même chose que le même hashcode.

Dans la mesure où une Map, et donc une HashMap, est censée s'assurer de l'unicité des clés, mais pas du tout de l'unicité des hashcodes des clés, alors HashMap gère les collisions de hashcode en mettant les clés différentes d'un même bucket dans une LinkedList stockée dans ce bucket.

Les clés restent toutes différentes, de valeur non égales. Elles se retrouvent juste, plus ou moins par malchance, dans le même bucket.


- Conclusion

1. On ne peut pas utiliser des tableaux comme clés.
2. Si on veut stocker plusieurs valeurs pour une même clé, il faut que les valeurs stockées soient des collections, dans lesquelles on peut ajouter des éléments individuels. Ce n'est pas fourni avec Java, mais il existe de nombreuses bibliothèques tierces qui fournissent MultiMap, une implémentation/légère modification de Map qui associe facilement une clé avec plusieurs valeurs.

Bonjour,

merci Thelvin pour cette réponse très complète.

Je ne l'avais pas précisé dans le 1er post, mais pour obtenir le hashcode des tableau, j'utilise Array.hashCode( monTableau );
Cela me sort un hashcode en fonction du contenu du tableau.

Petite question: pourrais-tu me conseiller une bibliothèque tierce qui puisse répondre à mon problème technique ?


Merci

Comment ça, "pour obtenir le hashcode" ?

Le hashcode d'une clé est obtenu en appelant hashCode() dessus, et pas autrement. C'est quoi tes clés ?

En fait, j'ai un tableau de byte[] qui contient différentes valeurs, qui évoluent selon certains processus.
J'ai besoin de stocker certaines valeurs (mais pas toutes), parmi des millions de possibilités.
Or certaines combinaisons de bytes réapparaissent plusieurs fois au cours du processus, et je ne veux pas stocker les doublons.

Avec la fonction Arrays.hashCode( monTableau );, qui est une fonction du package java.util.Arrays, j'obtiens un code de hashage qui dépend du contenu du tableau.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

public static int hashCode(byte[] a)   Returns a hash code based on the contents of the specified array. For any two byte arrays a and b such that Arrays.equals(a, b), it is also the case that Arrays.hashCode(a) == Arrays.hashCode(b).   The value returned by this method is the same value that would be obtained by invoking the hashCode method on a List containing a sequence of Byte instances representing the elements of a in the same order. If a is null, this method returns 0.   Parameters: a - the array whose hash value to compute Returns: a content-based hash code for a Since: 1.5

---

Le problème est que certaines combinaisons de bytes aboutissent au même HashCode... alors que les combinaisons sont différentes. Bref...
Dans ce cas, j'affine le test en comparant les 2 combinaisons pour savoir si elles sont vraiment identiques.
En cas d'inégalité, j'ai besoin de stocker aussi la deuxième combinaison... Mais comme je les classe dans la HashMap, avec comme clé, le code de hachage... je perds la première combinaison, car elle est écrasée par la seconde entrée:roll:.

Et c'est la que je suis embêté...

C'est tordu, il vaudrait mieux utiliser comme clé, un objet qui implémente hashCode() et equals().

Ce n'est pas le cas des tableaux eux-mêmes, mais un ByteBuffer par exemple fait la même chose et implémente ces deux (tant qu'on modifie pas son état).

Sinon on peut toujours faire sa propre classe pour représenter une séquence de bytes immutable, et qui implémente hashCode() et equals().

Tu peux lire cet article

https://jipe.developpez.com/articles.../?page=theorie

Bonjour,

merci, c'est gentil.
Je l'ai déjà lu. Je consulte toujours les tutos et les forums du site (et tout ce que Google me propose) avant de poster.
Bonne continuation.