Quel est le meilleur algorithme de hachage à utiliser sur une chaîne stl lors de l'utilisation de hash_map?

Question

J'ai constaté que la fonction de hachage standard sur le VS2005 est terriblement lente lorsque vous essayez d'obtenir des résultats de haute performance. Quels sont de bons exemples d’algorithmes de hachage rapides et efficaces qui devraient permettre d’éviter la plupart des collisions?

Answer 1

J'ai travaillé avec Paul Larson de Microsoft Research sur certaines implémentations de hashtable. Il a étudié un certain nombre de fonctions de hachage de chaîne sur divers jeux de données et a constaté qu'une simple multiplication par 101 et une boucle add fonctionnaient étonnamment bien.

 unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}
 

Answer 2

De mon ancien code:

 /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}
 

C'est rapide. Freaking vraiment rapide.

Answer 3

Boost a une bibliothèque boost :: hash qui peut fournir quelques fonctions de base pour les types les plus courants.

Answer 4

Qui dépend toujours de votre ensemble de données.

J'ai eu de très bons résultats en utilisant le CRC32 de la chaîne. Fonctionne très bien avec un large éventail de différents ensembles.

Beaucoup de bonnes CRC32 implémentations sont faciles à trouver sur le net.

Edit: j'ai Presque oublié: Cette page a une belle fonction de hachage fusillade avec les chiffres de la performance et de test des données:

http://smallcode.weblogs.us/ <-- en bas de la page.

Answer 5

J'ai utilisé le hachage Jenkins pour écrire une bibliothèque de filtres Bloom, qui offre d'excellentes performances.

Les détails et le code sont disponibles ici: http://burtleburtle.net/bob/c/lookup3.c

C’est ce que Perl utilise pour son opération de hachage, fwiw.