Chercher une clé dans un dict Python contenant dix entrées prend le même temps que dans un dict qui en contient dix millions. Ce n’est pas un hasard lié à un langage rapide. Le dict de Python, le HashMap de Java et la Map de JavaScript sont tous des tables de hachage, et toute leur conception vise à faire tourner recherche, insertion et suppression en O(1) en moyenne. La notation Big O donne à cette recherche l’étiquette “temps constant”. Voici le mécanisme qui la justifie.

Comment une table de hachage transforme une clé en index de tableau

Une table de hachage est un tableau associé à une fonction qui transforme une clé en position dans ce tableau.

1

index du bucket = hash(clé) % nombre_de_buckets

hash() prend une clé de taille quelconque (une chaîne, un tuple, un objet) et renvoie un entier. Au sein d’une même exécution du programme, la même clé produit toujours le même entier, et une bonne fonction de hachage répartit ces entiers de façon quasi uniforme sur toute sa plage de sortie. Prenez cet entier modulo la longueur du tableau et vous obtenez un emplacement. Vous y stockez la clé et la valeur. Une recherche ultérieure recalcule le même hash, tombe sur le même emplacement et lit la valeur. Aucun parcours, aucune comparaison avec les autres clés.

Tout le reste dans une vraie table de hachage — la gestion des collisions, le redimensionnement, la séquence exacte de sondage — ne sert qu’à maintenir cette recherche en une seule étape quand la table se remplit.

Une version minimale qui ignore les collisions :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

Ça casse dès que deux clés différentes aboutissent au même index. hash("user:42") % 8 et hash("user:17") % 8 peuvent tomber tous les deux sur 3, et TinyTable n’a de la place que pour une seule des deux : le second put écrase silencieusement le premier. C’est une collision.

Comment les tables de hachage gèrent les collisions : chaînage vs. adressage ouvert

Il existe deux façons standard de conserver les deux clés quand elles tombent sur le même emplacement.

Le chaînage transforme chaque bucket en petit conteneur, le plus souvent une liste chaînée. Une collision signifie que le bucket contient deux entrées au lieu d’une, et la recherche parcourt cette liste jusqu’à trouver la clé qui correspond.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

Le HashMap de Java est une table à chaînage. Chaque bucket démarre comme une liste chaînée. Si un bucket accumule au moins 8 entrées et que la table compte au moins 64 buckets, ce bucket se convertit en arbre rouge-noir (TREEIFY_THRESHOLD et MIN_TREEIFY_CAPACITY dans le code du JDK), si bien qu’un parcours O(n) dans le pire cas d’un bucket surchargé devient O(log n). Il redevient une liste si un redimensionnement le laisse avec 6 entrées ou moins.

L’adressage ouvert garde chaque entrée directement dans le tableau, sans structure secondaire ni pointeurs. En cas de collision, il sonde : il essaie un autre emplacement, selon une règle fixe, jusqu’à en trouver un vide. Le dict de CPython fonctionne ainsi, et le commentaire sur la recherche dans Objects/dictobject.c en donne la raison : “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” CPython évite aussi le sondage linéaire pur, qui forme des amas quand les clés arrivent dans un ordre prévisible. Chaque étape de sondage mélange davantage de bits du hash dans l’index suivant, si bien que deux clés qui entrent en collision sur leurs bits faibles se séparent quelques sondages plus tard.

Les deux approches échouent différemment. Une table à chaînage qui se remplit devient plus lente, et dans le pire cas, toutes les entrées finissent dans une seule liste longue. Une table à adressage ouvert n’a plus où mettre une entrée une fois le tableau plein, elle doit donc se redimensionner avant d’en arriver là.

Qu’est-ce que le facteur de charge et pourquoi la table se redimensionne avant d’être pleine

Le facteur de charge est le nombre d’entrées divisé par le nombre de buckets. Les deux approches le surveillent pour décider quand redimensionner, et Java et CPython choisissent des seuils différents.

Le HashMap de Java se redimensionne quand le nombre d’entrées dépasse la capacité multipliée par le facteur de charge. Le Javadoc du constructeur sans argument donne les valeurs par défaut : 16 buckets, facteur de charge 0,75, donc le premier redimensionnement se déclenche à la 12e entrée. Un redimensionnement double approximativement le nombre de buckets et refait le hash de toutes les entrées existantes dans le nouveau tableau. C’est pourquoi le Javadoc recommande de dimensionner la map à l’avance avec HashMap.newHashMap(expectedSize) (Java 19+) quand vous connaissez approximativement le nombre d’entrées qu’elle contiendra : vous évitez les rehachages répétés.

