Problème — Un dictionnaire par liste d'association, et pourquoi il ne suffit pas

1. Les quatre opérations.

(* cherche c d : Some v si (c, v) est la PREMIERE paire de cle c dans d,
   None si aucune paire de d ne porte la cle c.
   Precondition : aucune.  Complexite : Theta(n) dans le pire cas. *)
let rec cherche c d =
  match d with
  | [] -> None
  | (c', v) :: r -> if c' = c then Some v else cherche c r

(* ajoute c v d : un dictionnaire ou c vaut v, les liaisons anterieures
   de c etant MASQUEES sans etre supprimees. Complexite : Theta(1). *)
let ajoute c v d = (c, v) :: d

(* supprime c d : d prive de TOUTES ses paires de cle c.
   Complexite : Theta(n). *)
let rec supprime c d =
  match d with
  | [] -> []
  | (c', v) :: r -> if c' = c then supprime c r else (c', v) :: supprime c r

(* remplace c v d : un dictionnaire ou c vaut v, sans liaison morte.
   Complexite : Theta(n). *)
let remplace c v d = (c, v) :: supprime c d

Les quatre rendent une valeur neuve et ne modifient rien : les dictionnaires antérieurs restent valides et utilisables. Mesuré : après trois ajoute, les états intermédiaires ont encore leurs longueurs $1$ et $2$.

2. Masquer, ou supprimer. ajoute pose une paire en tête : $\Theta (1)$, et la recherche trouvera bien la nouvelle valeur, puisqu'elle rend la première. Mais l'ancienne paire est toujours là, derrière. remplace doit parcourir toute la liste pour l'ôter — d'où $\Theta (n)$.

L'écart se paye en mémoire, et il se mesure :

1000 ajoute de la meme cle   : longueur 1000, cherche donne la derniere valeur
1000 remplace de la meme cle : longueur 1

Mille mises à jour d'une seule clé produisent un dictionnaire de mille paires dont $999$ sont mortes — et que le ramasse-miettes ne peut pas récupérer, puisqu'elles sont bel et bien atteignables. C'est une fuite logique : pas un défaut de gestion mémoire, un défaut de structure. Le choix entre les deux est donc un choix de spécification, pas une optimisation : ajoute convient à un dictionnaire qui grossit par clés distinctes, remplace à un dictionnaire qu'on met à jour.

3. La mesure, et la limite de la structure. Mille recherches d'une clé située en fin de liste :

n =   1 000 : en liste 0,0270 s   en Hashtbl 0,0001 s
n =  10 000 : en liste 0,2572 s   en Hashtbl 0,0001 s
n = 100 000 : en liste 2,5356 s   en Hashtbl 0,0001 s

La liste multiplie son temps par dix quand $n$ est multiplié par dix : c'est $\Theta (n)$, sans ambiguïté. La table de hachage ne bouge pas : $\Theta (1)$ en moyenne.

Ce que la liste d'association garde pour elle. Sa simplicité — quatre fonctions de trois lignes —, son immuabilité, et le fait qu'elle ne demande aucune hypothèse sur les clés au-delà de l'égalité. La table de hachage exige une fonction de hachage, se comporte mal si celle-ci est mauvaise, et n'offre son $\Theta (1)$ qu'en moyenne — jamais en pire cas. Le chapitre chap:hachage établit ces réserves ; jusque-là, une liste d'association de dix clés est le bon outil, et une de cent mille ne l'est plus.