Chercher par clé, pas par position
Une table de hachage associe une clé unique à une valeur. Vous ne demandez pas « quelle valeur est à la position 12 ? », mais « quelle valeur appartient au matricule 12 ? ».
La clé est l'identité logique de la donnée. Un email peut identifier un compte, un code produit peut identifier un prix, un matricule peut identifier un étudiant. Si vous remettez une valeur avec la même clé, vous remplacez l'ancienne valeur. Vous ne créez pas une deuxième entrée avec la même identité.
| Besoin dominant | Structure naturelle | Question posée |
|---|---|---|
| Conserver un ordre ou travailler par position | List | Quel élément est à l'index i ? |
| Retrouver une donnée par identifiant | Map | Quelle valeur correspond à cette clé ? |
| Empiler ou dépiler | Pile | Quel élément a été ajouté en dernier ? |
L'API à reconnaître
En Java, programmez en général contre Map<K, V> et créez une HashMap<>(). Les opérations utiles ici sont put, get et containsKey. Nous reconstruisons une version simple pour comprendre ce qu'elles cachent.
La map naïve révèle le contrat
Commencez sans hachage. Une petite liste d'entrées suffit à offrir le bon contrat : chaque entrée contient une clé et une valeur, et get compare les clés jusqu'à trouver la bonne.
Ce qui fonctionne
- Le contrat clé vers valeur est déjà correct.
- Une clé existante est remplacée, pas dupliquée.
- Le code est facile à lire sur quelques entrées.
Ce qui coince
- Chaque recherche repart du début de la liste.
- Une entrée absente oblige à tout vérifier.
- Le nombre de comparaisons grandit avec la liste.
Ce que le hash change
- La clé produit directement une zone où regarder.
- La recherche globale devient une recherche locale.
- Il faut désormais gérer plusieurs clés dans la même zone.
Du hash à la case du tableau
Une fonction de hachage transforme la clé en nombre. Ce nombre ne contient pas la valeur et ne prouve pas l'identité de la clé. Il indique seulement où commencer la recherche.
Additionnez les caractères
Pour"bob", les codes sont 98, 111 et 98. La somme vaut 307.Ramenez le nombre dans le tableau
307 % 101vaut 4. La clé vise donc la case 4 d'un tableau de 101 cases.Vérifiez la clé stockée
Même après cet accès direct, comparez la clé demandée à la clé de l'entrée. Un index identique ne garantit jamais une clé identique.
Un hash pédagogique, exprès
La somme des caractères est facile à calculer de tête, donc utile pour les exercices. Elle répartit mal les clés : deux anagrammes ont la même somme. On ne vous demandera pas d'inventer une fonction de hash parfaite, ni de reproduire exactement String.hashCode().
Une collision ne peut pas être ignorée
"dan" donne aussi 100 + 97 + 110 = 307, donc la case 4. Deux clés différentes visent maintenant la même place : c'est une collision.
Piège fréquent : remettre la même clé n'est pas une collision
Une collision arrive quand deux clés différentes produisent le même index de départ.
put("bob", "42")
put("bob", "99")
Même clé : mise à jour. La valeur de "bob" devient "99".
Chaîne du bucket 4
Le dessin réduit le tableau à dix buckets pour rester lisible. Le calcul du cours et des QCM utilise bien le modulo 101.
Le vrai problème
Les collisions sont inévitables : il existe beaucoup plus de clés possibles que de cases. Une meilleure fonction les rend plus rares, elle ne les supprime pas. Une table de hachage doit donc décider comment stocker plusieurs clés qui commencent au même index.
Solution 1 : le chaînage séparé
Avec le chaînage séparé, chaque case du tableau contient une petite liste. Le hash choisit le bucket, puis on compare seulement les clés de cette liste locale.
Le ListIterator avance lien par lien et remplace l'entrée courante sans repartir de la tête de la liste.
Le hash choisit le bucket
"bob"et"dan"arrivent tous les deux au bucket 4.put cherche localement
Si la clé existe déjà dans ce bucket, sa valeur est remplacée. Sinon, une nouvelle entrée est ajoutée à la petite liste.get refait le début du trajet
Il calcule le même bucket puis compare les clés locales. Il ne renvoie jamais la première valeur sans vérifier sa clé.
Solution 2 : le sondage
Avec le sondage, aucune petite liste n'est ajoutée. En cas de collision, on reste dans le tableau et on essaie d'autres cases selon une règle précise.
La règle qui fait ou casse get
La lecture doit refaire exactement la même suite de cases que l'insertion. Si put passe de 4 à 5 puis 6, mais que get ne regarde que 4, une entrée présente semblera absente. À chaque case occupée, vérifiez aussi la clé réelle.
Le modulo fait reboucler la recherche au début du tableau. Avec une capacité de 10, la case qui suit 9 est 0. Après autant d'essais qu'il y a de cases, aucune place n'est disponible : la table est pleine.
Les trois stratégies de sondage
Les trois stratégies changent seulement la suite d'indices essayés. Elles gardent le même devoir : put et get suivent la même formule, rebouclent dans le tableau et s'arrêtent après un nombre d'essais borné.
Tracez la même insertion trois fois
Pour un départ en case 4, le linéaire essaie 4, 5, 6, 7. Le quadratique essaie 4, 5, 8, 13. Avec un pas secondaire de 15, le double hashing essaie 4, 19, 34, 49. Dans les trois cas, put s'arrête sur la première case vide ou la même clé, et get sur la même clé, une case vide ou la limite d'essais.
| Stratégie | Suite depuis i | Force | Limite |
|---|---|---|---|
| Linéaire | i, i+1, i+2… | La plus simple à tracer et à coder. | Les entrées forment vite des groupes compacts. |
| Quadratique | i, i+1², i+2², i+3²… | S'éloigne plus vite du premier groupe rempli. | La taille du tableau et la suite choisie demandent de la prudence. |
| Double hashing | i, i+pas, i+2×pas… | Le pas, calculé depuis secondHash(key), dépend de la clé et répartit mieux les trajets. | Le pas doit être premier avec la capacité, pas seulement non nul. |
Même niveau, même attente
Sachez tracer les trois suites, expliquer leur différence et annoncer leur compromis. Le sondage linéaire reste le plus facile à écrire sous pression, mais les deux autres ne sont pas des annexes. Le quadratique peut revisiter des cases avant d'avoir parcouru tout le tableau : sa formule et la capacité doivent être choisies ensemble.
Choisir et défendre une représentation
Chaînage
Sondage
- Tout reste dans un seul tableau compact.
- Les groupes remplis allongent les trajets.
- Une table entièrement pleine doit produire une erreur.
Votre justification
- Nommez l'opération fréquente et la représentation choisie.
- Tracez les cases réellement consultées.
- Donnez le cas qui dégrade votre choix.
Ce que cette leçon ne traite pas
Pas de suppression, donc pas de marqueur de case supprimée. Pas de redimensionnement, de facteur de charge ni d'itération. Ces sujets changeraient plusieurs invariants à la fois et ne sont pas demandés pour la remédiation.
Vérifiez vos réflexes
Vérifiez vos réflexes
Une réponse par question. La correction apparaît tout de suite.
Continuez le parcours
Vous savez maintenant partir d'un contrat clé-valeur, calculer une case et suivre une collision. Les leçons voisines montrent d'autres compromis de représentation et une autre structure de recherche.