informatique (tronc commun des prépas scientifiques) · Chapitre 17 · Exercice de TD
La clé qui mute — reconstitution d'une catastrophe
Les dictionnaires dévoilés : le hachage · niveau 2
Énoncé
Soit une table de hachage acceptant des clés mutables. On insère une liste mutable cle = [1, 2] avec la valeur "x", en calculant son adresse via hash(tuple(cle)). (a) Muter la clé insérée en effectuant cle.append(3). Décrire ce que produisent alors les recherches de [1, 2, 3] puis de [1, 2]. (b) Formuler précisément l'invariant de structure qui a été violé. (c) Expliquer comment la conception de Python prévient cette catastrophe.
Corrigé
(a)
- À l'insertion de
[1, 2], l'adresse est calculée viahash((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
cleen[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 viahash((1, 2, 3)) % mqui 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 viahash((1, 2)) % mqui 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.