fonction de hachage pour la chaîne

D'abord, vous faites généralement pas veulent utiliser un hash cryptographique pour une table de hash. Un algorithme qui est très rapide par les normes cryptographiques est toujours excessivement lent par les normes de table de hachage.

Deuxièmement, vous voulez vous assurer que chaque morceau de l'entrée peut/va affecter le résultat. Une façon facile de faire cela est de tourner le résultat courant par un certain nombre de bits, puis XOR le code de hachage courant avec le courant octet. Répétez jusqu'à ce que vous atteigniez le bout de la corde. Notez que vous faites généralement et non veulent que la rotation soit un multiple Pair de la taille des octets soit.

par exemple, en supposant le cas commun des octets 8 bits, vous pourriez tourner de 5 bits:

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

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

modifier: notez également que 10000 fentes est rarement un bon choix pour une taille de table de hachage. Vous voulez généralement l'une des deux choses: vous voulez soit un nombre premier que la taille (requis pour assurez l'exactitude avec certains types de résolution de hachage) ou bien une puissance de 2 (de sorte que la réduction de la valeur à la bonne portée peut être fait avec un masque de bits simple).

il existe un certain nombre d'implémentations hashtable existantes pour C, à partir de la bibliothèque C Standard hcreate/hdestroy/hsearch, à ceux dans les APR et glib , qui fournissent également des fonctions de hachage prébuilt. Je recommande fortement l'utilisation de ceux-ci plutôt que d'inventer votre propre hashtable ou fonction de hachage; ils ont été fortement optimisés pour les cas d'utilisation commune.

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

Wikipedia montre une belle chaîne de hachage fonction appelée Jenkins, Un À la Fois de Hachage. 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;
}

D'abord, 40 collisions pour 130 mots hachés à 0..99 mauvais? Vous ne pouvez pas vous attendre à un hachage parfait si vous ne prenez pas des mesures spécifiques 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 hash, il dépend vraiment quel type de table de hash vous avez dans attention, surtout, si les seaux sont extensibles ou à une fente. Si les seaux sont extensibles, là encore il y a un choix: vous choisissez la longueur moyenne des seaux pour les contraintes mémoire/vitesse que vous avez.

j'ai essayé ces fonctions de hachage et a obtenu le résultat suivant. J'ai environ 960^3 entrées, chacune 64 octets de long, 64 caractères dans un ordre différent, valeur de hachage 32bit. Codes de 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.

si djb2 , comme présenté sur stackoverflow par cnicutar , est presque certainement mieux, je pense qu'il est intéressant de montrer le K&R hashes too:

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

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

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

    return hash;
}

2) probablement un hash assez décent algorithme, tel que présenté dans K&R version 2 (vérifié par moi à la P. 144 du livre); NB: assurez-vous de supprimer % HASHSIZE de la déclaration de retour si vous prévoyez de faire le dimensionnement de module à la longueur de votre tableau en dehors de l'algorithme de hachage. En outre, je vous recommande de faire le retour et "hashval" type unsigned long au lieu de la simple unsigned (int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '"151910920"'; 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 la 1ère édition de hash est si terrible est parce qu'il ne prend pas en considération le caractère de chaîne ordre , de sorte que hash("ab") retournerait donc la même valeur que hash("ba") . C'est pas donc avec la 2e édition hash, cependant, qui serait (beaucoup mieux!) retour 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 (le hachage est un modèle de jeu) semblent être comme suit.

• ce est une réponse partielle à la question de quelles sont les fonctions de hachage GCC c++11 utilisées , en indiquant que GCC utilise une implémentation de "MurmurHashUnaligned2", par Austin Appleby ( http://murmurhash.googlepages.com / ).
• dans le dossier "gcc / libstdc++-v3/libsupc++/hash_bytes.cc", ici ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++ - v3 / libsupc++/hash_bytes.cc ), j'ai trouvé les implémentations. Voici celui de la valeur de retour" 32-bit size_t", par exemple (tiré le 11 août 2017):

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

une chose que j'ai utilisée avec de bons résultats est la suivante (Je ne sais pas si elle est déjà mentionnée 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 dans 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 nombre aléatoire et son calcul très faisable et si vraiment vous lancer dans un 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.