Les tables de hachage en pratique : collisions, facteur de charge et hachage avec graine

Ce que c'est

Une table de hachage fait correspondre une clé à un index de compartiment en calculant hash(key) mod capacity. Deux clés qui aboutissent dans le même compartiment entrent en collision ; la table résout cela par chaînage (une petite liste par compartiment) ou par adressage ouvert (sondage d'autres emplacements). Le facteur de charge est le nombre d'entrées divisé par la capacité. La documentation de HashMap en Java décrit le facteur de charge comme la mesure du taux de remplissage que la table peut atteindre avant que sa capacité ne soit augmentée, avec une valeur par défaut de 0,75 ; lorsque le nombre d'entrées dépasse le facteur de charge multiplié par la capacité, la table est rehachée, ce qui touche chaque entrée. Le modèle de données de Python indique que les valeurs de hachage de str et de bytes sont salées avec une valeur imprévisible propre à chaque processus (randomisation du hachage, activée par défaut depuis la 3.3), et la spécification de Go précise que l'ordre d'itération sur les maps n'est pas spécifié.

Pourquoi c'est important

Des recherches en O(1) en moyenne dépendent d'une répartition uniforme des clés. Un attaquant capable de choisir les clés (noms de paramètres de requête, noms de champs JSON, champs de formulaire) et connaissant la fonction de hachage peut faire entrer en collision des milliers de clés, transformant chaque insertion en un parcours linéaire et une requête en un travail quadratique ; c'est le hash flooding, et le salage propre à chaque processus en est la défense standard. Le rehachage est en O(n) et survient à certains seuils, si bien qu'une boucle insérant n éléments paie plusieurs tours de rehachage : le coût amorti reste en O(1), mais des insertions individuelles présentent des pics.

Comment l'appliquer

• Ne jamais persister, transmettre ni comparer entre processus une valeur de hachage de niveau langage ; elle change selon la graine, la version et le build. Trier la sortie qui doit être stable plutôt que de se fier à l'ordre d'une map.
• Prédimensionner lorsque le nombre est connu (HashMap(initialCapacity), make(map[K]V, n)) pour éviter des tours de rehachage dans les boucles critiques.
• Les clés ne doivent pas changer tant qu'elles sont dans la table ; muter une clé après insertion rend l'entrée introuvable. Des objets égaux doivent hacher de façon identique : définir l'égalité et le hachage ensemble.
• Lors de l'implémentation d'une table (code embarqué, allocateur personnalisé) : utiliser un hachage à bon effet d'avalanche, le semer par processus, plafonner le facteur de charge, et tester la plus longue chaîne de sondage avec des clés adverses.
• Pour des tests reproductibles, fixer explicitement la graine (PYTHONHASHSEED) plutôt que de compter sur le hasard, et exécuter aussi la suite avec une graine aléatoire.

Pièges

Un test qui réussit avec une graine et échoue avec une autre révèle une dépendance à l'ordre dans le code, pas un test instable. Clés en virgule flottante : 0.0 et -0.0 sont égaux et doivent hacher de façon identique ; NaN n'est pas égal à lui-même. Une table utilisée comme cache sans borne de taille est une fuite mémoire. Les empreintes cryptographiques telles que SHA-256 sont inutiles pour des tables, et lentes ; des fonctions de hachage à clé rapides, conçues pour les tables, sont la norme.