L'ordre que le hachage ne donne pas

Mesuré : aussi:1 dort:2 chat:2 mange:1 le:3 chien:1.

Cet ordre n'est ni alphabétique, ni celui de l'insertion, ni celui de la première apparition. C'est l'ordre des cases du tableau sous-jacent, c'est-à-dire l'ordre des hachés — une quantité qui n'a aucun sens pour l'utilisateur. Il est de plus instable : la même liste dans une table de taille différente sortirait dans un autre ordre, et une insertion supplémentaire, en déclenchant un redimensionnement, peut tout permuter.

La règle : ne jamais dépendre de l'ordre d'itération d'une table de hachage. Un programme qui « marche » parce qu'un Hashtbl.iter sort dans un ordre commode est un programme qui cassera.

Pour l'ordre alphabétique, deux voies :

(* (a) extraire puis trier : Theta(n log n), et il faut y penser *)
let tries h =
  let l = ref [] in
  Hashtbl.iter (fun mot n -> l := (mot, n) :: !l) h;
  List.sort compare !l

Mesuré : le résultat devient aussi:1 chat:2 chien:1 dort:2 le:3 mange:1.

(b) Employer un arbre de recherche dès le départ — le tableau associatif par ABR du chapitre chap:tas —, dont le parcours infixe rend les couples triés en $\Theta (n)$, sans un mot de plus.

Comment choisir. La question n'est pas « lequel est le plus rapide » mais « le tri est-il occasionnel ou constant ? ». Un comptage de mots que l'on trie une fois à la fin : la table gagne largement, et le $\Theta (n\log n)$ final est négligeable devant les millions d'insertions. Un classement affiché trié après chaque mise à jour : l'arbre gagne, car la table paierait le tri à chaque affichage. Mesuré sur $200000$ clés : lister trié coûte $0,014$ s par l'arbre contre $0,127$ s par la table — mais chaque recherche coûte $0,27$ microseconde par l'arbre contre $0,06$ par la table. On ne compare pas deux structures dans l'absolu, on les compare sur le mélange d'opérations qu'on va réellement leur demander.