fonction de hachage pour la chaîne

124

Je travaille sur une table de hachage en langage C et je teste la fonction de hachage pour la chaîne.

La première fonction que j'ai essayée est d'ajouter du code ascii et d'utiliser modulo (% 100) mais j'ai de mauvais résultats avec le premier test de données: 40 collisions pour 130 mots.

Les données d'entrée finales contiendront 8 000 mots (c'est un dictionnaire stocké dans un fichier). La table de hachage est déclarée comme int table [10000] et contient la position du mot dans un fichier txt.

La première question est quel est le meilleur algorithme pour la chaîne de hachage? et comment déterminer la taille de la table de hachage?

Merci d'avance !

:-)

lilawood
la source
11
Si votre table de hachage a 10K entrées, pourquoi utiliseriez-vous modulo 100? Obtenir 40 collisions sur 130 mots n'est pas surprenant avec un si petit module.
Carey Gregory
13
Voir burtleburtle.net/bob/hash/evahash.html et partow.net/programming/hashfunctions pour qui sont des ressources sur divers hachages (du général à la chaîne en passant par la crypto).
3
Pour clarifier @CareyGregory: Vous réalisez que, en tant que vérité mathématique de base, 130 éléments dans 100 seaux (c.-à-d. Mod 100) doivent produire 30 collisions (où la collision est comptée comme chaque fois qu'un deuxième, troisième, etc. élément est placé dans un seau), correct? Donc, vous êtes juste un peu au-dessus.
derobert
4
@lilawood: OK, c'est ce que j'ai pensé, mais pour être un meilleur test, vous devriez utiliser 80 mots avec une table de hachage de 100 entrées. Cela vous donnerait les mêmes proportions que vos données en direct et ne forcerait pas les collisions.
Carey Gregory
4
Reproduction possible de la fonction Good Hash pour les chaînes
MJ Rayburn

Réponses:

185

J'ai eu de beaux résultats avec djb2par Dan Bernstein.

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}
cnicutar
la source
37
la page liée dans la réponse est très intéressante.
Adrien Plisson
2
comment le programme sort de la boucle while ?? = S
Daniel N.
1
@ danfly09 Lorsque c est nul. L'équivalent de while (c = * str ++) serait (0! = (C = * str ++))
rxantos
5
@Josepas, la fonction de hachage devrait idéalement retourner une size_tou une autre valeur non signée (comme le long unsigned dans ce code). L' appelant est responsable de prendre modulo du résultat pour l'adapter à la table de hachage. L'appelant contrôle l'emplacement de table sur lequel le hachage est effectué; pas la fonction. Il renvoie juste un nombre non signé.
WhozCraig
6
incroyable. cet algorithme a vaincu le hachage Murmur, les hachages de variantes FNV et bien d'autres! +1
David Haim
24

Premièrement, vous ne souhaitez généralement pas utiliser de hachage cryptographique pour une table de hachage. Un algorithme très rapide par rapport aux normes cryptographiques est encore extrêmement lent par rapport aux normes de table de hachage.

Deuxièmement, vous voulez vous assurer que chaque bit de l'entrée peut / affectera le résultat. Un moyen simple de le faire est de faire pivoter le résultat actuel d'un certain nombre de bits, puis de XOR le code de hachage actuel avec l'octet actuel. Répétez jusqu'à ce que vous atteigniez la fin de la chaîne. Notez que vous ne souhaitez que la rotation soit un multiple pair de la taille d'octet.

Par exemple, en supposant le cas courant d'octets de 8 bits, vous pouvez effectuer une rotation de 5 bits:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

Edit: Notez également que 10000 emplacements sont rarement un bon choix pour une taille de table de hachage. Vous voulez généralement l'une des deux choses suivantes: vous voulez soit un nombre premier comme taille (requis pour assurer l'exactitude avec certains types de résolution de hachage), soit une puissance de 2 (donc réduire la valeur à la plage correcte peut être fait avec un simple masque de bits).