Le dict de CPython se redimensionne plus tard et grandit plus vite. Le commentaire USABLE_FRACTION dans le code indique que la table se redimensionne une fois pleine aux deux tiers, et GROWTH_RATE dimensionne la nouvelle table pour environ trois fois le nombre actuel d’entrées vivantes, pas un simple doublement.

Aucun des deux chiffres n’est arbitraire. Un facteur de charge proche de 1 remplit le tableau au maximum mais ralentit chaque opération à mesure que les buckets se remplissent ; un facteur proche de 0 gaspille de la mémoire sur des emplacements que personne n’utilise encore. Les deux conceptions se stabilisent entre 0,66 et 0,75, le point où la mémoire supplémentaire ne raccourcit plus guère les sondages.

Pourquoi la recherche dans une table de hachage est en O(1) en moyenne, pas toujours

Le temps constant ne tient que tant que les hash répartissent les clés de façon quasi uniforme entre les buckets. Deux choses cassent ça.

Une fonction de hachage mauvaise ou prévisible. Si toutes les clés que vous insérez tombent dans le même bucket, une table à chaînage dégénère en une seule liste chaînée avec une recherche en O(n), exactement ce que la structure est censée éviter. Cela arrive en production. Un serveur qui hache une entrée contrôlée par un attaquant (noms de champs de formulaire, en-têtes HTTP, clés JSON) avec une fonction prévisible est exposé à des attaques par complexité algorithmique : l’attaquant envoie des milliers de clés construites pour entrer en collision et force le pire comportement à chaque requête. Python randomise le hash de str et bytes par processus depuis la version 3.3 (contrôlé par PYTHONHASHSEED) précisément pour cette raison. La même chaîne produit des hash différents à deux exécutions de l’interpréteur, donc personne ne peut précalculer un ensemble de collisions hors ligne.

Modifier une clé après son insertion. Le bucket où vit une clé a été choisi d’après son hash, donc la table suppose que ce hash ne change jamais. Python l’impose au niveau du type : les types mutables comme list et dict fixent __hash__ à None, et en utiliser un comme clé déclenche TypeError: unhashable type: 'list' avant que l’erreur ne puisse se produire. Les tuples et les chaînes sont hachables parce qu’ils sont immuables. Pour une classe de clé personnalisée, implémentez __hash__ et __eq__ ensemble et basez-les uniquement sur des champs qui ne changent jamais. Sinon, une clé modifiée “disparaît” : l’entrée reste dans la table, dans le bucket que pointait son ancien hash, mais la recherche regarde ailleurs.

Quand ne pas utiliser une table de hachage

Une table de hachage répond vite à une seule question : cette clé existe-t-elle, et quelle est sa valeur ? Presque tout le reste, elle le fait mal.

  • Requêtes de plage et de tri. “Tous les utilisateurs créés ce mois-ci” ou “la clé suivante après celle-ci” nécessitent une structure triée. Une table de hachage n’a pas d’ordre. Le dict de CPython garantit l’ordre d’insertion depuis la 3.7, mais c’est un ordre d’itération, pas un ordre de tri, et ça n’aide pas pour “tout ce qui est entre X et Y”. Cette requête, c’est le travail d’un B-tree, ce qui explique pourquoi la plupart des bases de données utilisent par défaut des index B-tree plutôt que des index de hachage. Comment fonctionnent les index de base de données traite le compromis scan contre seek derrière ce choix par défaut.
  • Correspondance par préfixe ou approximative. “Les clés commençant par user:” veut dire vérifier chaque clé une par une. Un trie, ou une structure triée avec recherche binaire, le gère directement.
  • Petites clés entières dans une plage restreinte. Si la clé est déjà un jour de la semaine ou une classe de code de statut HTTP, sautez la fonction de hachage et indexez directement un tableau. Une couche de moins, aucune collision.

Quand une table de hachage est la bonne structure, vous n’en écrivez presque jamais une vous-même. dict, HashMap, Map et std::unordered_map sont déjà optimisées et correctes. Vous les utilisez aussi indirectement plus que vous ne le pensez : une fonction décorée avec functools.lru_cache, traitée dans Décorateurs Python expliqués, construit une clé à partir des arguments de l’appel et la recherche dans un dict.

La décision est donc courte. Si l’opération est “cherche ceci par clé exacte”, utilisez la table de hachage intégrée et n’en écrivez pas une vous-même. Si la question porte sur l’ordre, les plages ou les correspondances partielles, choisissez dès le départ une structure triée ou un trie, car aucune fonction de hachage ne répare une structure qui répond à la mauvaise question.

Articles associés