informatique (MP2I/MPI) · Chapitre 12 · Exercice de TD
Une mauvaise fonction de hachage, mesurée
Tableaux associatifs, hachage et sérialisation · niveau 2
Énoncé
On propose trois fonctions de hachage pour des chaînes :
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]; }Prévoir laquelle est la meilleure, et pourquoi. Puis mesurer sur un vocabulaire réel.
Corrigé
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 .
h_premierne regarde qu'un caractère : son image compte au plus valeurs, et les mots se répartissent selon la fréquence des initiales, qui est tout sauf uniforme.h_sommeignore l'ordre des lettres : deux anagrammes ont le même haché, toujours. Pire, son image est bornée par pour des mots courts : au-delà, les cases hautes ne seront jamais atteintes.h_polytient compte de la position, puisque la -ième lettre est multipliée par . Les se répandent sur tous les bits.
Les mesures, sur mots français distincts extraits de ce livre :
| cases vides | chaîne max | coût moyen d'une recherche | ||
|---|---|---|---|---|
h_somme | (18{,}1%) | |||
h_poly | (1{,}4%) | |||
h_premier | (97{,}6%) | |||
h_somme | (88{,}8%) | |||
h_poly | (58{,}9%) | |||
h_premier | (99{,}7%) |
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 , qui vaut pour et pour : h_poly l'atteint exactement, aux deux tailles.
Trois observations que la mesure seule donne.
h_sommene profite pas d'un agrandissement : passer de à cases ne fait pas descendre son coût ( puis ), parce que son image reste confinée aux premières cases — du tableau ne sert à rien. Une mauvaise fonction de hachage ne se répare pas en agrandissant la table.- Les anagrammes se confondent : mesuré,
chienetchineont la même somme, . Sur les mots, paires partagent une somme, contre zéro pour la version polynomiale. h_premierproduit une chaîne de mots — les mots enc. 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 annoncé n'est pas une propriété de la structure, c'est une propriété de la fonction qu'on y a mise.
