Fonctions de hachage simples

Essayez sdbm:

hashAddress = 0;
for (counter = 0; word[counter]!='\0'; counter++){
    hashAddress = word[counter] + (hashAddress << 6) + (hashAddress << 16) - hashAddress;
}

Ou djb2:

hashAddress = 5381;
for (counter = 0; word[counter]!='\0'; counter++){
    hashAddress = ((hashAddress << 5) + hashAddress) + word[counter];
}

Ou Adler32:

uint32_t adler32(const void *buf, size_t buflength) {
     const uint8_t *buffer = (const uint8_t*)buf;

     uint32_t s1 = 1;
     uint32_t s2 = 0;

     for (size_t n = 0; n < buflength; n++) {
        s1 = (s1 + buffer[n]) % 65521;
        s2 = (s2 + s1) % 65521;
     }     
     return (s2 << 16) | s1;
}

// ...

hashAddress = adler32(word, strlen(word));

Aucun d'entre eux n'est vraiment génial, cependant. Si vous voulez vraiment de bons hachages, vous avez besoin de quelque chose de plus complexe comme lookup3 par exemple.

Notez qu'une table de hachage devrait avoir beaucoup de collisions dès qu'elle est remplie de plus de 70-80% . Ceci est parfaitement normal et se produira même si vous utilisez un très bon algorithme de hachage. C'est pourquoi la plupart hashtable les implémentations augmentent la capacité de la table de hachage (par exemple capacity * 1.5 ou même capacity * 2) dès que vous ajoutez quelque chose à la table de hachage et que le rapport size / capacity est déjà supérieur à 0,7 à 0,8. Augmenter la capacité signifie qu'une nouvelle table de hachage est créée avec une capacité plus élevée, toutes les valeurs de l'actuelle sont ajoutées à la nouvelle (elles doivent donc toutes être hachées, car leur nouvel index sera différent dans la plupart des cas), le nouveau tableau hastable remplace l'ancien et l'ancien est libéré/Libéré. Si vous planifiez le hachage des mots 1000, une capacité de hashtable d'au moins 1250 recommandé, mieux 1400 ou même 1500.

Les Tables de hachage ne sont pas censées être "remplies à ras bord", du moins pas si elles doivent être rapides et efficaces (elles devraient donc toujours avoir une capacité de réserve). C'est la réduction de la taille des hashtables, elles sont rapides (O(1)), mais elles gaspillent généralement plus d'espace que nécessaire pour stocker les mêmes données dans une autre structure (lorsque vous les stockez en tant que tableau trié, vous aurez seulement besoin d'un capacité de 1000 pour 1000 mots; la réduction est que la recherche ne peut pas être plus rapide que O(log n) dans ce cas). Une hashtable sans collision n'est pas possible dans la plupart des cas de toute façon. À peu près toutes les implémentations de hashtable s'attendent à ce que des collisions se produisent et ont généralement une sorte de moyen de les traiter (généralement les collisions rendent la recherche un peu plus lente, mais la hashtable fonctionnera toujours et battra d'autres structures de données dans de nombreux cas).

Notez également que si vous utilisez un assez bon fonction de hachage, il n'y a pas d'exigence, mais même pas d'avantage, si la table de hachage a une puissance de capacité 2 Si vous recadrez des valeurs de hachage en utilisant modulo (%) à la fin. La raison pour laquelle de nombreuses implémentations hashtable utilisent toujours la puissance des capacités 2 est que elles n'utilisent pas modulo , mais QU'elles utilisent AND (&) pour le recadrage car une opération AND est parmi les opérations les plus rapides que vous trouverez sur la plupart des processeurs (modulo n'est jamais plus rapide que et, dans le meilleur tout aussi rapide, dans la plupart des cas, il est beaucoup plus lent). Si votre hashtable utilise une puissance de 2 tailles, vous pouvez remplacer n'importe quel module par une opération AND:

x % 4  == x & 3
x % 8  == x & 7
x % 16 == x & 15
x % 32 == x & 31
...

, Cela ne fonctionne que pour une puissance de 2 tailles, cependant. Si vous utilisez modulo, la puissance de 2 tailles ne peut acheter quelque chose, si le hachage est un très mauvais hachage avec une très mauvaise "distribution de bits". Une mauvaise distribution de bits est généralement causée par des hachages qui n'utilisent aucun type de décalage de bits (>> ou <<) ou toute autre opération qui aurait un effet comme Bit shifting.

J'ai créé une implémentation de lookup3 dépouillée pour Vous:

#include <stdint.h>
#include <stdlib.h>

#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);  c += b; \
  b -= a;  b ^= rot(a, 6);  a += c; \
  c -= b;  c ^= rot(b, 8);  b += a; \
  a -= c;  a ^= rot(c,16);  c += b; \
  b -= a;  b ^= rot(a,19);  a += c; \
  c -= b;  c ^= rot(b, 4);  b += a; \
}

#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c,4);  \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

