Construction d'une table de hachage/fonction de hachage

Question

Je voudrais construire une table de hachage qui recherche les clés dans des séquences (chaînes) d'octets allant de 1 à 15 octets.

Je voudrais stocker une valeur entière, donc j'imagine qu'un tableau pour le hachage suffirait. J'ai de la difficulté à conceptualiser comment construire une fonction de hachage de telle sorte que, étant donné que la clé donne un index dans le tableau.

Toute assistance serait très appréciée.

Le nombre maximum d'entrées dans le hachage est: 4081 * 15 + 4081 * 14 + ... = 4081 4081 ((15 * (16))/2) = 489720.

Ainsi, par exemple:

int table[489720]; 

int lookup(unsigned char *key) 
{ 
    int index = hash(key); 
    return table[index]; 
} 

Quels sont les bons choix pour une fonction de hachage, ou comment pourrais-je en construire une?

Merci.

Answer 1

Si vous voulez un hachage parfait, alors vous pouvez commencer par lire l'article Wikipedia sur perfect hashing. Si vous rencontrez des problèmes, vous pouvez demander de l'aide ici.

Answer 2

Si le nombre moyen de chaînes résident dans la table est faible - comme moins de 10 000 entrées - un tableau associatif serait une approche raisonnable, même en utilisant une recherche linéaire si c'est sur une architecture de CPU moderne. Dans le cas contraire, la construction d'un "hachage parfait" nécessite d'inspecter chaque caractère de la chaîne et de calculer une valeur unique en fonction de la plage possible. Par exemple, si seuls les 26 caractères A..Z sont autorisés dans la clé, cela fonctionne:

int 
hash (const char *key) 
{ 
    int h = 0; 
    while (key && *key) 
     h = h * 26 + (*key++ - 'A'); 
    return h; 
} 

Answer 3

Votre espace clé est grande (environ 2^(8 * 15)), donc si vous voulez un hachage parfait, vous aurez besoin de savoir quelles 489720 touches réelles apparaîtront à l'avance. Même alors, il est pratiquement impossible de trouver un hachage parfait pour ces clés, même si vous avez permis une table beaucoup plus grande (a.k.a un facteur de charge très faible). La seule façon que je connaisse pour trouver un hachage parfait est par essais et erreurs, et un hachage aléatoire est susceptible d'échouer à moins que votre table ait près de 489720^2 entrées. Je recommande fortement d'utiliser un regular (non-perfect) hash et deal with collisions appropriately, par exemple avec enchaînant:

struct entry { 
    unsigned char *key; 
    int value; 
    struct entry *next; 
} *table[1<<20]; 
int lookup(unsigned char *key) { 
    int index = hash(key) % (1<<20); 
    for (struct entry *e = table[index]; e != NULL; e = e->next) { 
    if (!strcmp(key, e->key)) return e->value; 
    } 
    // not found 
} 

Je recommande également que vous ne mettez pas en œuvre vous-même - utiliser une bibliothèque standard comme un c++ hashmap.

Answer 4

Hash cordes C, je l'ai toujours utilisé cette fonction (prendre le résultat% votre taille de la table de hachage):

int hashstring(const char* s) { 
    int key = 0; 
    while (*s) { 
    key = key*37 + *s++; 
    } 
    return key; 
} 

Je ne me souviens pas où je l'ai eu au départ, mais dans de nombreuses années il ne m'a pas laissé tomber.