Avoir une bonne fonction de hachage pour un C++ table de hachage?

Maintenant assumming vous voulez une table de hachage, et que vous voulez quelque chose de ultra-rapide qui fonctionne dans votre cas, parce que vos cordes sont à seulement 6 caractères, vous pouvez utiliser cette magic:

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

CRC est pour slowpokes 😉

Explication:
Cela fonctionne en jetant le contenu du pointeur de la chaîne pour "ressembler à" un size_t (int32 ou int64 basé sur la meilleure correspondance pour votre matériel). Si le contenu de la chaîne est interprétée comme un nombre brut, pas de soucis sur les personnages, et de plus, vous ensuite de décalage de bit-ce la précision nécessaire (vous ajuster ce nombre pour la meilleure performance, j'ai trouvé 2 qui fonctionne bien pour le hachage des chaînes de caractères dans un ensemble de quelques milliers).

Également la partie vraiment bien est tout bon compilateur sur le matériel moderne sera hash d'une chaîne comme celle-ci dans 1 instructions de montage, difficile de faire mieux que ça 😉

Coup de pouce.Fonctionnel/Hash pourraient vous être utiles. Je n'ai pas essayé, donc je ne peux pas se porter garant de ses performances.

Boost a aussi un CRC bibliothèque.

Je regarde un Coup de pouce.Non ordonnée en premier (boost::unordered_map<>). Il utilise le hachage des cartes à la place des arbres binaires pour les conteneurs.

Je crois que certains STL implémentations ont classes hash_map<> container dans le stdext espace de noms.

Puisque vous stockez les mots en anglais, la plupart de vos personnages seront des lettres et il n'y aura pas beaucoup de variation dans la plus importante des deux bits de vos données. De plus, j'aimerais garder très simple, il suffit à l'aide de XOR. Après tout, vous n'êtes pas à la recherche de la robustesse cryptographique, mais juste pour un raisonnablement même de la distribution. Quelque chose le long de ces lignes:

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

En plus de cela, avez-vous regardé std::tr1::hachage une fonction de hachage et/ou std::tr1::unordered_map comme une mise en place d'une table de hachage? L'utilisation de ces sera probablement sauver beaucoup de travail opposition à la mise en œuvre de vos propres classes.

Comment parler de quelque chose de simple:

//Initialize hash lookup so that it maps the characters
//in your string to integers between 0 and 31
int hashLookup[256];

//Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

Cela suppose 32 bits entiers. Il utilise 5 bits par caractère, de sorte que la valeur de hachage a seulement 30 bits en elle. Vous pouvez résoudre ce problème, peut-être, par la génération de six bits pour la première fois une ou deux caractères. Si vous jeu de caractères est assez petit, vous pourriez ne pas avoir besoin de plus de 30 bits.

Depuis C++11, C++ a fourni un std::hash< string >( string ). C'est probablement une bonne fonction de hachage qui fournit un une bonne répartition de hash-codes pour la plupart des chaînes de caractères.

En outre, si vous envisagez de mettre en œuvre une table de hachage, vous devriez maintenant être vu à l'aide d'un C++ std::unordered_map à la place.