uint32_t lookup3 (
  const void *key,
  size_t      length,
  uint32_t    initval
) {
  uint32_t  a,b,c;
  const uint8_t  *k;
  const uint32_t *data32Bit;

  data32Bit = key;
  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;

  while (length > 12) {
    a += *(data32Bit++);
    b += *(data32Bit++);
    c += *(data32Bit++);
    mix(a,b,c);
    length -= 12;
  }

  k = (const uint8_t *)data32Bit;
  switch (length) {
    case 12: c += ((uint32_t)k[11])<<24;
    case 11: c += ((uint32_t)k[10])<<16;
    case 10: c += ((uint32_t)k[9])<<8;
    case 9 : c += k[8];
    case 8 : b += ((uint32_t)k[7])<<24;
    case 7 : b += ((uint32_t)k[6])<<16;
    case 6 : b += ((uint32_t)k[5])<<8;
    case 5 : b += k[4];
    case 4 : a += ((uint32_t)k[3])<<24;
    case 3 : a += ((uint32_t)k[2])<<16;
    case 2 : a += ((uint32_t)k[1])<<8;
    case 1 : a += k[0];
             break;
    case 0 : return c;
  }
  final(a,b,c);
  return c;
}

Ce code n'est pas aussi optimisé pour les performances que le code original, c'est donc beaucoup plus simple. Il n'est pas aussi portable que le code original, mais il est portable pour toutes les principales plates-formes grand public utilisées aujourd'hui. Il ignore également complètement le CPU endian, mais ce n'est pas vraiment un problème, il fonctionnera sur les gros et petits processeurs endian. Il suffit de garder à l'esprit que ce ne sera pas calculer le même hachage pour les mêmes données sur les processeurs Big et little endian, mais ce n'est pas une exigence; il calculera un bon hachage sur les deux types de processeurs et il est seulement important qu'il calcule toujours le même hachage pour les mêmes données d'entrée sur une seule machine.

Vous utiliseriez cette fonction comme suit:

unsigned int stringToHash(char *word, unsigned int hashTableSize){
  unsigned int initval;
  unsigned int hashAddress;

  initval = 12345;
  hashAddress = lookup3(word, strlen(word), initval);
  return (hashAddress%hashTableSize);
  // If hashtable is guaranteed to always have a size that is a power of 2,
  // replace the line above with the following more effective line:
  //     return (hashAddress & (hashTableSize - 1));
}

Vous vous demandez ce que initval est. Eh bien, c'est ce que vous voulez qu'il soit. On pourrait appeler cela un sel. Cela influencera les valeurs de hachage, mais les valeurs de hachage n'obtiendront pas meilleure ou pire en qualité à cause de cela (du moins pas dans le cas Moyen, cela peut conduire à plus ou moins de collisions pour des données très spécifiques). Par exemple, vous pouvez utiliser des valeurs initval différentes si vous voulez hacher les mêmes données deux fois, mais chaque fois devrait produire une valeur de hachage différente (il n'y a aucune garantie que ce sera le cas, mais il est plutôt probable que initval soit différent; si cela crée la même valeur, ce serait une coïncidence très malchanceuse que vous Il n'est pas il est conseillé d'utiliser des valeurs initval différentes lors du hachage de données pour la même table de hachage (cela provoquera plutôt plus de collisions en moyenne). Une autre utilisation pour initval est si vous voulez combiner un hachage avec d'autres données, auquel cas le hachage déjà existant devient initval lors du hachage des autres données (donc les autres données ainsi que le hachage précédent influencent le résultat de la fonction de hachage). Vous pouvez même définir initval sur 0 si vous le souhaitez ou choisir une valeur aléatoire lorsque la table de hachage est créée (et toujours utiliser cette valeur aléatoire pour cette instance de hashtable, mais chaque hashtable a sa propre valeur aléatoire).

Une note sur les collisions:

Les Collisions ne sont généralement pas un problème aussi énorme dans la pratique, il ne paie généralement pas de gaspiller des tonnes de mémoire juste pour les éviter. La question est plutôt de savoir comment vous allez les traiter de manière efficace.

Vous avez dit que vous traitez actuellement avec 9000 mots. Si vous utilisiez un tableau non trié, trouver un mot dans le array aura besoin de 4500 comparaisons en moyenne. Sur mon système, les comparaisons de chaînes 4500 (en supposant que les mots mesurent entre 3 et 20 caractères) nécessitent 38 microsecondes (0,000038 secondes). Donc, même un algorithme aussi simple et inefficace est assez rapide pour la plupart des fins. En supposant que vous triez la liste de mots et utilisez une recherche binaire, trouver un mot dans le tableau n'aura besoin que de 13 comparaisons en moyenne. 13 les comparaisons sont proches de rien en termes de temps, c'est trop peu pour même comparer de manière fiable. Donc, si trouver un mot dans une table de hachage nécessite des comparaisons 2 à 4, Je ne perdrais même pas une seule seconde sur la question de savoir si cela peut être un énorme problème de performance.