Jerry Coffin
la source
Ce n'est pas c, mais je serais intéressé par vos réflexions sur cette réponse connexe: stackoverflow.com/a/31440118/3681880
Suragch
1
@Suragch: Depuis que j'ai écrit ceci, un certain nombre de processeurs ont commencé à inclure soit du matériel spécial pour accélérer le calcul SHA, ce qui l'a rendu beaucoup plus compétitif. Cela dit, je doute que votre code soit aussi sûr que vous le pensez - par exemple, les nombres à virgule flottante IEEE ont deux modèles de bits différents (0 et -0) qui devraient produire les mêmes hachages (ils se compareront comme égaux l'un à l'autre. ).
Jerry Coffin
@Jerry Coffin de quelle bibliothèque ai-je besoin pour la fonction rol ()?
thanos.a
@ thanos.a: Je ne suis pas au courant qu'il se trouve dans une bibliothèque, mais lancer le vôtre ne prend qu'une ligne ou deux de code. Décalez un morceau vers la gauche, l'autre vers la droite, et / ou les ensemble.
Jerry Coffin
8

Wikipedia montre une belle fonction de hachage de chaîne appelée Jenkins One At A Time Hash. Il cite également des versions améliorées de ce hachage.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}
RushPL
la source
8

Il existe un certain nombre d'implémentations de table de hachage pour C, de la bibliothèque standard C hcreate / hdestroy / hsearch, à celles de l' APR et de la glib , qui fournissent également des fonctions de hachage prédéfinies. Je recommande fortement de les utiliser plutôt que d'inventer votre propre table de hachage ou fonction de hachage; ils ont été fortement optimisés pour les cas d'utilisation courants.

Si votre jeu de données est statique, cependant, votre meilleure solution est probablement d'utiliser un hachage parfait . gperf générera un hachage parfait pour vous pour un ensemble de données donné.

Nick Johnson
la source
hsearch recherche en comparant les chaînes ou la chaîne ptr address? Je pense que c'est juste la vérification de l'adresse ptr? J'ai essayé d'utiliser différents pointeurs mais la même chaîne de caractères. hsearch échoue en déclarant aucun élément trouvé
mk ..
3

djb2 ​​a 317 collisions pour ce dictionnaire anglais de 466k tandis que MurmurHash n'en a aucune pour les hachages 64 bits, et 21 pour les hachages 32 bits (environ 25 sont à prévoir pour les hachages 32 bits aléatoires de 466k). Ma recommandation est d'utiliser MurmurHash s'il est disponible, il est très rapide, car il prend plusieurs octets à la fois. Mais si vous avez besoin d'une fonction de hachage simple et courte à copier et coller dans votre projet, je vous recommande d'utiliser la version un octet à la fois de murmures:

uint32_t inline MurmurOAAT32 ( const char * key)
{
  uint32_t h(3323198485ul);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  return h;
}

uint64_t inline MurmurOAAT64 ( const char * key)
{
  uint64_t h(525201411107845655ull);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e9955bd1e995;
    h ^= h >> 47;
  }
  return h;
}

La taille optimale d'une table de hachage est - en bref - aussi grande que possible tout en restant en mémoire. Parce que nous ne savons généralement pas ou ne voulons pas rechercher la quantité de mémoire disponible, et que cela pourrait même changer, la taille optimale de la table de hachage est environ 2 fois le nombre attendu d'éléments à stocker dans la table. Allouer beaucoup plus que cela rendra votre table de hachage plus rapide mais avec des rendements décroissants rapidement, ce qui rendra votre table de hachage plus petite que cela la rendra exponentiellement plus lente. C'est parce qu'il y a un compromis non linéaire entre la complexité spatiale et temporelle pour les tables de hachage, avec un facteur de charge optimal de 2-sqrt (2) = 0,58 ... apparemment.

Wolfgang Brehm
la source
2

Premièrement, 40 collisions pour 130 mots hachés à 0..99 sont-ils mauvais? Vous ne pouvez pas vous attendre à un hachage parfait si vous ne prenez pas les mesures nécessaires pour que cela se produise. Une fonction de hachage ordinaire n'aura pas moins de collisions qu'un générateur aléatoire la plupart du temps.

Une fonction de hachage avec une bonne réputation est MurmurHash3 .

Enfin, en ce qui concerne la taille de la table de hachage, cela dépend vraiment du type de table de hachage que vous avez à l'esprit, en particulier, si les buckets sont extensibles ou à un emplacement. Si les buckets sont extensibles, il y a encore un choix: vous choisissez la longueur moyenne des buckets pour les contraintes mémoire / vitesse dont vous disposez.

Pascal Cuoq
la source
1
Le nombre attendu de collisions de hachage est de n - m * (1 - ((m-1)/m)^n) = 57.075.... 40 collisions, c'est mieux que ce à quoi on pouvait s'attendre par hasard (46 à 70 pour un p-score de 0,999). La fonction de hachage en question est plus uniforme que si elle était aléatoire ou si nous assistons à un événement très rare.
Wolfgang Brehm le
2

