Fonctions de hachage simples

J’essaie d’écrire un programme en C qui utilise une table de hachage pour stocker différents mots et je pourrais utiliser de l’aide.

Tout d’abord, je crée une table de hachage avec la taille d’un nombre premier qui se rapproche le plus du nombre de mots que je dois stocker, puis j’utilise une fonction de hachage pour trouver une adresse pour chaque mot. J’ai commencé avec la fonction la plus simple, en additionnant les lettres, ce qui a abouti à une collision de 88%. Ensuite, j’ai commencé à expérimenter la fonction et découvert que quoi que je change, les collisions ne sont pas inférieures à 35%. En ce moment j’utilise

unsigned int ssortingngToHash(char *word, unsigned int hashTableSize){ unsigned int counter, hashAddress =0; for (counter =0; word[counter]!='\0'; counter++){ hashAddress = hashAddress*word[counter] + word[counter] + counter; } return (hashAddress%hashTableSize); } 

ce qui est juste une fonction aléatoire que je suis venu avec, mais cela me donne les meilleurs résultats – environ 35% de collision.

Je lis des articles sur les fonctions de hachage depuis quelques heures et j’ai essayé d’en utiliser quelques-uns simples, comme djb2, mais ils m’ont tous donné des résultats encore pires. C’est bien pire, mais j’attendais quelque chose de mieux que de pire. Je ne sais pas non plus utiliser certains des autres, plus complexes, tels que le murmure2, car je ne sais pas quels sont les parameters (clé, len , graine) ils prennent en sont.

Est-il normal d’avoir plus de 35% de collisions, même en utilisant le djb2, ou est-ce que je fais quelque chose de mal? Quelles sont les valeurs clés, len et seed?

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

Aucune de ces choses n'est vraiment géniale, cependant. Si vous voulez vraiment de bonnes hachages, vous avez besoin de quelque chose de plus complexe comme lookup3 par exemple.

