Visualiseur de table de hachage

Saisissez des clés et observez comment elles sont associées aux emplacements. Découvrez ce qui se passe en cas de collision.

Exemple résolu — Visualiseur de table de hachage

Facteur de charge alpha	0.75
Comportement actuel	5 collision(s)
Sondages supplémentaires	15
Sondages moyens	3.5
Probabilité de collision	85%

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Le préréglage « tout collisionne » n’a pas un hachage cassé — il a la mauvaise taille de table 🖖

Ses clés sont 0, 8, 16, 24, 32 et 40, et la table compte 8 cases. Chacune de ces clés est un multiple de 8, donc key mod 8 envoie les six dans la case 0 et la table dégénère en une seule liste. La fonction de hachage n’a rien de fautif : elle fait exactement ce qu’elle promet. Le défaut est que la taille de la table partage un facteur avec le motif des clés. C’est tout l’argument en faveur des tailles premières — une taille de 8 est sans défense face à des clés qui avancent par 8, alors qu’un nombre premier n’offre aucun facteur sur lequel retomber. Passez aux préréglages de sondage et voyez la même collision traitée de deux façons.

Sauter directement à la bonne case 🖖

Une table de hachage n’est rien d’autre qu’un tableau associé à une règle, la fonction de hachage, qui transforme chaque clé en numéro de case. Au lieu de parcourir les entrées une à une, vous calculez directement la place d’un élément et vous y accédez aussitôt. Les recherches restent ainsi rapides, même parmi des millions de clés. Encore faut-il répartir les clés uniformément. Insérez-en quelques-unes ici et observez avec quelle facilité deux clés se retrouvent en concurrence pour la même case.

Quand les collisions deviennent une arme 🖖

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 vous pouvez déclencher ci-dessus —, un attaquant qui connaît votre 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.

TABLES DE HACHAGE — OÙ TOMBE UNE CLÉ, ET CE QUI ARRIVE QUAND DEUX TOMBENT ENSEMBLE

Quel cas de collision traitez-vous ?

Une table de hachage n'est en O(1) que tant que les clés se répartissent. Deux questions décident de tout : la fonction de hachage disperse-t-elle vos clés, et lorsque deux d'entre elles se percutent, accrochez-vous la seconde à la case ou partez-vous en chercher une autre ? Le facteur de charge α = n/m fixe la fréquence des collisions ; la stratégie en fixe le coût.

Aucune collision — le cas que suppose la promesse O(1) h(k) = k mod m, α = n/m

Toutes les clés dans une case — le chaînage dégénère en liste O(n)

Sondage linéaire — adressage ouvert et regroupement primaire (h + i) mod m

Sondage quadratique — plus de blocs, mais des insertions refusées (h + i²) mod m

Aucune collision — le cas que suppose la promesse O(1)

Ce que vous savez: Chaque clé tombe dans une case différente. Le facteur de charge α = n/m est inférieur à 1 et le hachage répartit les clés uniformément dans la table.

Règle de sondage: h(k) = k mod m, α = n/m

Exemple résolu: clés 0–5 dans m = 8 avec h(k) = k mod 8 → cases 0–5, un sondage chacune : α = 0,75 et une moyenne d'exactement 1,00 sondage

Ouvrir ce cas: Aucune collision

Aucune collision — le cas que suppose la promesse O(1). Six clés, six cases différentes, un sondage chacune : il n'y a que le facteur de charge à surveiller. Chaque clé tombe dans une case différente. Le facteur de charge α = n/m est inférieur à 1 et le hachage répartit les clés uniformément dans la table. — Six clés, six cases différentes, un sondage chacune : il n'y a que le facteur de charge à surveiller.

Toutes les clés dans une case — le chaînage dégénère en liste

Ce que vous savez: Toutes les clés sont des multiples de la taille de la table, donc k mod m donne la même case pour chacune. Le chaînage les stocke quand même, mais dans une seule chaîne.

Règle de sondage: O(n)

Exemple résolu: clés 0, 8, 16, 24, 32, 40 dans m = 8 → toutes en case 0 ; les insérer coûte 1+2+3+4+5+6 = 21 sondages, soit 3,50 en moyenne

Ouvrir ce cas: Toutes en collision