Bien que djb2, comme présenté sur stackoverflow par cnicutar , c'est presque certainement mieux, je pense que cela vaut la peine de montrer le K&R hachages aussi:

1) Apparemment un algorithme de hachage terrible , tel que présenté dans la 1ère édition de K&R ( source )

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) Probablement un algorithme de hachage assez décent, tel que présenté dans K&R version 2 (vérifié par moi à la page 144 du livre); NB: assurez-vous de supprimer % HASHSIZEde l'instruction return si vous prévoyez de faire le dimensionnement du module à la longueur de votre tableau en dehors de l'algorithme de hachage. Aussi, je vous recommande de faire le retour et le type "hashval" unsigned longau lieu du simple unsigned(int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}

Notez qu'il est clair d'après les deux algorithmes que l'une des raisons pour lesquelles le hachage de la 1ère édition est si terrible est qu'il ne prend PAS en compte l' ordre des caractères de la chaîne et hash("ab")qu'il renvoie donc la même valeur que hash("ba"). Ce n'est cependant pas le cas avec le hachage de la 2e édition, qui renverrait (beaucoup mieux!) Deux valeurs différentes pour ces chaînes.

Les fonctions de hachage GCC C ++ 11 utilisées pour unordered_map(un modèle de table de hachage) et unordered_set(un modèle de jeu de hachage) semblent être les suivantes.

Code:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}
Gabriel Staples
la source
2

J'ai essayé ces fonctions de hachage et j'ai obtenu le résultat suivant. J'ai environ 960 ^ 3 entrées, chacune de 64 octets de long, 64 caractères dans un ordre différent, valeur de hachage 32 bits. Codes d' ici .

Hash function    | collision rate | how many minutes to finish
==============================================================
MurmurHash3      |           6.?% |                      4m15s
Jenkins One..    |           6.1% |                      6m54s   
Bob, 1st in link |          6.16% |                      5m34s
SuperFastHash    |            10% |                      4m58s
bernstein        |            20% |       14s only finish 1/20
one_at_a_time    |          6.16% |                       7m5s
crc              |          6.16% |                      7m56s

Une chose étrange est que presque toutes les fonctions de hachage ont un taux de collision de 6% pour mes données.

Xiaoning Bian
la source
Bien que ce lien puisse répondre à la question, il est préférable d'inclure les parties essentielles de la réponse ici et de fournir le lien pour référence. Les réponses aux liens uniquement peuvent devenir invalides si la page liée change.
thewaywewere le
Évalué pour une bonne table, mettre le code source de chacun de ces hachages dans votre réponse est également essentiel. Sinon, les liens risquent de se rompre et nous n'avons pas de chance.
Gabriel Staples
Le nombre attendu de collisions devrait être de 9,112499989700318E + 7 ou 0,103 * 960³ si les hachages étaient vraiment aléatoires, je n'aurais donc pas été surpris s'ils étaient tous autour de cette valeur, mais 0,0616 * 960³ semble un peu décalé, presque comme si le les hachages sont distribués plus uniformément que ce à quoi on pourrait s'attendre par hasard, et à 64 octets de longueur, cette limite devrait certainement être approchée. Pouvez-vous partager l'ensemble de chaînes que vous avez haché afin que je puisse essayer de le reproduire?
Wolfgang Brehm le
0

Une chose que j'ai utilisée avec de bons résultats est la suivante (je ne sais pas si c'est déjà mentionné parce que je ne me souviens pas de son nom).

Vous précalculez un tableau T avec un nombre aléatoire pour chaque caractère de l'alphabet de votre clé [0,255]. Vous hachez votre clé 'k0 k1 k2 ... kN' en prenant T [k0] xor T [k1] xor ... xor T [kN]. Vous pouvez facilement montrer que c'est aussi aléatoire que votre générateur de nombres aléatoires et qu'il est très faisable sur le plan informatique et si vous rencontrez vraiment une très mauvaise instance avec beaucoup de collisions, vous pouvez simplement répéter le tout en utilisant un nouveau lot de nombres aléatoires.

Michael Nett
la source
Si je ne me trompe pas, cela souffre du même problème que K&R 1st dans la réponse de Gabriel; c'est-à-dire que "ab" et "ba" seront hachés à la même valeur.
Johann Oskarsson