Coder une table de hachage en Python étape par étape

Le dictionnaire est probablement la structure la plus utilisée du Python moderne. Une simple ligne users[email] = profil cache une mécanique sophistiquée : fonction de hachage, sondage de collisions, redimensionnement automatique, gestion des suppressions par sentinelle. Ce tutoriel construit une table de hachage de zéro avec adressage ouvert et sondage linéaire — c’est-à-dire la même famille d’algorithmes que celle utilisée par CPython sous le capot. À la fin, vous aurez une classe qui se comporte comme un mini-dict et vous comprendrez précisément ce que payent les milliers de lookups quotidiens dans votre code.

Pour la vue d’ensemble des structures de données et des algorithmes, lire d’abord le guide principal Algorithmes et structures de données : repères 2026 pour devs.

Prérequis

• Python 3.10 ou plus récent
• Bases sur les listes Python, les tuples, les méthodes spéciales (__getitem__, __setitem__)
• Avoir lu, idéalement, le tutoriel Implémenter une liste chaînée en Python de cette série pour le réflexe sur les cas limites
• Niveau attendu : intermédiaire
• Temps estimé : 60 minutes

Étape 1 — Comprendre l’idée du hachage

Le principe de la table de hachage tient en une phrase : transformer une clé arbitraire en un index dans un tableau, par une fonction déterministe qu’on appelle fonction de hachage. Si la fonction est rapide et bien répartie, l’accès devient O(1) en moyenne — on calcule l’index, on lit la case, fini. Le problème, c’est que deux clés différentes peuvent produire le même index : c’est une collision. La stratégie pour résoudre les collisions distingue les grandes familles de tables de hachage. CPython, et ce tutoriel, utilisent l’adressage ouvert avec sondage linéaire : quand la case est occupée, on essaie la suivante, et ainsi de suite jusqu’à trouver une case libre.

L’autre famille, le chaînage séparé, stocke à chaque index une liste chaînée des paires qui s’y projettent. C’est plus simple à implémenter mais moins efficace en cache : les listes chaînées dispersent les données en mémoire alors que l’adressage ouvert garde tout dans un seul tableau contigu. Pour des tables qui tiennent en mémoire vive et qu’on consulte souvent, l’adressage ouvert gagne presque toujours. C’est pour cette raison que les implémentations modernes (CPython, V8 pour JavaScript, hashbrown pour Rust) y sont passées.

Étape 2 — Définir la classe et les sentinelles

On démarre avec trois constantes de classe : la capacité initiale (une puissance de 2 pour faciliter les calculs), le facteur de charge à partir duquel on redimensionne (2/3 comme CPython, ce qui garde les chaînes de sondage courtes), et une sentinelle TOMBSTONE qui marque les cases supprimées. La sentinelle est cruciale : si on remettait simplement None, les sondages s’arrêteraient prématurément et on ne retrouverait plus les clés stockées plus loin dans la chaîne.

class HashMap:
    INITIAL_CAPACITY = 8
    LOAD_FACTOR = 2 / 3
    TOMBSTONE = object()  # sentinelle unique pour les suppressions

    def __init__(self):
        self._capacity = self.INITIAL_CAPACITY
        self._buckets = [None] * self._capacity
        self._size = 0

    def __len__(self):
        return self._size

Notez le choix de object() pour la sentinelle. Toute autre valeur — chaîne spéciale, tuple bizarre, entier négatif — pourrait par malchance être stockée comme vraie clé par l’utilisateur. Un object() tout neuf, comparé avec is, ne peut pas entrer en collision avec une vraie donnée parce que personne d’autre dans le programme ne tient une référence vers lui. C’est l’astuce standard pour les sentinelles uniques en Python.

Étape 3 — La fonction de hachage et le sondage

