Retrouver une fiche parmi 30 000
Une table de hachage range des paires clé-valeur et retrouve une clé en quelques étapes, sans tout parcourir. C’est la structure qui se cache derrière un dictionnaire Python.
La bibliothèque d’une université garde 30 000 fiches d’étudiants. Dans une liste non triée, trouver un numéro demande jusqu’à 30 000 étapes. Une table de hachage calcule d’abord où regarder.
À la fin de cette leçon
Remarque
Je peux expliquer comment une table de hachage retrouve une clé rapidement.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Table de hachage | une structure qui retrouve une valeur à partir de sa clé | |
| Clé | ce que l’on cherche, comme un numéro d’étudiant | "Lea" |
| Fonction de hachage | un calcul qui transforme une clé en numéro d’alvéole | |
| Alvéole | une case de la table, qui peut contenir plusieurs paires | |
| Collision | deux clés qui tombent dans la même alvéole | |
| Chaînage | garder dans chaque alvéole la liste de ses paires |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction de hachage donne l’alvéole
Une table de hachage est un tableau d’alvéoles. Pour ranger une clé, une fonction de hachage la transforme en numéro d’alvéole.
Notre fonction simple additionne les codes des lettres, puis garde le reste de la division par le nombre d’alvéoles. Le même calcul retrouve la clé plus tard : on ne cherche qu’au bon endroit.
Exemple travaillé : hacher des prénoms (7 alvéoles)
| Clé | Somme des codes | Reste modulo 7 | Alvéole |
|---|---|---|---|
| Lea | 274 | 274 = 39 × 7 + 1 | 1 |
| Max | 294 | 294 = 42 × 7 + 0 | 0 |
| Tom | 304 | 304 = 43 × 7 + 3 | 3 |
| Eva | 284 | 284 = 40 × 7 + 4 | 4 |
| Ines | 399 | 399 = 57 × 7 + 0 | 0 |
| Zoe | 302 | 302 = 43 × 7 + 1 | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Calculer une alvéole dans le labo
Python donne le code d’une lettre avec ord. La première commande affiche les codes de A et de a. La deuxième additionne les codes de Lea et garde le reste modulo 7, ce qui donne son alvéole.
La troisième affiche le hachage de deux entiers : pour un entier, Python rend l’entier lui-même.
Le code d’une lettre
python3 -c "print(ord('A'), ord('a'))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
L’alvéole de Lea
python3 -c "print(sum(ord(c) for c in 'Lea') % 7)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le hachage de deux entiers
python3 -c "print(hash(42), hash(7))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une collision : deux clés dans une alvéole
Dans le tableau ci-dessus, Max et Ines tombent tous deux dans l’alvéole 0. C’est une collision. Elle est normale, car il y a bien plus de clés possibles que d’alvéoles.
Le chaînage la règle : chaque alvéole garde une petite liste de paires. Pour chercher, on calcule l’alvéole, puis on regarde les quelques paires qu’elle contient.
Exemple travaillé : la table après les six ajouts
| Alvéole | Paires rangées |
|---|---|
| 0 | Max, Ines |
| 1 | Lea, Zoe |
| 2 | Vide |
| 3 | Tom |
| 4 | Eva |
| 5 | Vide |
| 6 | Vide |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un dictionnaire Python à lancer
# Un dictionnaire Python est une table de hachage.
notes = {}
notes["Lea"] = 15
notes["Max"] = 12
notes["Ines"] = 17
print(notes["Max"])
print("Tom" in notes)
# Ajoutez Tom avec la note 9, puis relancez.
Une table assez grande reste rapide
Si la fonction répartit bien les clés, chaque alvéole en contient peu. Chercher coûte alors quelques étapes, même avec un million de clés. Il faut seulement agrandir la table quand elle se remplit.
Avec une très mauvaise fonction, toutes les clés tombent dans la même alvéole. La table devient alors une simple liste, lente à parcourir.
Exemple travaillé : le remplissage de la table
| Clés | Alvéoles | Paires par alvéole en moyenne |
|---|---|---|
| 100 | 10 | 10 |
| 100 | 100 | 1 |
| 100 | 1 000 | 0,1 |
| 100 | 1, mauvaise fonction | 100 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Erreur fréquente
Attention
Beaucoup d’étudiants pensent qu’une collision est une erreur, ou que la seconde clé écrase la première. Ce n’est pas vrai. Avec le chaînage, les deux paires partagent l’alvéole et restent toutes deux là. Une collision ne perd aucune donnée.
Pour aller plus loin
Avec la somme des codes, les mots abc, cba et bca tombent toujours dans la même alvéole. Dites pourquoi.
Proposez une fonction de hachage qui les sépare, par exemple en multipliant le code de chaque lettre par sa position. Testez-la sur ces trois mots.