Définition du hachage d'un objet comme somme des hachages de ses membres

Question

J'ai une classe qui représente les arêtes non orientées dans un graphique. Chaque arête a deux membres vertex1 et vertex2 représentant les sommets qu'elle relie. Le problème est, qu'un bord peut être spécifié deux directions. Mon idée était maintenant de définir le hachage d'un bord comme la somme des hachages de ses sommets. De cette façon, la direction ne joue plus aucun rôle, le hachage serait le même. Y a-t-il des pièges avec ça?

Answer 1

J'ai dû résoudre un problème similaire et j'ai trouvé que l'utilisation de la somme des hachages comme un hachage entraînait trop de collisions. La distribution de la somme des hashes n'est pas assez étalée.

J'ai trouvé que l'utilisation du produit de hachage entraînait beaucoup moins de collisions. Cela dépend bien sûr de la nature des hachages pour les sommets individuels.

Mettre en place un banc d'essai et tester quelques fonctions symétriques de hachage, puis choisir la meilleure basée sur les collisions.

Vous pouvez essayer

h(x,y) = x+y 
h(x,y) = x*y 
h(x,y) = x * y + (x^y) 
h(x,y) = x *y + x + y 

où x^y = min (x, y)