On délègue le hachage à la fonction intégrée hash() de Python, qui sait gérer correctement les chaînes (avec SipHash13 depuis la 3.11), les nombres, les tuples immuables. Le modulo par la capacité ramène l’index dans la plage [0, capacity[. Le sondage linéaire avance ensuite case par case si la cible est occupée. La méthode _probe renvoie soit l’index où la clé est déjà présente, soit l’index où on peut l’insérer, en privilégiant les tombstones rencontrées en chemin pour recycler l’espace.

    def _hash(self, key):
        return hash(key) % self._capacity

    def _probe(self, key):
        """Sondage linéaire. Renvoie l'index de la clé si présente,
        ou l'index où l'insérer (en réutilisant un tombstone si possible)."""
        idx = self._hash(key)
        first_tombstone = -1
        while True:
            slot = self._buckets[idx]
            if slot is None:
                return first_tombstone if first_tombstone >= 0 else idx
            if slot is self.TOMBSTONE:
                if first_tombstone < 0:
                    first_tombstone = idx
            elif slot[0] == key:
                return idx
            idx = (idx + 1) % self._capacity

L'invariant clé du sondage : on s'arrête uniquement sur None (case jamais occupée) ou sur la clé recherchée. Une TOMBSTONE n'arrête pas le parcours, parce que la clé qu'on cherche pourrait avoir été insérée plus loin dans la chaîne après une suppression. La variable first_tombstone mémorise la première case recyclable rencontrée — c'est elle qu'on renverra si la clé n'existe pas encore, ce qui maintient les chaînes de sondage compactes au fil du temps. Sans cette astuce, un cycle d'insertions et suppressions saturerait la table de tombstones et ferait dégénérer les performances.

Étape 4 — Insertion et lecture

Avec _probe en place, l'insertion et la lecture deviennent presque triviales. __setitem__ appelle _probe, traite le cas où l'index renvoyé contient une vraie paire (mise à jour) ou pas (insertion + incrément du compteur). On ajoute en tête le redimensionnement préventif : si on dépasse le facteur de charge, on double la capacité avant d'insérer, ce qui garantit qu'il restera de la place et que les chaînes de sondage ne s'allongent pas trop.

    def __setitem__(self, key, value):
        if (self._size + 1) > self._capacity * self.LOAD_FACTOR:
            self._resize(self._capacity * 2)
        idx = self._probe(key)
        slot = self._buckets[idx]
        if slot is None or slot is self.TOMBSTONE:
            self._buckets[idx] = (key, value)
            self._size += 1
        else:
            self._buckets[idx] = (key, value)  # mise à jour

    def __getitem__(self, key):
        idx = self._probe(key)
        slot = self._buckets[idx]
        if slot is None or slot is self.TOMBSTONE:
            raise KeyError(key)
        return slot[1]

    def __contains__(self, key):
        idx = self._probe(key)
        slot = self._buckets[idx]
        return slot is not None and slot is not self.TOMBSTONE

Une fois ces trois méthodes en place, on peut déjà tester : m = HashMap(); m["a"] = 1; m["b"] = 2; print(m["a"]) doit afficher 1, et "a" in m doit renvoyer True. Si vous insérez une clé qui n'existe pas et que vous la cherchez ensuite, __getitem__ doit lever KeyError — c'est l'API standard des dictionnaires Python, et la respecter rend la classe interchangeable avec dict dans le reste du code.

Étape 5 — Suppression avec tombstone

Supprimer une entrée semble trivial — on remet None à sa place. C'est faux. Si la clé qu'on supprime fait partie d'une chaîne de sondage, la remettre à None casse l'invariant du sondage : la prochaine recherche d'une clé plus loin dans la chaîne s'arrêtera sur ce None et déclarera la clé absente alors qu'elle est bien là. La solution est la tombstone : un marqueur qui dit "cette case a été occupée mais ne l'est plus", qui n'arrête pas le sondage mais peut être recyclé à la prochaine insertion qui passe par là.

    def __delitem__(self, key):
        idx = self._probe(key)
        slot = self._buckets[idx]
        if slot is None or slot is self.TOMBSTONE:
            raise KeyError(key)
        self._buckets[idx] = self.TOMBSTONE
        self._size -= 1

Testez le cycle complet : insérer "a", "b", "c" qui se hashent successivement à des positions voisines, supprimer "b", puis demander "c". Sans tombstone, la recherche de "c" trouverait la case None laissée par "b" et lèverait KeyError. Avec tombstone, le sondage saute la case et finit par trouver "c" plus loin. C'est ce mécanisme, invisible mais essentiel, qui rend les tables de hachage à adressage ouvert robustes en présence de suppressions fréquentes.

Étape 6 — Redimensionnement

Quand le facteur de charge est dépassé, il faut agrandir le tableau pour garder les opérations rapides. La méthode _resize alloue un nouveau tableau plus grand (généralement le double, parfois plus si la table contient beaucoup de tombstones), réinitialise le compteur de taille, puis réinsère chaque paire valide. La réinsertion repasse par __setitem__, ce qui recalcule les positions selon la nouvelle capacité — on ne peut pas simplement copier les cases parce que les modulos ont changé.

    def _resize(self, new_capacity):
        old_buckets = self._buckets
        self._capacity = new_capacity
        self._buckets = [None] * new_capacity
        self._size = 0
        for slot in old_buckets:
            if slot is not None and slot is not self.TOMBSTONE:
                self[slot[0]] = slot[1]

Le redimensionnement coûte O(n) puisqu'on réinsère tous les éléments. C'est précisément ce qui rend la complexité O(1) amortie et non O(1) absolue : un appel sur N à __setitem__ paye le redimensionnement, mais sa fréquence décroît exponentiellement à mesure que la table grossit, donc le coût moyen reste constant. Sur une trace de 100 000 insertions, vous verrez quelques pics de latence isolés (les redimensionnements) noyés dans des dizaines de milliers d'insertions instantanées.

Étape 7 — Itération et __repr__

Pour rendre la classe agréable à utiliser, il manque l'itération sur les clés et une représentation lisible. L'itération filtre les None et les tombstones et ne renvoie que les clés réelles. La représentation les formate sous une forme proche de celle de dict, ce qui aide au débogage : un print(m) doit afficher quelque chose qui ressemble à ce qu'on attend.

    def __iter__(self):
        for slot in self._buckets:
            if slot is not None and slot is not self.TOMBSTONE:
                yield slot[0]

    def items(self):
        for slot in self._buckets:
            if slot is not None and slot is not self.TOMBSTONE:
                yield slot

    def __repr__(self):
        pairs = ', '.join(f"{k!r}: {v!r}" for k, v in self.items())
        return "{" + pairs + "}"

Avec ces ajouts, la classe est utilisable comme un mini-dict. Tester for k in m: print(k, m[k]) doit fonctionner et lister toutes les paires sans afficher les sentinelles. Notez que l'ordre d'itération ici suit l'ordre des cases internes, donc dépend du hachage — il n'a aucune raison d'être l'ordre d'insertion. Le dict standard de Python, depuis la 3.7, garantit l'ordre d'insertion grâce à un mécanisme dual (un tableau d'indices et un tableau d'entrées en ordre d'arrivée), qu'on n'implémente pas ici par simplicité.

Étape 8 — Vérification

Le test final couvre l'insertion, la mise à jour, la lecture, la suppression, la réinsertion après suppression (qui doit recycler la tombstone), le déclenchement du redimensionnement, et les KeyError attendues. Si tout passe, vous tenez une implémentation correcte au sens où elle respecte les invariants du sondage et la sémantique des dictionnaires Python.

if __name__ == "__main__":
    m = HashMap()
    assert len(m) == 0

    # Insertions et lectures
    for i, k in enumerate(["a", "b", "c", "d", "e"]):
        m[k] = i
    assert m["c"] == 2
    assert "a" in m and "z" not in m
    assert len(m) == 5

    # Mise à jour (pas d'incrément de taille)
    m["a"] = 99
    assert m["a"] == 99
    assert len(m) == 5

    # Suppression et réinsertion
    del m["b"]
    assert "b" not in m
    assert len(m) == 4
    m["b"] = 42
    assert m["b"] == 42
    assert len(m) == 5

    # Déclenchement du redimensionnement
    for k in range(100):
        m[k] = k * k
    assert m[10] == 100
    assert len(m) >= 100

    # KeyError attendu
    try:
        _ = m["pas-la"]
    except KeyError:
        pass
    else:
        raise AssertionError("KeyError attendu")

    print("Tous les tests passent.")

Lancez python table_hachage.py et vous devez voir le message Tous les tests passent.. Pour aller plus loin, mesurez le temps moyen d'insertion sur 1 million de clés avec votre implémentation et avec dict — vous verrez l'écart, considérable, qui justifie d'utiliser dict en production. dict est écrit en C, profite de la cache du processeur, et utilise des tables d'indices compactes pour la version 3.6+ ; il est de l'ordre de 30 à 100 fois plus rapide qu'une implémentation Python pure équivalente.

Erreurs fréquentes

Erreur	Cause	Solution
Performances qui s'effondrent après beaucoup de suppressions	Tombstones accumulées qui allongent les chaînes de sondage	Redimensionner aussi quand le ratio (size + tombstones) / capacity dépasse le seuil, pas seulement size / capacity
KeyError imprévue sur une clé qu'on vient d'insérer	None remis en suppression au lieu d'une tombstone	Toujours utiliser une sentinelle object() distincte
Sondage qui boucle à l'infini	Table totalement pleine sans None	Maintenir le facteur de charge strictement < 1 et redimensionner avant l'insertion
Hachage non uniforme → pics O(n)	Fonction de hachage maison mauvaise, ou clés malicieuses	S'appuyer sur hash() intégré ; pour la culture, lire sur les attaques par collisions HashDoS
Clé mutable utilisée comme clé	Listes ou dicts utilisés comme clés → TypeError: unhashable type	N'utiliser que des clés immuables (str, int, tuple de types immuables)

Comparaison rapide avec dict

Le dict de CPython et notre HashMap partagent la famille (adressage ouvert) mais divergent sur plusieurs détails de production. dict sépare un tableau d'indices compact (entiers de 1, 2, 4 ou 8 octets selon la taille) d'un tableau d'entrées dense, ce qui réduit la mémoire pour les tables peu remplies et préserve l'ordre d'insertion. Il utilise une stratégie de sondage perturbé (basée sur les bits de poids fort du hachage) plus résistante aux entrées adverses que le sondage linéaire pur. Et il bénéficie d'une implémentation en C qui élimine le coût des appels de méthode Python.

Notre implémentation a le mérite d'être lisible en moins de cent lignes — c'est l'objectif pédagogique. En production, restez sur dict, sauf cas exotiques où un comportement spécifique justifie une réécriture (cache LRU avec contrainte de taille fixe, table partagée entre processus en mémoire, structure persistée disque). Et même alors, regardez d'abord du côté des bibliothèques tierces matures (functools.lru_cache, cachetools, diskcache) avant d'écrire la vôtre.

Stratégies de sondage : linéaire, quadratique, double hachage

Notre implémentation utilise le sondage linéaire : si la case i est occupée, on essaie i + 1, puis i + 2, etc. C'est simple à coder et excellent pour la cache du processeur, parce que les cases voisines sont contiguës en mémoire et préchargées en blocs. Le défaut est le clustering primaire : les chaînes d'occupation se collent les unes aux autres et grossissent ensemble, ce qui allonge les sondages au fil du temps. Pour une charge inférieure à 50 %, le phénomène est négligeable ; au-delà de 70 %, il devient sensible — raison pour laquelle on redimensionne avant.

Le sondage quadratique parcourt i, i + 1, i + 4, i + 9, ... en utilisant les carrés des entiers. Il dilue le clustering primaire mais en introduit un autre, le clustering secondaire : deux clés dont le hachage initial coïncide suivent la même séquence de sondage. Le double hachage fait varier l'incrément en fonction d'une seconde fonction de hachage, ce qui élimine les deux types de clustering au prix d'une seconde évaluation et d'une moins bonne localité de cache. CPython utilise une variante perturbée du sondage linéaire qui mélange les bits de poids fort du hachage à chaque étape — un compromis entre la simplicité du sondage linéaire et la dispersion du double hachage.

Sécurité : attaques par collisions

En 2003, Crosby et Wallach ont publié un article qui montrait qu'un attaquant pouvait paralyser un serveur web en envoyant des paramètres POST dont les noms entraient tous en collision dans la table de hachage utilisée pour stocker les variables. Le sondage devenait O(n) systématiquement, et l'analyse de la requête, censée être O(n), passait à O(n²) — quelques milliers de paramètres suffisaient à bloquer un Apache pendant des minutes. Cette classe d'attaques s'appelle HashDoS, et elle a forcé tous les langages modernes à randomiser leur fonction de hachage à chaque démarrage du processus.

En Python, c'est l'objet de PYTHONHASHSEED et du passage à SipHash13 pour les chaînes depuis la 3.11. Concrètement, deux exécutions du même script produisent des hachages différents pour les mêmes chaînes — ce qui rend l'ordre d'itération d'un dictionnaire potentiellement différent d'un lancement à l'autre, mais surtout empêche un attaquant de calculer à l'avance des collisions exploitables. Si vous écrivez un service réseau qui accepte des entrées arbitraires, ne désactivez jamais cette randomisation et n'écrivez pas votre propre fonction de hachage maison sans randomisation par session.

Tutoriels suivants

• Programmer le tri rapide (quicksort) en Python — on quitte les structures associatives pour les algorithmes par diviser-pour-régner.
• Implémenter le parcours BFS sur un graphe en Python — le dictionnaire devient l'outil clé pour stocker la liste d'adjacence.
• Implémenter une liste chaînée en Python étape par étape — à lire avant si la manipulation de pointeurs vous échappe.

Pour aller plus loin

• Retour au guide principal : Algorithmes et structures de données : repères 2026 pour devs
• Documentation officielle Python — dictionnaires
• Code source CPython — Objects/dictobject.c
• Wikipedia — Hash table (familles de stratégies, analyses asymptotiques)
• Wikipedia — Open addressing (sondage linéaire, quadratique, double hachage)
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (chapitre 11)