Avez-vous une bonne fonction de hachage pour une table de hachage C++ ?

Question

J'ai besoin d'une implémentation de fonction de hachage orientée vers la performance en C++ pour une table de hachage que je vais coder. J'ai déjà regardé autour de moi et je n'ai trouvé que des questions demandant ce qu'est une bonne fonction de hachage "en général". J'ai envisagé le CRC32 (mais où trouver une bonne implémentation ?) et quelques algorithmes de cryptographie. Ma table, cependant, a des exigences très spécifiques.

Voici à quoi ressemblera la table :

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

El priorité numéro un de ma table de hachage est la recherche rapide (retrieval). L'insertion rapide n'est pas importante, mais elle viendra avec la recherche rapide. L'effacement n'est pas important, et le re-hachage n'est pas quelque chose que j'envisage. Pour gérer les collisions, je vais probablement utiliser chaînage séparé comme décrit aquí . J'ai déjà regardé cet article mais j'aimerais avoir l'avis de ceux qui ont déjà accompli une telle tâche.

Answer 1

Maintenant, en supposant que vous voulez un hachage, et que vous voulez quelque chose rapide comme l'éclair qui fonctionnerait dans votre cas, puisque vos chaînes de caractères ne font que 6 caractères, vous pourriez utiliser cette magie :

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

Le CRC est pour les slowpokes ;)

Explication : Cela fonctionne en coulant le contenu du pointeur de la chaîne pour qu'il "ressemble" à un size_t (int32 ou int64 en fonction de la correspondance optimale pour votre matériel). Ainsi, le contenu de la chaîne de caractères est interprété comme un nombre brut, sans se soucier des caractères, et vous décalez le bit de la précision nécessaire (vous modifiez ce nombre pour obtenir les meilleures performances, j'ai trouvé que 2 fonctionne bien pour hacher des chaînes de caractères de quelques milliers).

De plus, la partie la plus intéressante est que n'importe quel compilateur décent sur du matériel moderne peut hacher une chaîne comme celle-ci en une instruction d'assemblage, difficile de faire mieux ;)

Answer 2

Ce simple polynôme fonctionne étonnamment bien. Je l'ai obtenu de Paul Larson de Microsoft Research qui a étudié une grande variété de fonctions de hachage et de multiplicateurs de hachage.

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt doit être initialisé à un certain au hasard valeur choisie avant la création de la table de hachage pour se défendre contre attaques de tables de hachage . Si ce n'est pas un problème pour vous, utilisez simplement 0.

La taille de la table est également importante, pour minimiser les collisions. On dirait que le vôtre est bon.

Answer 3

Boost.Functional/Hash pourrait vous être utile. Je ne l'ai pas essayé, donc je ne peux pas me porter garant de ses performances.

Boost dispose également d'un Bibliothèque du CRC .

Je chercherais un Boost.Unordered en premier (c'est-à-dire boost::unordered_map<>). Il utilise des cartes de hachage au lieu d'arbres binaires pour les conteneurs.

Je crois que certaines implémentations de la STL ont un conteneur hash_map<> dans l'espace de noms stdext.

Answer 4

Comme vous stockez des mots anglais, la plupart de vos caractères seront des lettres et il n'y aura pas beaucoup de variation dans les deux bits les plus significatifs de vos données. En dehors de cela, je garderais les choses très simples, en utilisant simplement XOR. Après tout, vous ne cherchez pas une force cryptographique mais juste une distribution raisonnablement égale. Quelque chose de ce genre :

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

A part cela, avez-vous regardé std::tr1::hash comme fonction de hachage et/ou std::tr1::unordered_map comme implémentation d'une table de hachage ? Leur utilisation vous épargnerait probablement beaucoup de travail par rapport à l'implémentation de vos propres classes.

Answer 5

La taille de votre table déterminera la taille du hachage que vous devrez utiliser. Vous voudrez bien sûr minimiser les collisions. Je ne suis pas sûr de ce que vous spécifiez par éléments max et capacité (ils me semblent être la même chose). Dans tous les cas, l'un ou l'autre de ces chiffres suggère qu'un hachage de 32 bits serait suffisant. Vous pourriez vous en sortir avec le CRC16 (~65 000 possibilités) mais vous auriez probablement beaucoup de collisions à gérer. D'un autre côté, une collision peut être plus rapide à traiter qu'un hachage CRC32.

Je dirais, allez-y avec CRC32. Vous ne manquerez pas de documentation et d'exemples de code. Puisque vous avez déterminé vos maximums et que la vitesse est une priorité, optez pour un tableau de pointeurs. Utilisez le hachage pour générer un index. En cas de collision, incrémentez l'index jusqu'à ce que vous atteigniez un seau vide rapide et simple.