Dans votre cas, une liste triée avec recherche binaire peut même battre un hashtable de loin. Bien sûr, 13 comparaisons besoin de plus de temps 2-4 comparaisons, cependant, dans le cas d'une table de hachage, vous devez d'abord hachage des données d'entrée pour effectuer une recherche. Le hachage seul peut déjà prendre plus de temps que les comparaisons 13! Lemieux le hachage, le plus long Il faudra pour que la même quantité de données soit hachée. Ainsi, une table de hachage ne rapporte que si vous avez une quantité vraiment énorme de données ou si vous devez mettre à jour les données fréquemment (par exemple, Ajouter/Supprimer constamment des mots dans/de la table, car ces opérations sont moins coûteuses pour une table de hachage que pour une liste triée). Le fait qu'un hashatble soit O(1) signifie seulement que quelle que soit sa taille, une recherche sera env. toujours besoin de la même quantité de temps. O(log n) cela signifie seulement que la recherche augmente logarithmiquement avec le nombre de mots, cela signifie plus de mots, une recherche plus lente. Pourtant, la notation Big-O ne dit rien sur la vitesse absolue! C'est un grand malentendu. On ne dit pas qu'un algorithme O(1) fonctionne toujours plus vite qu'un algorithme O(log n). La notation Big-O vous indique seulement que si l'algorithme O(log n) est plus rapide pour un certain nombre de valeurs et que vous continuez à augmenter le nombre de valeurs, l'algorithme O(1) dépassera certainement l'algorithme O(log n) à un moment donné, mais votre nombre de mots actuel peut être bien en dessous de ce point. Sans benchmarking les deux approches, vous ne pouvez pas dire laquelle est la plus rapide en regardant simplement la notation Big-O.

Retour aux collisions. Que devez-vous faire si vous rencontrez une collision? Si le nombre de collisions est petit, et ici Je ne veux pas dire le nombre total de collisions (le nombre de mots qui entrent en collision dans la table de hachage) mais celui par index (le nombre de mots stockés dans la même table de hachage index, donc dans votre cas peut-être 2-4), l'approche la plus simple est de les stocker en tant que liste liée. S'il n'y a pas eu de collision jusqu'à présent pour cet index de table, il n'y a qu'une seule paire clé/valeur. S'il y a eu une collision, il existe une liste liée de paires clé/valeur. Dans ce cas, votre code doit parcourir la liste liée et vérifier chacune des clés et renvoyer la valeur si elle correspond. En passant par vos chiffres, cette liste liée n'aura pas plus de 4 entrées et faire 4 comparaisons est insignifiant en termes de la performance. Donc, trouver l'index est O(1), trouver la valeur (ou détecter que cette clé n'est pas dans la table) est O(n), mais ici n est seulement le nombre d'entrées de liste liées (donc c'est 4 au plus).

Si le nombre de collisions augmente, une liste liée peut ralentir et vous pouvez également stocker un tableau trié de paires clé/valeur de taille dynamique, ce qui permet des recherches de O(log n) et encore une fois, n est seulement le nombre de clés dans ce tableau, pas de toutes les clés dans la table hastable. Même si il y a eu 100 collisions à un index, trouver la bonne paire clé / valeur prend au plus 7 comparaisons. C'est toujours près à rien. Malgré le fait que si vous avez vraiment 100 collisions à un index, votre algorithme de hachage n'est pas adapté à vos données clés ou la table de hachage est beaucoup trop petite. L'inconvénient d'un tableau trié de taille dynamique est que l'Ajout/Suppression de clés est un peu plus de travail que dans le cas d'une liste liée (en termes de code, pas nécessairement en termes de performance). Donc, en utilisant une liste liée est généralement suffisante si vous maintenez le nombre de collisions assez bas et qu'il est presque trivial d'implémenter une telle liste liée vous-même en C et de l'ajouter à une implémentation Hashtable existante.

La plupart des implémentations hashtable que j'ai semblent utiliser un tel "repli sur une structure de données alternative" pour faire face aux collisions. L'inconvénient est que ceux ci nécessitent un peu plus de mémoire pour stocker la structure de données alternative et un peu plus de code pour rechercher également des clés structure. Il existe également des solutions qui stockent les collisions dans la table de hachage elle-même et qui ne nécessitent aucune mémoire supplémentaire. Cependant, ces solutions ont quelques inconvénients. Le premier inconvénient est que chaque collision augmente les chances de collisions encore plus que plus de données sont ajoutées. Le deuxième inconvénient est que si les temps de recherche des clés diminuent linéairement avec le nombre de collisions jusqu'à présent (et comme je l'ai déjà dit, chaque collision entraîne encore plus de collisions à mesure que les données sont ajoutées), les temps de recherche pour les clés qui ne sont pas dans la table de hachage diminuent encore pire et à la fin, si vous effectuez une recherche pour une clé qui n'est pas dans la table de hachage (mais vous ne pouvez pas savoir sans effectuer la recherche), la recherche peut prendre aussi longtemps qu'une recherche linéaire sur toute la table de hachage (BEURK!!!). Donc, si vous pouvez épargner la mémoire supplémentaire, optez pour une structure alternative pour gérer les collisions.