Le vestiaire du gymnase
Au gymnase, le vestiaire a des casiers numérotés. Le prof dit : « Ton nom donne ton numéro de casier. »
Pas besoin de tout fouiller. Tu calcules ton numéro, tu ouvres le casier, c’est là.
C’est ainsi qu’un dictionnaire retrouve une valeur très vite.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Dictionnaire | Une structure qui retrouve une valeur à partir de sa clé. | {"Lina": "0611"} |
| Clé | Le nom avec lequel on cherche. Elle est unique. | "Lina" |
| Casier | Une case de la table où on range des paires. | table[3] |
| Fonction de hachage | Une fonction qui transforme une clé en numéro de casier. | numero_casier("Lina", 5) |
| Collision | Deux clés qui tombent dans le même casier. | Lina et Hugo : casier 3 |
| Table de hachage | La table de casiers qui est le cœur d’un dictionnaire. | cinq casiers |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : trouve le casier
À toi de jouer
À toi : trouve le casier
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
De la clé au casier
Un dictionnaire garde ses paires dans une table de casiers. Pour savoir où ranger une clé, on calcule.
Voici un calcul simple : on additionne les codes des lettres. Puis on prend le reste de la division par le nombre de casiers.
Le reste est toujours entre 0 et le nombre de casiers moins un.
Exemple travaillé : calculer les casiers
| Clé | Somme des codes | Division par 5 | Casier |
|---|---|---|---|
| Lina | 76 + 105 + 110 + 97 = 388 | 388 = 5 × 77 + 3 | 3 |
| Karim | 500 | 500 = 5 × 100 + 0 | 0 |
| Zoe | 302 | 302 = 5 × 60 + 2 | 2 |
| Hugo | 403 | 403 = 5 × 80 + 3 | 3 |
| Emma | 384 | 384 = 5 × 76 + 4 | 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : la fonction qui trouve le casier
def numero_casier(cle, taille):
total = 0
for lettre in cle:
total = total + ord(lettre) # ord donne le code de la lettre
return total % taille # le reste de la division donne le casier
for nom in ["Lina", "Karim", "Zoe", "Hugo", "Emma"]:
print(nom, "-> casier", numero_casier(nom, 5))
# Lina et Hugo tombent dans le même casier. On appelle cela une collision.
À toi : un reste à la main
À toi de jouer
À toi : un reste à la main
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.