Table de hachage — fonctionnement du hachage et résolution des collisions

Une table de hachage stocke des paires clé-valeur en transformant chaque clé en un indice de tableau grâce au hachage. Cela permet à la table d’aller directement près du bon emplacement au lieu de parcourir tous les éléments stockés un par un.

C’est pourquoi les tables de hachage sont souvent proches de $O(1)$ en moyenne pour la recherche, l’insertion et la suppression. Cette condition est importante : la fonction de hachage doit répartir les clés de façon raisonnablement uniforme, et la table doit aussi prévoir une règle pour gérer les collisions.

À quoi sert une table de hachage

Une table de hachage stocke des paires clé-valeur comme "name" -> "Ada" ou 42 -> "blue". Elle comporte deux éléments principaux :

• un tableau de cases ou de seaux
• une fonction de hachage qui associe chaque clé à l’une de ces cases

Si le tableau a $m$ cases, on peut voir la fonction de hachage comme produisant un indice de $0$ à $m-1$.

Pour un petit exemple avec des entiers, la règle pourrait être

$$h(k) = k \bmod 8$$

Alors la clé $10$ va dans la case $2$ parce que $10 \bmod 8 = 2$.

Les vraies fonctions de hachage sont conçues plus soigneusement, surtout pour les chaînes de caractères et les ensembles de données plus grands. Mais l’idée de base reste la même : calculer rapidement un indice, puis vérifier l’élément stocké à cet endroit.

Pourquoi les collisions de hachage sont inévitables

Une collision se produit lorsque deux clés différentes sont associées à la même case.

C’est normal, car la table a généralement moins de cases que le nombre de clés possibles. Avec

$$h(k) = k \bmod 8$$

les clés $10$, $18$ et $26$ sont toutes associées à la case $2$. Donc, même si la fonction fonctionne exactement comme prévu, la table a quand même un conflit à résoudre.

Une table de hachage ne promet donc pas une case unique pour chaque clé. Elle promet un moyen rapide de réduire la recherche, à condition que les collisions soient bien gérées.

Exemple détaillé : une table, une collision

Supposons qu’une table ait $8$ cases et utilise

$$h(k) = k \bmod 8$$

Insérez les clés $10$, $18$ et $7$.

D’abord, $10$ va dans la case $2$ parce que $10 \bmod 8 = 2$.

Ensuite, $18$ est lui aussi haché vers la case $2$, donc une collision se produit.

Puis $7$ va dans la case $7$, donc cette insertion n’entre pas en collision.

Le schéma utile est toujours le même :

1. Hacher la clé.
2. Aller à la case indiquée.
3. Si une autre clé s’y trouve déjà, appliquer la règle de collision.

Une fois ce schéma compris, les deux principales stratégies de gestion des collisions deviennent plus faciles à comprendre.

Chaînage vs adressage ouvert

Le chaînage garde un seau à chaque case

Dans le chaînage, chaque case stocke une petite collection d’entrées au lieu d’une seule.

Si $10$ et $18$ sont tous deux hachés vers la case $2$, le seau $2$ peut contenir

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Pour trouver la clé $18$, la table va directement au seau $2$ et compare seulement les entrées de ce seau.

Le chaînage est simple sur le plan conceptuel, et la suppression y est généralement plus facile qu’en adressage ouvert. En contrepartie, de longs seaux rendent les opérations plus lentes.

L’adressage ouvert reste à l’intérieur du tableau

En adressage ouvert, chaque case du tableau contient au plus une entrée. Si la case d’origine est occupée, la table sonde d’autres cases selon une règle fixe.

Une règle courante est le sondage linéaire : si la case $2$ est occupée, on essaie $3$, puis $4$, puis $5$, en revenant au début si nécessaire.

Cela évite des listes de seaux séparées, mais des cases remplies proches les unes des autres peuvent former des grappes. Un autre point important est que la recherche et la suppression doivent respecter la même règle de sondage que celle utilisée lors de l’insertion.

Quand $O(1)$ est une affirmation raisonnable

On décrit souvent les tables de hachage comme ayant une recherche, une insertion et une suppression en $O(1)$ en moyenne. Cette affirmation sur le cas moyen dépend de certaines conditions :

• la fonction de hachage répartit les clés de façon raisonnablement uniforme
• le facteur de charge reste maîtrisé
• la stratégie de collision est correctement implémentée

Le facteur de charge est le rapport

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Si la table devient trop remplie, les collisions deviennent plus fréquentes et les performances se dégradent. C’est pourquoi beaucoup d’implémentations redimensionnent le tableau au fur et à mesure qu’il se remplit.

Les performances dans le pire des cas peuvent tout de même se dégrader jusqu’à approcher $O(n)$ si trop de clés s’accumulent dans la même zone.

Erreurs fréquentes avec les tables de hachage

Penser que les collisions signifient que la fonction de hachage a échoué

Ce n’est pas le cas. Les collisions sont attendues. La vraie question est de savoir si la table les gère efficacement.

Considérer $O(1)$ comme inconditionnel

$O(1)$ décrit généralement le cas moyen, pas une promesse valable pour chaque entrée et à tout moment.

Confondre le hachage ici avec le chiffrement

Dans le contexte de base des structures de données, une fonction de hachage sert surtout à indexer rapidement, pas à garantir le secret. Ce sont deux objectifs différents.

Oublier de comparer la clé réelle

Deux clés peuvent avoir le même résultat de hachage. Après être arrivé dans le bon seau ou à la bonne position de sondage, la table doit encore vérifier si la clé correspond réellement.

Quand utilise-t-on les tables de hachage

Les tables de hachage sont utilisées chaque fois qu’une recherche rapide par clé est importante. Parmi les exemples courants, on trouve les dictionnaires, les tables de symboles, les caches, l’indexation et le comptage de fréquences dans des données.

Elles conviennent très bien quand la recherche exacte par clé est plus importante que le maintien des éléments dans un ordre trié. Si vous avez besoin d’un parcours ordonné, de requêtes par intervalle ou de valeurs les plus proches, une autre structure peut être préférable.

Essayez un exemple de collision similaire

Prenez un petit tableau de $8$ cases et utilisez $h(k)=k \bmod 8$. Insérez quelques clés comme $3$, $11$, $19$ et $27$. Puis résolvez les collisions une fois avec le chaînage et une fois avec le sondage linéaire.

Ce seul exercice rend l’idée principale très concrète : les collisions sont inévitables, et la règle de collision change le comportement de la table. Si vous voulez aller un peu plus loin, essayez votre propre version avec une taille de table différente et observez comment les collisions changent.