Le pire cas provoqué, chronométré

Les clés hostiles sont les listes [1;...;12; i] de l'exercice précédent ; les clés honnêtes sont les listes [i]. Mesuré :

Lire la colonne de droite. Le temps hostile quadruple quand $n$ double : c'est la signature d'un $\Theta (n^2)$. Et pour cause — toutes les clés forment une seule chaîne, la $i$-ième insertion parcourt les $i-1$ précédentes pour vérifier l'absence, et $\sum i=n^2/2$. La table de hachage est devenue une liste chaînée, avec le surcoût du hachage en prime.

Le rapport n'est pas une constante : il croît linéairement, de $519$ à $3619$ quand $n$ passe de $1000$ à $8000$. Un rapport qui croît n'est pas une lenteur, c'est un changement de complexité.

Ce qu'il faut en conclure pour un serveur. C'est une attaque par déni de service, et elle est réelle : un serveur qui range dans une table de hachage des données venues du réseau — paramètres d'une requête, en-têtes, identifiants de session — offre à l'attaquant le choix des clés. Il lui suffit d'envoyer quelques milliers de clés de même haché pour que le serveur passe des secondes de calcul sur une requête qui devait en prendre des microsecondes. Quelques requêtes par seconde suffisent alors à saturer une machine.

Les deux parades.

• La randomisation : tirer au démarrage une graine qui entre dans le calcul de $h$. L'attaquant ne peut plus prévoir les collisions, puisqu'elles changent à chaque lancement du programme. C'est ce que font aujourd'hui la plupart des langages par défaut ; en OCaml, Hashtbl.create random:true 97 l'active — et le programme précise que Hashtbl y est employé sans randomisation, ce qui est un choix pédagogique, pas une recommandation d'ingénierie.
• Ne pas indexer par des données non contrôlées, ou plafonner leur nombre.

Et la leçon de fond. Le tableau de synthèse du chapitre dit « $O(1)$ en moyenne ». Ces mesures montrent que « en moyenne » présuppose un tirage : elles décrivent des clés arbitraires, pas des clés choisies. Dès que quelqu'un choisit les entrées, la moyenne n'a plus de sens et seul le pire cas parle — et il vaut $O(n)$ par opération. Une complexité en moyenne est une hypothèse sur le monde, pas une propriété du programme.