Toutes les clés dans une case — le chaînage dégénère en liste. Les six clés en case 0 : une table de hachage devenue liste chaînée. Toutes les clés sont des multiples de la taille de la table, donc k mod m donne la même case pour chacune. Le chaînage les stocke quand même, mais dans une seule chaîne. — Les six clés en case 0 : une table de hachage devenue liste chaînée.

Sondage linéaire — adressage ouvert et regroupement primaire

Ce que vous savez: Pas de chaînes : en cas de collision, on avance case par case jusqu'à en trouver une libre. Chaque entrée vit dans la table elle-même.

Règle de sondage: (h + i) mod m

Exemple résolu: clés 3, 11, 19, 6, 14, 22 dans m = 8 → cases 3, 4, 5, 6, 7, 0 en 1, 2, 3, 1, 2, 3 sondages : moyenne 2,00, et les six entrées forment un bloc continu

Ouvrir ce cas: Sondage linéaire

Sondage linéaire — adressage ouvert et regroupement primaire. Les cases occupées fusionnent en un bloc ; une clé tombant dedans doit le parcourir jusqu'au bout. Pas de chaînes : en cas de collision, on avance case par case jusqu'à en trouver une libre. Chaque entrée vit dans la table elle-même. — Les cases occupées fusionnent en un bloc ; une clé tombant dedans doit le parcourir jusqu'au bout.

Sondage quadratique — plus de blocs, mais des insertions refusées

Ce que vous savez: En cas de collision, on saute de i² cases au lieu de i. Cela casse les blocs, mais la suite de sondage ne visite plus toutes les cases.

Règle de sondage: (h + i²) mod m

Exemple résolu: les mêmes clés dans m = 8 → 3, 4, 7, 6, 2 — puis 22 échoue purement et simplement : avec m puissance de deux, i² mod 8 ne vaut que 0, 1 ou 4, donc trois cases au total

Ouvrir ce cas: Sondage quadratique

Sondage quadratique — plus de blocs, mais des insertions refusées. La suite saute puis se répète : des cases restent libres et la dernière clé n'a nulle part où aller. En cas de collision, on saute de i² cases au lieu de i. Cela casse les blocs, mais la suite de sondage ne visite plus toutes les cases. — La suite saute puis se répète : des cases restent libres et la dernière clé n'a nulle part où aller.

Problèmes entièrement résolus

Une table pleine à 75 % avec une moyenne de 3,5 sondages par recherche 5 étapes
La table est remplie à 75 % et compte en moyenne 3,5 sondages par recherche. La formule classique du sondage linéaire prédit 2,5 pour ce taux de charge. Déterminez lequel des deux est faux.
1. Aucun des deux n'est faux, et l'explication réside dans les clés. Hachez chacune des six avec la propre fonction de la table et chacune d'elles renvoie 3 — elles forment une progression arithmétique de raison 8, et la table comporte exactement 8 emplacements.
  
  $h (k) = k mod 8 : 3, 11, 19, 27, 35, 43 ⟼ 3, 3, 3, 3, 3, 3$
2. Le facteur de charge vaut toujours bel et bien 0,75 : six clés dans huit emplacements. Il ne dit tout simplement rien sur l'endroit où elles sont allées.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
3. La séquence de sondage est donc la pire possible. La première clé s'installe sans obstacle ; la deuxième avance d'un emplacement ; la troisième avance de deux. Six clés coûtent 1 + 2 + … + 6 = 21 sondages, dont 15 constituent le travail supplémentaire indiqué par le panneau.
  
  $probes = 1, 2, 3, 4, 5, 6 ⟹ \sum = 21, extra = 21 - 6 = 15$
4. Cela donne une moyenne de 3,5 sondages par recherche.
  
  $\overset{p}{ˉ} = \frac{21}{6} = 3.5$
5. L'estimation des manuels suppose que les clés se répartissent uniformément, et pour α = 0,75, elle donne 2,5. L'écart entre 2,5 et 3,5 n'est pas une erreur — c'est le coût d'une fonction de hachage ayant un facteur commun avec la taille de la table, appliquée à des clés qui le partagent également.
  
  $\frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5 (random keys) < 3.5$
Réponse

