3- Dictionnaires et hachage
On a utilisé les dictionnaires en première année comme une "boîte noire" : on sait que l'accès, l'insertion et le test d'appartenance sont en temps constant (en moyenne). Voyons comment c'est possible.
I. Rappels : les dictionnaires en Python
Loading editor...
d = {"pomme": 3, "kiwi": 5} # création
d["poire"] = 2 # insertion
d["pomme"] += 1 # modification
print(d["pomme"], len(d)) # accès, taille
print("kiwi" in d) # présence d'une clé
del d["kiwi"] # suppression
for (cle, valeur) in d.items(): # parcours (aussi : d.keys(), d.values())
print(cle, valeur)II. Le principe du hachage
a) Idée
Dans une liste, l'accès à L[i] est en temps constant : l'élément d'indice i est rangé à un emplacement de la mémoire qu'on peut calculer directement à partir de i.
L'idée du hachage est de faire la même chose avec des clés quelconques : on transforme chaque clé en un entier, grâce à une fonction de hachage, et on range la valeur dans une liste à l'indice correspondant.
Définition : fonction de hachage
Une fonction de hachage est une fonction
Par exemple, prenons comme fonction de hachage pour les chaînes de caractères : "a" est 97, celui de "b" est 98, etc.). Avec une table de
| clé | case | |
|---|---|---|
"pomme" | 542 | 2 |
"kiwi" | 436 | 0 |
"poire" | 543 | 3 |
"mangue" | 637 | 1 |
Pour chercher la valeur associée à "poire", pas besoin de parcourir la table : on calcule
Une bonne fonction de hachage doit :
- être déterministe : la même clé donne toujours le même entier (sinon on ne retrouve plus la clé !) ;
- être rapide à calculer ;
- bien répartir les clés entre les cases. Par exemple, la fonction « code de la première lettre » serait une mauvaise fonction de hachage :
"pomme","poire"et"prune"tomberaient toutes dans la même case.
Python fournit une fonction de hachage, hash :
Loading editor...
print(hash("pomme"))
print(hash(42))
print(hash((1, 2)))
print(hash("pomme") % 8) # la case où ranger "pomme" dans une table de 8 casesLe hash d'une chaîne de caractères change d'une exécution de Python à l'autre (pour des raisons de sécurité : il ne faut pas qu'un attaquant puisse prévoir les collisions), mais il reste le même pendant toute une exécution. Celui d'un entier est l'entier lui-même (pour les entiers pas trop grands).
b) Collisions
Deux clés différentes peuvent tomber dans la même case : c'est une collision. Dans l'exemple ci-dessus, si on ajoute la clé "fraise" : "pomme" !
Les collisions sont inévitables : il y a beaucoup plus de clés possibles que de cases. Une solution simple est de stocker dans chaque case la liste des couples (clé, valeur) qui y tombent. On appelle ces listes des seaux (buckets en anglais) :
Pour chercher "fraise", on calcule sa case (2), puis on parcourt le seau de la case 2 en comparant chaque clé avec "fraise".
Voici une implémentation minimale d'une table de hachage, avec une liste de
Loading editor...
def creer_table(m):
return [[] for _ in range(m)]
def inserer(table, cle, valeur):
seau = table[hash(cle) % len(table)]
for i in range(len(seau)):
if seau[i][0] == cle: # la clé est déjà présente : on remplace la valeur
seau[i] = (cle, valeur)
return
seau.append((cle, valeur))
def chercher(table, cle):
seau = table[hash(cle) % len(table)]
for (c, v) in seau:
if c == cle:
return v
return None
table = creer_table(4)
for (fruit, prix) in [("pomme", 3), ("kiwi", 5), ("poire", 2), ("mangue", 4), ("fraise", 6)]:
inserer(table, fruit, prix)
print(table)
print(chercher(table, "poire"), chercher(table, "banane"))(Ici, on utilise le hash de Python : les clés ne sont pas forcément rangées dans les mêmes cases que sur le dessin, et cela change d'une exécution à l'autre.)
Si la fonction de hachage répartit bien les clés, et si la table a assez de cases (Python l'agrandit automatiquement quand elle se remplit), chaque seau contient peu d'éléments : les opérations sont en temps constant en moyenne. Dans le pire cas (toutes les clés dans le même seau), elles deviennent linéaires.
Taux de remplissage
Avec
Pour que les opérations restent en temps constant, il faut que append sur les listes, le coût moyen d'une insertion reste constant.
Il existe d'autres façons de gérer les collisions. Par exemple, l'adressage ouvert : chaque case contient au plus un couple, et si la case est occupée, on essaie une autre case selon une règle fixée (par exemple la case suivante, puis la suivante, etc.). Les dictionnaires de Python utilisent une variante de l'adressage ouvert, mais le principe du hachage reste le même.
III. Limitation : quelles clés ?
Pour retrouver une clé, il faut que son hachage ne change jamais. Si on pouvait modifier une clé après l'avoir insérée, elle ne serait plus dans le bon seau !
Imaginons qu'on puisse utiliser une liste L = [1, 2] comme clé, et qu'elle soit rangée dans la case 1 parce que L[1] = 3, la clé devient [1, 3], dont le hachage est différent : si on la cherche, on calcule par exemple
C'est pourquoi les clés d'un dictionnaire doivent être non mutables (on dit hachables) : entiers, flottants, chaînes de caractères, tuples (de valeurs non mutables)... mais pas de listes ni de dictionnaires.
Loading editor...
d = {}
d[(1, 2)] = "un tuple : autorisé"
print(d)
d[[1, 2]] = "une liste : interdit"Pour utiliser une liste comme clé, on la convertit en tuple : d[tuple(L)].
IV. Lien avec la mémoïsation
En programmation dynamique, la mémoïsation consiste à stocker les résultats déjà calculés d'une fonction récursive, pour ne pas les recalculer. Un dictionnaire est idéal pour cela : les clés sont les arguments (sous forme de tuple s'il y en a plusieurs), les valeurs sont les résultats.
Loading editor...
def nb_chemins(i, j, memo):
"""Nombre de chemins de (0, 0) à (i, j) en allant vers la droite ou vers le bas."""
if i == 0 or j == 0:
return 1
if (i, j) not in memo:
memo[(i, j)] = nb_chemins(i - 1, j, memo) + nb_chemins(i, j - 1, memo)
return memo[(i, j)]
memo = {}
print(nb_chemins(15, 15, memo))
print(len(memo), "valeurs calculées")Sans mémoïsation, le nombre d'appels serait exponentiel ; avec, chaque couple
Exercices
Exercice 1
Ajouter à la table de hachage ci-dessus une fonction supprimer(table, cle) qui supprime la clé (si elle est présente).
Loading editor...
def supprimer(table, cle):
seau = table[hash(cle) % len(table)]
for i in range(len(seau)):
if seau[i][0] == cle:
seau.pop(i)
returnExercice 2
Avec une table de 4 cases, on insère 1000 clés. Combien d'éléments y a-t-il en moyenne par seau ? Quel est alors le coût d'une recherche ? Que faut-il faire pour garder des opérations en temps constant ?
250 éléments par seau en moyenne : une recherche parcourt un seau, soit environ 250 comparaisons. Il faut agrandir la table quand elle se remplit (par exemple doubler le nombre de cases quand il y a plus d'éléments que de cases), et réinsérer tous les éléments : c'est ce que fait Python.
Exercice 3
Écrire une version mémoïsée (avec un dictionnaire) de la fonction de Fibonacci, et comparer le nombre d'appels avec la version naïve pour
Loading editor...
def fib(n, memo):
if n <= 1:
return 1
if n not in memo:
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n] Chaque valeur de