Skip to main content Informatique en prépa - Lycée Malherbe 

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

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 qui associe à chaque clé un entier. Pour une table de cases, on range la clé dans la case .

Par exemple, prenons comme fonction de hachage pour les chaînes de caractères : la somme des codes des lettres de (le code de "a" est 97, celui de "b" est 98, etc.). Avec une table de cases :

clé case
"pomme"5422
"kiwi"4360
"poire"5433
"mangue"6371

Pour chercher la valeur associée à "poire", pas besoin de parcourir la table : on calcule et on regarde directement dans la case 3. Le calcul de ne dépend que de la longueur de la clé, pas du nombre d'éléments dans la table.

Une bonne fonction de hachage doit :

Python fournit une fonction de hachage, hash :

Python

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 cases

Le 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" : , et , la même case que "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) :

T 0 1 2 3 k ("kiwi", 5) T:c0->k m ("mangue", 4) T:c1->m p ("pomme", 3) T:c2->p q ("poire", 2) T:c3->q f ("fraise", 6) p->f

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 "seaux" :

Python

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 clés dans une table de cases, le taux de remplissage est : c'est le nombre moyen d'éléments par seau. Une recherche coûte en moyenne : le calcul du hachage, puis le parcours d'un seau.

Pour que les opérations restent en temps constant, il faut que reste borné. Quand la table est trop remplie (par exemple quand dépasse 1), on crée une table deux fois plus grande et on y réinsère toutes les clés (elles changent de case, puisque a changé). Cette opération coûte , mais elle est rare : comme pour 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 . Si on modifie ensuite L[1] = 3, la clé devient [1, 3], dont le hachage est différent : si on la cherche, on calcule par exemple , on regarde dans la case 2... et on ne la trouve pas, alors qu'elle est bien dans la table, dans la case 1.

T 0 1 2 3 cle ([1, 3], ...) rangée quand elle valait [1, 2] T:c1->cle rech recherche de [1, 3] rech->T:c2

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.

Python

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.

Python

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 n'est calculé qu'une fois.

Exercices

Exercice 1

Ajouter à la table de hachage ci-dessus une fonction supprimer(table, cle) qui supprime la clé (si elle est présente).

Python

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)
            return
Exercice 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 ?

Réponse

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 .

Python

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 à n'est calculée qu'une fois : il y a appels, contre un nombre exponentiel pour la version naïve.