Une mauvaise fonction de hachage, mesurée

unsigned long h_somme(const char* s) {         /* somme des codes */
    unsigned long h = 0;
    for (int i = 0; s[i] != '\0'; i = i + 1) { h = h + (unsigned char) s[i]; }
    return h;
}
unsigned long h_poly(const char* s) {          /* polynomiale, base 31 */
    unsigned long h = 0;
    for (int i = 0; s[i] != '\0'; i = i + 1) { h = 31 * h + (unsigned char) s[i]; }
    return h;
}
unsigned long h_premier(const char* s) { return (unsigned char) s[0]; }

La prévision. Une bonne fonction de hachage doit disperser : deux clés proches doivent donner des hachés éloignés, et l'image doit couvrir tout $\{0,\dots ,m-1\}$.

• h_premier ne regarde qu'un caractère : son image compte au plus $26$ valeurs, et les mots se répartissent selon la fréquence des initiales, qui est tout sauf uniforme.
• h_somme ignore l'ordre des lettres : deux anagrammes ont le même haché, toujours. Pire, son image est bornée par $15\times 122\approx 1830$ pour des mots courts : au-delà, les cases hautes ne seront jamais atteintes.
• h_poly tient compte de la position, puisque la $i$-ième lettre est multipliée par $31^{\ell -1-i}$. Les $31^k$ se répandent sur tous les bits.

Les mesures, sur $4321$ mots français distincts extraits de ce livre :

La dernière colonne est le nombre moyen de comparaisons d'une recherche fructueuse avec chaînage. Le repère est la valeur idéale $1+\alpha /2$, qui vaut $3,11$ pour $m=1024$ et $1,26$ pour $m=8192$ : h_poly l'atteint exactement, aux deux tailles.

Trois observations que la mesure seule donne.

• h_somme ne profite pas d'un agrandissement : passer de $1024$ à $8192$ cases ne fait pas descendre son coût ($4,95$ puis $4,89$), parce que son image reste confinée aux $1830$ premières cases — $88,8\%$ du tableau ne sert à rien. Une mauvaise fonction de hachage ne se répare pas en agrandissant la table.
• Les anagrammes se confondent : mesuré, chien et chine ont la même somme, $519$. Sur les $4321$ mots, $16815$ paires partagent une somme, contre zéro pour la version polynomiale.
• h_premier produit une chaîne de $501$ mots — les mots en c. Sa table est une liste chaînée à peine déguisée.

Le programme dit que la construction d'une fonction de hachage « n'est pas exigible ». Ces chiffres disent pourquoi il faut tout de même savoir en juger une : le $O(1)$ annoncé n'est pas une propriété de la structure, c'est une propriété de la fonction qu'on y a mise.