Quel est le meilleur algorithme de hachage à utiliser sur une chaîne stl lorsque vous utilisez hash map?

j'ai travaillé avec Paul Larson de Microsoft Research sur certaines implémentations hashtable. Il a étudié un certain nombre de chaînes de fonctions de hachage sur une variété d'ensembles de données et a constaté qu'un simple multiplier par 101 et ajouter boucle fonctionnait étonnamment bien.

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

D'un de mes vieux codes:

/* 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;
}

Son rapide. Vraiment flippant rapide.

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

cela 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 implémentations CRC32 sont faciles à trouver sur le net.

Edit: 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.

j'ai utilisé le hachage de Jenkins pour écrire une bibliothèque de filtre de fleur, il a une grande performance.

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

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

si vous hachez un ensemble fixe de mots, la meilleure fonction de hachage est souvent un fonction de hachage parfait . Cependant, ils exigent généralement que l'ensemble des mots que vous essayez de hachage est connu au moment de la compilation. La détection de mots-clés dans un lexer (et la traduction de mots-clés en tokens) est une pratique courante des fonctions de hachage parfait généré avec des outils tels que gperf . Un hachage parfait vous permet également de remplacer hash_map avec un simple tableau ou vector .

si vous n'utilisez pas un ensemble fixe de mots, alors évidemment cela ne s'applique pas.

une suggestion classique pour un hachage de chaîne est de passer à travers les lettres une par une en ajoutant leurs valeurs ASCII/unicode à un accumulateur, chaque fois en multipliant l'accumulateur par un nombre premier. (permettant le débordement sur la valeur de hachage)

  template <> struct myhash{};

  template <> struct myhash<string>
    {
    size_t operator()(string &to_hash) const
      {
      const char * in = to_hash.c_str();
      size_t out=0;
      while(NULL != *in)
        {
        out*= 53; //just a prime number
        out+= *in;
        ++in;
        }
      return out;
      }
    };

  hash_map<string, int, myhash<string> > my_hash_map;

il est difficile d'obtenir plus vite que cela sans jeter des données. Si vous savez que vos chaînes de caractères peuvent être différenciées par seulement quelques caractères et pas tout leur contenu, Vous pouvez faire plus vite.

Vous pourriez essayer de mieux cacher la valeur de hachage en créant une nouvelle sous-classe de basic_string qui se souvient de sa valeur de hachage, si la valeur est calculée trop souvent. hash_map devrait le faire en interne.

j'ai fait une petite recherche, et chose drôle, le petit algorithme de Paul Larson s'est montré ici http://www.strchr.com/hash_functions comme ayant le moins de collisions de toutes testées dans un certain nombre de conditions, et il est très rapide pour un qu'il est déroulé ou table conduite.

Larson étant le simple multiplier par 101 et ajouter boucle ci-dessus.

Python 3.4 inclut un nouvel algorithme de hachage basé sur SipHash . PEP 456 est très instructif.

si vos chaînes sont en moyenne plus longues qu'une seule ligne de cache, mais que leur longueur+préfixe sont raisonnablement uniques, pensez à ne Haser que la longueur+8/16 des premiers caractères. (La longueur est contenue dans le std::string objet lui-même et donc pas cher à lire)

à Partir de Fonctions de Hachage tout le chemin vers le bas :

MurmurHash a obtenu tout à fait populaire, au moins dans les cercles de développeur de jeu, comme une "fonction de hachage général".

c'est un bon choix, mais voyons plus tard si nous pouvons généralement faire mieux. Un autre bon choix, en particulier si vous en savez plus sur vos données que "il va être un nombre inconnu d'octets", est de lancer vos propres (par exemple voir Won Les réponses de Chun, ou les xxHash/Murmur modifiés de Rune qui sont spécialisés pour les touches de 4 octets, etc.). Si vous connaissez vos données, essayez toujours de voir si cette connaissance peut être utilisée pour un bon effet!

sans plus d'information je recommande MurmurHash comme un but général fonction de hachage non-cryptographique . Pour les petites cordes (de la taille de l'identificateur moyen dans les programmes) le très simple et célèbre djb2 et FNV sont très bons.

ici (tailles de données < 10 octets) nous pouvons voir que l'intelligence ILP d'autres algorithmes ne peut pas se montrer, et la super-simplicité de FNV ou djb2 gagner en performance.

djb2

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;
}

FNV-1

hash = FNV_offset_basis
for each byte_of_data to be hashed
     hash = hash × FNV_prime
     hash = hash XOR byte_of_data
return hash

FNV-1A

hash = FNV_offset_basis
for each byte_of_data to be hashed
     hash = hash XOR byte_of_data
     hash = hash × FNV_prime
return hash

une note sur la sécurité et la disponibilité

peuvent rendre votre code vulnérable aux attaques par déni de service. Si un attaquant est capable de forcer votre serveur à gérer trop de collisions, votre serveur peut ne pas être capable de gérer les requêtes.

certaines fonctions de hachage comme MurmurHash accepter une graine que vous pouvez fournir pour réduire drastiquement la la capacité des attaquants de prédire les hachages que le logiciel de votre serveur Produit. Gardez cela à l'esprit.