Muter une clé rend l'entrée introuvable

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))

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 $h(c)\mathrm{mod}m$, où $h$ 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 $369955794$, et Hashtbl.hash [|42;2;3|] vaut $587111518$. 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, $n$-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.