fonction de hachage pour une chaîne de caractères

Question

Je travaille sur une table de hachage en langage C et je teste la fonction de hachage pour les chaînes de caractères.

La première fonction que j'ai essayée est d'ajouter du code ascii et d'utiliser le modulo (%100) mais j'ai obtenu de mauvais résultats avec le premier test de données : 40 collisions pour 130 mots.

Les données d'entrée finales contiendront 8 000 mots (il s'agit d'un dictionnaire stocké dans un fichier). La table de hachage est déclarée comme int table[10000] et contient la position du mot dans un fichier txt.

La première question est la suivante : quel est le meilleur algorithme pour hacher une chaîne de caractères ? et comment déterminer la taille de la table de hachage ?

Merci d'avance !

-)

Answer 1

J'ai eu de bons résultats avec djb2 par Dan Bernstein.

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

Answer 2

D'abord, vous faites généralement no vous voulez utiliser un hachage cryptographique pour une table de hachage. Un algorithme qui très rapide selon les normes cryptographiques est toujours atrocement lent selon les normes des tables de hachage.

Deuxièmement, vous voulez vous assurer que chaque élément de l'entrée peut/va affecter le résultat. Un moyen simple d'y parvenir est de faire tourner le résultat actuel d'un certain nombre de bits, puis de faire un XOR du code de hachage actuel avec l'octet actuel. Répétez l'opération jusqu'à ce que vous atteigniez la fin de la chaîne. Notez que vous faites généralement no Je ne veux pas non plus que la rotation soit un multiple pair de la taille de l'octet.

Par exemple, dans le cas courant d'octets de 8 bits, vous pouvez effectuer une rotation de 5 bits :

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

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

Edit : Notez également que 10000 slots est rarement un bon choix pour la taille d'une table de hachage. En général, vous souhaitez deux choses : soit un nombre premier comme taille (nécessaire pour garantir la correction avec certains types de résolution de hachage), soit une puissance de 2 (afin que la réduction de la valeur à la plage correcte puisse être effectuée avec un simple masque de bits).

Answer 3

Wikipedia montre une belle fonction de hachage de chaîne appelée Jenkins One At A Time Hash. 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;
}

Answer 4

Il existe un certain nombre d'implémentations de tables de hachage pour le langage C, depuis la bibliothèque standard hcreate/hdestroy/hsearch, jusqu'à celles de l'application APR y glib qui fournissent également des fonctions de hachage préconstruites. Je vous recommande vivement de les utiliser plutôt que d'inventer votre propre table de hachage ou fonction de hachage ; elles ont été fortement optimisées pour les cas d'utilisation courants.

Toutefois, si votre ensemble de données est statique, la meilleure solution est probablement d'utiliser un fichier de type hachis parfait . gperf générera pour vous un hachage parfait pour un ensemble de données donné.

Answer 5

Tout d'abord, 40 collisions pour 130 mots hachés à 0..99 est-il mauvais ? Vous ne pouvez pas vous attendre à un hachage parfait si vous ne prenez pas de mesures spécifiques pour qu'il 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 ayant une bonne réputation est MurmurHash3 .

Enfin, en ce qui concerne la taille de la table de hachage, cela dépend vraiment du type de table de hachage que vous avez en tête, notamment si les buckets sont extensibles ou à un seul emplacement. Si les buckets sont extensibles, là encore, il y a un choix à faire : vous choisissez la longueur moyenne du bucket en fonction des contraintes de mémoire et de vitesse que vous avez.