informatique (MP2I/MPI) · Chapitre 12 · Application directe du cours
Muter une clé rend l'entrée introuvable
Tableaux associatifs, hachage et sérialisation · niveau 2
Énoncé
Que rend ce fragment ? Expliquer, et en tirer une règle.
let h = Hashtbl.create 16 in
let cle = [| 1; 2; 3 |] in
Hashtbl.add h cle "la valeur";
print_string (string_of_bool (Hashtbl.mem h cle));
cle.(0) <- 42;
print_string (string_of_bool (Hashtbl.mem h cle))Corrigé
Mesuré : il affiche true puis false — pour la même valeur physique, celle que l'on vient de passer à add.
Pourquoi. Le module Hashtbl range la liaison à l'indice , où est la fonction de hachage structurelle d'OCaml : elle parcourt la valeur et calcule un entier à partir de son contenu. Mesuré : Hashtbl.hash [|1;2;3|] vaut , et Hashtbl.hash [|42;2;3|] vaut . Après la mutation, mem calcule le second haché et va regarder dans une case où rien n'a été rangé.
La liaison n'a pas disparu : mesuré, Hashtbl.iter la voit toujours. Elle est simplement inaccessible par sa clé — perdue dans la table, jusqu'à ce qu'on remette la clé dans son état d'origine.
La règle : une clé de table de hachage doit être immuable. Plus précisément, son haché ne doit pas changer tant qu'elle est dans la table. Trois manières de s'y tenir :
- n'employer comme clés que des valeurs immuables — entiers, chaînes, -uplets de valeurs immuables, listes de telles valeurs ;
- si l'on doit indexer un objet mutable, en copier la partie qui sert de clé au moment de l'insertion ;
- si une clé doit changer, la retirer avant, et la réinsérer après.
Ce que cela dit du hachage en général. La fonction de hachage lie une valeur à une position. Toute la structure repose sur l'hypothèse que cette liaison est stable. C'est une contrainte que l'arbre de recherche partage — muter une clé y romprait aussi l'invariant — mais qui est plus visible ici, parce que le hachage lit le contenu de la clé, tandis que l'arbre ne fait que la comparer.