Java HashMap détecter une collision

Question

Existe-t-il un moyen de détecter une collision dans Java Hash-map? Quelqu'un peut-il signaler une situation où beaucoup de collision peut avoir lieu. Bien sûr, si vous surchargez le code de hachage d'un objet et que vous renvoyez simplement une collision de valeurs constantes, vous ne risquez pas de survenir. Je ne parle pas de cela. Je veux savoir dans quelles autres situations les autres collisions sans modifier l'implémentation du hashcode par défaut.

Answer 1

J'ai créé un projet pour comparer ce genre de choses: http://code.google.com/p/hashingbench/ (Pour les tables de hachage avec filtres de chaînage, d'adressage ouvert et de bloom).

Outre le hashCode() de la clé, vous devez connaître le « barbouiller » (ou « brouillage », comme je l'appelle dans ce projet) en fonction de la table de hachage. De this list, la fonction de maculage HashMap est l'équivalent de:

public int scramble(int h) { 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

Donc, pour une collision se produire dans un HashMap, la et nécessaire suffisante condition est la suivante: scramble(k1.hashCode()) == scramble(k2.hashCode()). Ceci est toujours vrai sik1.hashCode() == k2.hashCode() (sinon, la fonction maculage/brouillage ne serait pas être fonction), de sorte que c'est une suffisante, mais pas nécessaire condition d'une collision se produise.

Edit: En fait, la condition nécessaire et suffisante au-dessus aurait dû être compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode())) - la fonction compress prend un entier et cartes à {0, ..., N-1}, où N est le nombre de seaux, il sélectionne essentiellement un seau. Habituellement, ceci est simplement implémenté comme hash % N, ou quand la taille de hashtable est une puissance de deux (et c'est réellement une motivation pour avoir des tailles hashtable de puissance de deux), comme hash & N (plus rapide). ("compress" est le nom utilisé par Goodrich et Tamassia pour décrire cette étape, dans le Data Structures and Algorithms in Java). Merci à ILMTitan d'avoir repéré mes négligences.

D'autres implémentations de hachage (ConcurrentHashMap, IdentityHashMap, etc.) ont d'autres besoins et utilisent une autre fonction de smearing/embrouillage, vous devez donc savoir de laquelle vous parlez. Par exemple, la fonction de hachage de HashMap a été mise en place parce que les gens utilisaient HashMap avec des objets avec le pire type de hashCode() pour l'ancienne implémentation de HashMap sans étalement - des objets qui diffèrent un peu, ou pas du tout, dans leurs bits de poids faible qui ont été utilisés pour sélectionner un seau - par exemple new Integer(1 * 1024), new Integer(2 * 1024) *, etc. Comme vous pouvez le voir, la fonction de maculage de HashMap fait de son mieux pour avoir tous les bits affectent le bits de poids faible). Cependant, tous ces éléments sont censés fonctionner correctement dans les cas courants - un cas particulier est celui des objets qui héritent du hashCode() du système. PS: En fait, le cas absolument laid qui a incité les implémenteurs à insérer la fonction smearing est le hashCode() de Floats/Doubles, et l'utilisation comme clés de valeurs: 1.0, 2.0, 3.0, 4.0 ..., tous ayant les mêmes bits de poids faible (zéro). Voici le rapport vieux bug lié: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

Answer 2

Exemple simple: hacher un Long. Il y a évidemment 64 bits d'entrée et seulement 32 bits de sortie. Le hachage de Long est documenté être:

(int)(this.longValue()^(this.longValue()>>>32)) 

à savoir imaginer qu'il est deux int valeurs collées les unes à côté des autres, et les XOR.

Donc tous ces aura un hashcode 0:

0 
1L | (1L << 32) 
2L | (2L << 32) 
3L | (3L << 32) 

etc

Je ne sais pas si ce compte comme un « grand nombre de collisions », mais il est un exemple où les collisions sont facile à fabriquer.

De toute évidence tout hachage où il y a plus de 2 valeurs possibles aura des collisions, mais dans de nombreux cas, ils sont plus difficiles à produire. Par exemple, alors que j'ai certainement vu des collisions de hachage sur String en utilisant uniquement des valeurs ASCII, ils sont légèrement plus difficiles à produire que ce qui précède.

Answer 3

Les deux autres réponses que je vois un bon OMI, mais je voulais juste partager que la meilleure façon de tester comment votre hashCode() se comporte dans un HashMap est de générer en fait un grand nombre de objets de votre classe, mettez-les dans l'implémentation HashMap particulière en tant que clé et chargez le processeur et la mémoire. 1 ou 2 millions d'entrées sont un bon nombre à mesurer mais vous obtiendrez de meilleurs résultats si vous testez avec vos tailles de cartes anticipées.

Je viens de regarder une classe que je doutais de sa fonction de hachage. J'ai donc décidé de remplir un HashMap avec des objets aléatoires de ce type et de tester le nombre de collisions. J'ai testé deux implémentations hashCode() de la classe à l'étude. J'ai donc écrit dans groovy la classe que vous voyez dans l'implémentation OpenJDK de HashMap pour compter le nombre de collisions dans la HashMap (voir countCollidingEntries()). Notez que ce ne sont pas de vraies collisions du hachage entier mais des collisions dans le tableau contenant les entrées. L'index de tableau est calculé en tant que hash & (length-1), ce qui signifie que plus la taille de ce tableau est courte, plus vous avez de collisions. Et la taille de ce tableau dépend de initialCapacity et loadFactor du HashMap (il peut augmenter quand put() plus de données). A la fin, j'ai considéré que regarder ces chiffres n'avait pas beaucoup de sens. Le fait que HashMap soit plus lent avec une mauvaise méthode hashCode() signifie qu'en comparant simplement l'insertion et la récupération des données de la carte, vous savez effectivement quelle implémentation hashCode() est la meilleure.

public class TestHashMap extends HashMap { 

    public TestHashMap(int size) { 
     super(size); 
    } 

    public TestHashMap() { 
     super(); 
    } 

    public int countCollidingEntries() { 
     def fs = this.getClass().getSuperclass().getDeclaredFields(); 
     def table; 
     def count =0 ; 
     for (java.lang.reflect.Field field: fs) { 
     if (field.getName() == "table") { 
      field.setAccessible(true); 
      table = field.get(super); 
      break; 
     } 
     } 
     for(Object e: table) { 
     if (e != null) { 
      while (e.next != null) { 
       count++ 
       e = e.next; 
      } 
     } 
     } 
     return count; 
    } 
}