Notez qu'une hashtable devrait avoir beaucoup de collisions dès qu'elle sera remplie à 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 des implémentations de table de hachage 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 dépasse déjà 0,7 à 0,8. L'augmentation de la capacité signifie qu'une nouvelle table de hachage est créée avec une capacité supérieure, toutes les valeurs de la valeur actuelle sont ajoutées à la nouvelle (elles doivent donc toutes être réorganisé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 envisagez de hacher 1000 mots, la capacité de la table de hachage est au minimum de 1250, mieux de 1400 voire 1500.

Les tables de hachage ne sont pas censées être "remplies à craquer", du moins pas si elles doivent être rapides et efficaces (elles doivent donc toujours disposer d'une capacité disponible). C’est la réduction des hashtables, elles sont rapides ( O(1) ), mais elles gaspillent généralement plus d’espace que ce qui serait nécessaire pour stocker les mêmes données dans une autre structure (lorsque vous les stockez sous la forme d’un tableau sortingé, 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. Pratiquement toutes les implémentations de hashtable s'attendent à des collisions et ont généralement une façon de les gérer (généralement, les collisions ralentissent la recherche, mais la hashtable fonctionnera toujours et dépassera encore d'autres structures de données).

Notez également que si vous utilisez une assez bonne fonction de hachage, il n’ya aucune exigence, même pas un avantage, si la hashtable a une puissance de 2, si vous recadrez des valeurs de hachage en utilisant modulo ( % ). La plupart des implémentations de table de hachage utilisent systématiquement une puissance de 2 capacités, car elles n'utilisent pas modulo . Elles utilisent plutôt AND ( & ) pour le rognage, car une opération AND fait partie des opérations les plus rapides que vous trouverez sur la plupart des processeurs (modulo n'est jamais plus rapide que ET, dans le meilleur des cas, ce serait tout aussi rapide, dans la plupart des cas, il est beaucoup plus lent). Si votre table de hachage utilise deux tailles de puissance, 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, une puissance de 2 tailles ne peut acheter que quelque chose, si le hash est un très mauvais hash avec une très mauvaise "dissortingbution de bits". Une mauvaise dissortingbution 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 ayant un effet similaire à celui-ci.

J'ai créé une implémentation simplifiée de lookup3 pour vous:

 #include  #include  #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é que le code original en termes de performances. Il est donc beaucoup plus simple. Il n’est pas aussi portable que le code original, mais il est portable sur toutes les grandes plates-formes grand public actuellement utilisées. Il ignore également complètement le processeur endian, mais ce n’est pas vraiment un problème, cela fonctionnera sur les gros et petits processeurs endian. Gardez simplement à l'esprit qu'il ne calculera pas la même valeur de hachage pour les mêmes données sur les processeurs de grande et de petite taille, mais ce n'est pas une obligation; il calculera une bonne valeur de hachage sur les deux types de CPU et il est seulement important de toujours calculer la même valeur de hachage pour les mêmes données d'entrée sur une seule machine.

Vous utiliseriez cette fonction comme suit:

 unsigned int ssortingngToHash(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 qu'est initval . Eh bien, c'est ce que vous voulez que ce soit. Vous pourriez l'appeler un sel. Cela influera sur les valeurs de hachage. Cependant, la qualité des valeurs de hachage ne sera ni meilleure ni pire (du moins pas dans la moyenne, cela peut conduire à plus ou moins de collisions pour des données très spécifiques). Par exemple, vous pouvez utiliser différentes valeurs initval si vous souhaitez hacher les mêmes données deux fois, mais chaque fois doit produire une valeur de hachage différente (rien ne garantit qu'elle le fera, mais il est fort probable que initval soit différent, s'il crée la même valeur , ce serait une coïncidence très malchanceuse que vous devez traiter cela comme une sorte de collision). Il est déconseillé d'utiliser des valeurs initval différentes lors du hachage de données pour la même table de hachage (cela entraînerait plutôt plus de collisions en moyenne). Une autre utilisation d’initval est si vous souhaitez combiner un hachage avec d’autres données. Dans ce cas, le hachage déjà existant devient initval lors du hachage des autres données (de sorte que les deux données, ainsi que le hachage précédent, influent sur le résultat du hachage. une fonction). Vous pouvez même définir initval sur 0 si vous le souhaitez ou choisir une valeur aléatoire lors de la création de la table de hachage (et utilisez toujours cette valeur aléatoire pour cette instance de hashtable, chaque hashtable ayant cependant sa propre valeur aléatoire).

Une note sur les collisions:

Les collisions ne sont généralement pas un si gros problème dans la pratique, il n'est généralement pas rentable de gaspiller des tonnes de mémoire rien que pour les éviter. La question est plutôt de savoir comment vous allez les gérer de manière efficace.

Vous avez dit que vous avez actuellement 9 000 mots. Si vous utilisiez un tableau non sortingé, la recherche d'un mot dans le tableau nécessitera en moyenne 4500 comparaisons. Sur mon système, 4500 comparaisons de chaînes (en supposant que les mots comportent entre 3 et 20 caractères) nécessitent 38 microsecondes (0,000038 seconde). Ainsi, même un algorithme aussi simple et inefficace est suffisamment rapide pour la plupart des applications. En supposant que vous sortingiez la liste de mots et utilisiez une recherche binary, la recherche d'un mot dans le tableau ne nécessite que 13 comparaisons en moyenne. 13 comparaisons sont presque nulles en termes de temps, c’est trop peu pour que nous puissions nous comparer de manière fiable. Donc, si trouver un mot dans une table de hachage nécessite 2 à 4 comparaisons, je ne perdrais même pas une seule seconde sur la question de savoir si cela pouvait poser un énorme problème de performance.

Dans votre cas, une liste sortingée avec recherche binary peut même battre de loin une table de hachage. Bien sûr, 13 comparaisons nécessitent plus de temps que 2 à 4 comparaisons, cependant, dans le cas d’une table de hachage, vous devez d’abord hacher les données d’entrée pour pouvoir effectuer une recherche. Le hachage seul peut déjà prendre plus de 13 comparaisons! Plus le hachage est bon, plus il faudra de temps pour que la même quantité de données soit hachée. Ainsi, une table de hachage ne paie en termes de performances que si vous avez une quantité de données vraiment énorme ou si vous devez mettre à jour les données fréquemment (par exemple, append / supprimer constamment des mots dans / de la table, car ces opérations sont moins coûteuses qu'elles ne le sont. sont pour une liste sortingée). Le fait qu'un hashatble soit O(1) signifie seulement que quelle que soit sa taille, une recherche aura env. toujours besoin du même temps. O(log n) signifie uniquement que la recherche croît logarithmiquement avec le nombre de mots, ce qui signifie plus de mots, recherche plus lente. Pourtant, la notation Big-O ne dit rien sur la vitesse absolue! C'est un gros malentendu. On ne dit pas qu'un algorithme O(1) 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 le nombre actuel de mots peut être très inférieur à ce point. Sans comparer les deux approches, vous ne pouvez pas dire laquelle est la plus rapide en regardant simplement la notation Big-O.

Retour aux collisions. Que devriez-vous faire en cas de collision? Si le nombre de collisions est faible et que je ne parle pas ici du nombre total de collisions (le nombre de mots qui entrent en collision dans la table de hachage), mais de la valeur par index (le nombre de mots stockés dans le même index de hachage, donc dans votre cas 2-4), l’approche la plus simple consiste à les stocker sous forme de liste chaîné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. En cas de collision, il existe une liste chaînée de paires clé / valeur. Dans ce cas, votre code doit parcourir la liste liée, vérifier chacune des clés et renvoyer la valeur si elle correspond. Sur la base de vos chiffres, cette liste chaînée ne contiendra pas plus de 4 entrées et 4 comparaisons sont insignifiantes en termes de performances. Donc, trouver l’indice est O(1) , trouver la valeur (ou détecter que cette clé n’est pas dans la table) est O(n) , mais ici n n’est que le nombre d’entrées de liste liées (donc au maximum 4) .

Si le nombre de collisions augmente, une liste chaînée peut devenir trop lente et vous pouvez également stocker un tableau sortingé de taille dynamic, composé de paires clé / valeur, qui permet la recherche de O(log n) Là encore, n correspond uniquement au nombre de clés. dans ce tableau, pas de toutes les clés dans le hastable. Même s'il y avait 100 collisions à un indice, la recherche de la paire clé / valeur appropriée prend au plus 7 comparaisons. C'est encore proche de rien. Malgré le fait que si vous avez réellement 100 collisions à un index, votre algorithme de hachage n'est pas adapté à vos données clés ou la capacité de la table de hachage est beaucoup trop petite. L'inconvénient d'un tableau sortingé de taille dynamic réside dans le fait que l'ajout / la suppression de clés représente un peu plus de travail que dans le cas d'une liste chaînée (en termes de code, pas nécessairement de performances). Donc, utiliser une liste chaînée est généralement suffisant si vous maintenez un nombre de collisions suffisamment faible et qu'il est presque sortingvial d'implémenter vous-même une telle liste chaînée en C et l'append à une implémentation de table de hachage existante.

La plupart des implémentations de table de hachage semblent utiliser un tel "recours à une structure de données alternative" pour traiter les collisions. L'inconvénient est que cela nécessite 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 dans cette structure. Il existe également des solutions qui stockent les collisions à l'intérieur de la table de hachage et ne nécessitent aucune mémoire supplémentaire. Cependant, ces solutions présentent quelques inconvénients. Le premier inconvénient est que chaque collision augmente les chances d’augmenter le nombre de collisions à mesure que de nouvelles données sont ajoutées. Le deuxième inconvénient est que, bien que 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 lorsque des données sont ajoutées), les temps de recherche des clés qui ne sont pas dans la table de hachage diminuent encore plus mal. et à la fin, si vous effectuez une recherche pour une clé qui ne se trouve pas dans la table de hachage (vous ne pouvez pas savoir sans effectuer la recherche), la recherche peut prendre aussi longtemps qu'une recherche linéaire sur la table de hachage entière (beurk !!!) . Donc, si vous pouvez économiser de la mémoire supplémentaire, optez pour une autre structure pour gérer les collisions.

Tout d’abord, je crée une table de hachage de la taille d’un nombre premier qui se rapproche du nombre de mots que je dois stocker, puis j’utilise une fonction de hachage pour trouver une adresse pour chaque mot.

return (hashAddress% hashTableSize);

Étant donné que le nombre de hachages différents est comparable au nombre de mots, vous ne pouvez pas vous attendre à des collisions beaucoup moins importantes.

J’ai fait un test statistique simple avec un hachage aléatoire (ce qui est le meilleur que vous puissiez obtenir) et j’ai constaté que 26% est le taux de collision limite si vous avez #words == #different hash.