Saboter une table — la fonction qui disperse mal

(a) Pour générer des collisions parfaites, on utilise des anagrammes de même longueur. Par exemple, les $200$ chaînes formées de $199$ lettres "a" et une lettre "b" placée à des positions différentes (&quot;b&quot; + &quot;a&quot;<em>199, &quot;a&quot; + &quot;b&quot; + &quot;a&quot;</em>198, etc.) possèdent toutes exactement le même code de hachage sous la fonction-somme. Toutes ces clés sont donc insérées dans l'alvéole 2 de notre table. La table dégénère en une simple liste de taille 200. Effectuer 1000 recherches nécessite de parcourir cette chaîne. On mesure alors un temps de recherche $50$ à $100$ fois plus lent qu'avec hash(), car cette dernière prend en compte la position des caractères et disperse donc correctement les anagrammes. (b) La fonction somme est commutative ($h("ab")=h("ba")=\text{ord}{(}^{\prime }{a}^{\prime })+\text{ord}{(}^{\prime }{b}^{\prime })$), ce qui est un défaut majeur. Une bonne fonction de hachage doit être sensible à l'ordre des éléments, à la longueur et au contenu de la clé. (c) Si la fonction de hachage d'un système était entièrement prévisible, un pirate pourrait envoyer un grand nombre de clés en collision parfaite (par exemple via des requêtes HTTP POST) pour forcer le dictionnaire interne du serveur à travailler en $O(n)$, saturant ainsi le processeur (attaque par déni de service). En salant la graine du hachage de manière aléatoire à chaque lancement de programme, Python rend la découverte de collisions impossibles de l'extérieur.