Hashtbl.hash ne regarde pas tout

Mesuré : une seule. Les cent mille listes, toutes distinctes, ont le même haché.

Pourquoi. Hashtbl.hash ne parcourt pas la valeur entière : pour rester en temps constant sur des structures arbitrairement grandes, elle s'arrête après un nombre borné de nœuds significatifs — dix par défaut. Tout ce qui vient au-delà est ignoré.

Mesuré en cherchant le seuil : sur une liste de trente entiers, modifier une des positions $0$ à $9$ change le haché ; modifier une des positions $10$ à $29$ ne le change jamais. Le treizième élément de nos listes, celui qui les distingue, tombe donc en dehors de la fenêtre.

Ce n'est pas un défaut du module, c'est un contrat. Une fonction de hachage doit être rapide — sinon elle mange le $O(1)$ qu'elle promet. Hacher une liste d'un million d'éléments en la parcourant coûterait $\Theta (n)$ par accès, et la table serait plus lente qu'une liste d'association. Le module choisit donc de plafonner, et l'annonce dans sa documentation. La faute serait de l'ignorer.

La conséquence, à connaître : des clés qui ne diffèrent que « profondément » se comportent comme une seule clé. Un tuple dont seules les premières composantes varient, une liste dont on ne change que la fin, un enregistrement dont le champ discriminant est le dernier — tous produisent une table dégénérée.

Les parades.

• Résumer la clé : au lieu d'indexer par la liste entière, indexer par une chaîne construite à partir d'elle, ou par un entier calculé soi-même — la fonction polynomiale mesurée plus haut parcourt tout.
• Mettre en tête ce qui distingue : si les clés sont des couples, placer en première composante celle qui varie.
• Employer le foncteur Hashtbl.Make, qui prend en paramètre l'égalité et le hachage — hors annexe, mais c'est la réponse propre.

Ce que cet exercice éprouve : la mise en garde du chapitre — « le $O(1)$ est en moyenne, jamais dans le pire cas » — ne parle pas d'un cas rare. Il suffit d'un choix de clés maladroit, sans la moindre intention, pour tomber dessus. L'exercice suivant chiffre ce que cela coûte.