La clé qui mute — reconstitution d'une catastrophe

(a)

• À l'insertion de [1, 2], l'adresse est calculée via hash((1, 2)) % m, ce qui donne une alvéole (par exemple, l'alvéole 4). La paire [[1, 2], "x"] y est stockée.
• La mutation de cle en [1, 2, 3] modifie directement l'objet en mémoire stocké dans la table de hachage (par effet de bord de l'objet partagé).
• Si l'on cherche [1, 2, 3] : le programme calcule l'indice via hash((1, 2, 3)) % m qui cible une autre alvéole (par exemple, l'alvéole 1). L'alvéole 1 étant vide ou contenant d'autres clés, la recherche échoue.
• Si l'on cherche [1, 2] : le programme calcule l'indice via hash((1, 2)) % m qui cible l'alvéole 4. Il parcourt l'alvéole 4 et y trouve la paire stockée. Il compare la clé recherchée [1, 2] avec l'objet stocké qui vaut désormais [1, 2, 3]. La comparaison échoue, la recherche échoue également. La valeur "x" est devenue orpheline : elle occupe de la place en mémoire mais est à jamais inaccessible. (b) L'invariant violé est : « Tout élément associé à une clé c doit se trouver dans l'alvéole désignée par h(c) ». La mutation de l'objet depuis l'extérieur a altéré son haché sans déplacer l'élément dans la bonne alvéole. (c) Pour éviter ce comportement incohérent et silencieux, Python interdit purement et simplement l'utilisation d'objets mutables (comme les listes) comme clés de dictionnaire ou d'ensemble, en levant une erreur à l'exécution dès la tentative de hachage.