Comment calculer un bon code de hachage pour une liste de chaînes de caractères ?

Question

Le contexte :

• J'ai une courte liste de cordes.
• Le nombre de cordes n'est pas toujours le même, mais il est presque toujours de l'ordre d'une "poignée".
• Dans notre base de données, nous stockons ces chaînes dans une deuxième table normalisée.
• Ces chaînes sont jamais modifiés une fois qu'ils sont écrits dans la base de données.

Nous souhaitons être en mesure de faire correspondre ces chaînes rapidement dans une requête sans que les performances ne soient affectées par un grand nombre de jointures.

Je pense donc stocker un code de hachage de toutes ces chaînes dans la table principale et l'inclure dans notre index, de sorte que les jointures ne soient traitées par la base de données que lorsque le code de hachage correspond.

Alors comment obtenir un bon code de hachage ? Je pourrais :

• Xor les codes de hachage de toutes les chaînes ensemble
• Xor avec multiplication du résultat après chaque chaîne (disons par 31)
• Rassemblez toutes les chaînes et obtenez le code de hachage.
• D'une autre manière

Alors, qu'en pensent les gens ?

---

En fin de compte, je me contente de concaténer les chaînes et de calculer le code de hachage pour la concaténation, car c'est simple et cela fonctionne assez bien.

(Si cela vous intéresse, nous utilisons .NET et SqlServer)

---

Bug !, Bug !

Citation des directives et règles pour GetHashCode par Eric Lippert

La documentation de System.String.GetHashCode note spécifiquement que deux chaînes identiques identiques peuvent avoir des codes de hachage différents dans différentes versions du CLR, et en fait, c'est le cas. Ne stockez pas de chaînes dans des bases de données et ne vous attendez pas à ce qu'ils qu'ils soient toujours les mêmes, car ils car ce ne sera pas le cas.

Donc String.GetHashcode() ne doit pas être utilisé pour cela.

Answer 1

La pratique standard de Java est d'écrire simplement

final int prime = 31;
int result = 1;
for( String s : strings )
{
    result = result * prime + s.hashCode();
}
// result is the hashcode.

Answer 2

Votre première option n'a que l'inconvénient de (String1, String2) produisant le même code de hachage de (String2, String1) . Si ce n'est pas un problème (par exemple, parce que vous avez un ordre fixe), c'est parfait.

" Rassemblez toutes les chaînes et obtenez le code de hachage. "me semble plus naturel et plus sûr.

Mise à jour : Comme le souligne un commentaire, cela présente l'inconvénient que la liste ("x", "yz") et ("xy", "z") donneraient le même hachage. Pour éviter cela, vous pourriez joindre les chaînes de caractères avec un délimiteur de chaîne qui ne peut pas apparaître à l'intérieur des chaînes de caractères.

Si les chaînes de caractères sont grandes, vous préférerez peut-être hacher chacune d'entre elles, catcher les codes de hachage et ré-hausser le résultat. Plus de CPU, moins de mémoire.

Answer 3

Je ne vois aucune raison de ne pas concaténer les chaînes de caractères et de ne pas calculer le code de hachage pour la concaténation.

Par analogie, si je voulais calculer une somme de contrôle MD5 pour un bloc de mémoire, je ne diviserais pas le bloc en petits morceaux et je calculerais des sommes de contrôle MD5 individuelles pour chacun d'eux, puis je les combinerais avec une méthode ad hoc.

Answer 4

Un autre moyen qui me vient à l'esprit est de chaîner des xors avec des hachages tournés basés sur l'index :

int shift = 0;
int result = 1;
for(String s : strings)
{
    result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1);
    shift = (shift+1)%32;
}

edit : en lisant l'explication donnée dans java effective, je pense que le code de geoff serait beaucoup plus efficace.

Answer 5

Une solution SQL pourrait être basée sur les fonctions checksum et checksum_agg. Si je suis bien, vous avez quelque chose comme.. :

MyTable
  MyTableId
  HashCode

MyChildTable
  MyTableId  (foreign key into MyTable)
  String

avec les différentes chaînes de caractères pour un élément donné (MyTableId) stocké dans MyChildTable. Pour calculer et stocker une somme de contrôle reflétant ces chaînes (qui ne seront jamais modifiées), quelque chose comme ceci devrait fonctionner :

UPDATE MyTable
 set HashCode = checksum_agg(checksum(string))
 from MyTable mt
  inner join MyChildTable ct
   on ct.MyTableId = mt.MyTableId
 where mt.MyTableId = @OnlyForThisOne

Je crois que c'est indépendant de l'ordre, donc les chaînes "The quick brown" produiraient la même somme de contrôle que "brown The quick".