L'outil affiche α = 0,75, 15 sondages de travail supplémentaire et une moyenne de 3,5. La leçon à en tirer est que le facteur de charge est la valeur célèbre, mais la mauvaise à surveiller isolément : il est ici identique à celui d'une table contenant six clés bien dispersées, ce qui coûterait 2,5. Ce qui a changé, c'est l'interaction entre l'ensemble de clés et le modulo. C'est pourquoi la taille des tables est choisie première, et pourquoi le hachage d'une structure par un champ qui se trouve être un multiple de la capacité transforme O(1) en O(n) tout en conservant des métriques apparemment saines. Faites passer la taille de 8 à 7 et observez l'effondrement de la moyenne.

$\overset{p}{ˉ} = 3.5 observed vs 2.5 predicted : α is not the whole story$
Une vraie table de hachage se redimensionnant au facteur de charge de 0,75 6 étapes
Le panneau met 6 clés dans 8 cases, facteur de charge 0,75, et signale 3,5 sondages. Une recherche fructueuse à cette charge coûte environ 2,5 — confortable. Alors pourquoi toute vraie table de hachage se redimensionne-t-elle précisément à 0,75 au lieu de se remplir ?
1. Partez de l'état du panneau. Aux trois quarts pleine, ce qui ressemble à un usage raisonnable de la mémoire.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
2. La recherche fructueuse est le chiffre rassurant : en moyenne vous examinez environ deux cases et demie avant de trouver la clé voulue.
  
  $S (α) \approx \frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5$
3. La recherche infructueuse suit une autre formule, et toute la réponse tient dans cette différence. Un échec doit parcourir jusqu'au bout une suite de cases occupées pour prouver l'absence — d'où un terme au carré, et non linéaire.
  
  $U (α) \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) = \frac{1}{2} (1 + 16) = 8.5$
4. Poussez la charge un peu plus haut et lisez ce que fait le carré. De 0,75 à 0,90 semble un changement d'occupation modeste.
  
  $U (0.90) = \frac{1}{2} (1 + 100) = 50.5, U (0.95) = \frac{1}{2} (1 + 400) = 200.5$
5. Comparez les deux taux de croissance sur ce même pas. Le coût du succès fait un peu plus que doubler ; celui de l'échec est multiplié par six.
  
  $α : 0.75 \to 0.90 ⟹ S : 2.5 \to 5.5 (\times 2.2), U : 8.5 \to 50.5 (\times 5.9)$
6. La table double donc plutôt. Chaque clé est réinsérée, ce qui coûte m opérations, mais achète m insertions de plus avant que cela ne recommence.
  
  $m \to 2 m ⟹ α \to \frac{α}{2}, \frac{m}{m} = O (1)$
Réponse

Un échec à 0,75 coûte 8,5 sondages ; à 0,90 il en coûte 50,5, et à 0,95 il en coûte 200,5. Voilà pourquoi 0,75 est le seuil de redimensionnement dans une bibliothèque standard après l'autre : moins un compromis mémoire-vitesse que le dernier point avant la falaise. Et ce qui compte est l'échec, car c'est par un échec que commence chaque insertion, et c'est d'échec qu'est faite toute recherche infructueuse. Le rassurant 2,5 décrit le cas qui ne vous inquiétait pas.

$U (α) = \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) : 2.5 (0.50), 8.5 (0.75), 50.5 (0.90), 200.5 (0.95)$

Parcours

Quand deux choses tombent sur la même valeur

Références (1)

Hashing, collision resolution and why table size matters, at length: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.4. Addison-Wesley, 1998. ISBN 978-0-201-89685-5.

Par l’équipe 42Math · Mis à jour 2026-07-27

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

Aucune collision - Les clés de 0 à 5 dans une table de taille 8 : six cases distinctes, un seul sondage par clé et aucune collision. Le facteur de charge atteint déjà 0,75.
Toutes en collision - Chaque clé est un multiple de 8 : les six aboutissent donc à la case 0, et la chaîne compte six éléments. Il faut en moyenne 3,5 sondages, valeur initiale de l’exercice résolu.
Sondage linéaire - 3, 11 et 19 visent tous la case 3 ; 6, 14 et 22, la case 6. Le sondage linéaire place les six clés en respectivement 1, 2, 3, 1, 2 et 3 sondages, soit une moyenne de 2.
Sondage quadratique - Avec les mêmes six clés, le sondage quadratique ne parvient pas à placer la dernière. Modulo 8, les carrés ne valent que 0, 1 ou 4 : depuis la case 6, la suite n’atteint donc que 6, 7 et 2, tandis que les cases 0, 1 et 5 restent vides.