Visualiseur de table de hachage

Les tables de hachage utilisent des algorithmes mathématiques déterministes pour mapper des clés arbitraires à des espaces d'index finis, en optimisant la récupération temporelle O(1). Les collisions, conséquence inévitable du principe du casier, nécessitent des protocoles de résolution stricts. Le chaînage repose sur des allocations de listes chaînées, tandis que les sondages linéaires et quadratiques utilisent des fonctions mathématiques par étapes pour parcourir les indices de tableau. Le facteur de charge dicte en permanence la probabilité statistique de ces collisions coûteuses en calcul.

Une table de hachage n'est qu'un tableau assorti d'une règle — la fonction de hachage — qui transforme chaque clé en numéro de case. Au lieu de parcourir chaque entrée une à une, tu calcules où doit se trouver un élément et tu y vas directement ; c'est pourquoi les recherches restent rapides même avec des millions de clés. Le piège : la vitesse dépend d'une répartition uniforme des clés. Insères-en quelques-unes ici et regarde à quelle vitesse deux clés visent la même case.

Comme une table de hachage dégénère en une lente recherche linéaire lorsque trop de clés s'entassent dans la même case — exactement le pire cas que tu peux déclencher ci-dessus —, un attaquant qui connaît ta fonction de hachage peut fabriquer des milliers de clés qui entrent délibérément en collision. En 2011, cette attaque dite 'hash-flooding' a paralysé des serveurs web en PHP, Java, Python et Ruby avec une seule requête forgée. La parade : des fonctions de hachage à graine aléatoire comme SipHash, aujourd'hui standard dans de nombreux langages.