Tables de hachage : collisions, charge et redimensionnement

Retrouver une fiche par identifiant utilisateur revient à demander « quelle valeur correspond à cette clé ? », plutôt que « quel élément occupe cette position ? ». Une table de hachage transforme la clé en entier, puis s’en sert pour choisir une position de départ dans un tableau. Elle réduit ainsi le nombre de comparaisons à effectuer. Le chapitre d’Open Data Structures consacré aux tables de hachage présente deux implémentations courantes : le chaînage séparé et le sondage linéaire.

La carte des structures de données aide à choisir une représentation selon les opérations nécessaires. Ici, il s’agit de comprendre comment la recherche reste correcte lorsque plusieurs clés arrivent au même endroit, pourquoi la suppression demande un traitement particulier et sous quelles conditions le coût est constant en espérance. Pour les notions de tableau et de capacité, voir Tableaux et tableaux dynamiques.

Dictionnaires, ensembles et tables de hachage

Un dictionnaire associe des clés uniques à des valeurs et permet de rechercher par clé, d’insérer ou de mettre à jour une association et de la supprimer. Un ensemble ne conserve que les membres ; il permet l’ajout, la suppression et le test d’appartenance. Ce sont des interfaces. La table de hachage est une implémentation ; un arbre de recherche équilibré peut aussi réaliser ces interfaces, à condition de pouvoir comparer les clés selon un ordre total cohérent, avec d’autres coûts et d’autres possibilités de parcours ordonné.

La FAQ sur l’implémentation de CPython décrit ses dictionnaires comme des tables de hachage redimensionnables. Le traitement des clés absentes, l’itération et la fusion en Python sont expliqués dans Dictionnaires et état indexé par clé. Le petit dictionnaire ci-dessous rend le stockage visible ; le même traitement des collisions convient à un ensemble, en omettant les valeurs.

Le hachage choisit le départ, l’égalité reconnaît la clé

Notons $h(k)$ la valeur de hachage entière d’une clé et $m$ la capacité. On peut, par exemple, calculer la position de départ par $h(k)\bmod m$. Deux clés distinctes peuvent avoir la même valeur de hachage complète, ou des valeurs différentes qui donnent la même position après réduction. Dans les deux cas, il faut traiter la collision.

Les conditions sur les codes de hachage dans Open Data Structures imposent que des clés égales aient le même hachage et cherchent à limiter la probabilité que des clés différentes partagent une valeur. Une collision exige encore de comparer les clés. Utiliser le hachage comme identifiant unique fusionnerait des clés distinctes.

La définition d’un objet hachable en Python exige un hachage constant pendant toute sa durée de vie et identique pour des objets égaux. Les champs intervenant dans le hachage et l’égalité doivent rester stables : une entrée pourrait sinon rester à son ancienne position alors qu’une nouvelle recherche commencerait ailleurs. Modifier l’égalité peut aussi rompre l’unicité des clés sans changer leur hachage. Les chaînes et les tuples d’éléments hachables sont des choix courants. Les listes ne sont pas hachables, pas plus que les tuples contenant une liste. Pour les objets personnalisés, mutabilité et hachabilité sont deux propriétés distinctes : une instance utilisant l’égalité par identité fournie par défaut peut être hachable.

Le modèle de données de Python précise aussi que le hachage des chaînes et des objets bytes utilise par défaut un sel aléatoire. Il reste constant dans un processus, mais sa valeur n’est pas garantie d’un processus à l’autre. Cela aide à résister aux entrées choisies pour provoquer des collisions, sans éliminer tous les cas défavorables ni rendre efficace un hachage personnalisé constant. Les identifiants persistants doivent être conservés séparément, sans dépendre du hachage intégré.

Deux organisations du stockage

Le chaînage séparé conserve une collection d’entrées dans chaque compartiment du tableau. La recherche choisit le compartiment, puis y compare les clés ; la suppression en retire l’entrée trouvée. Une liste chaînée est une représentation possible du compartiment, mais d’autres structures de liste conviennent aussi.

L’adressage ouvert avec sondage linéaire place les entrées dans un seul tableau, à raison d’au plus une entrée par case. Si la case de départ est occupée, il examine les suivantes et revient à zéro après la dernière. La recherche doit suivre le même parcours de sondage.

Question	Chaînage séparé	Adressage ouvert avec sondage linéaire
Où placer une entrée après collision ?	Dans la liste du même compartiment	Dans une case disponible plus loin
Comment chercher ?	Comparer les clés du compartiment	Comparer les clés le long du parcours de sondage
Comment supprimer ?	Retirer l’entrée de la liste	Ici, laisser une marque de suppression pour préserver le parcours
Espace et accès	Le stockage des compartiments ajoute un surcoût ; les nœuds chaînés demandent des accès indirects	Il faut des cases libres ; les sondages consécutifs ont une bonne localité, mais peuvent former de longs amas

Avec le sondage linéaire, les cases occupées adjacentes forment un amas. Les nouvelles clés dont le départ tombe dans cet amas le prolongent : c’est l’agglomération primaire. La distribution du hachage et la règle de sondage influencent les performances ; le nombre d’entrées ne suffit donc pas à les prévoir.

Une trace de collision avec suppression

Prenons une capacité $m=8$ et le hachage pédagogique $h(k)=k$ pour des clés entières. Insérons dans cet ordre 5, 13 et 21, avec les valeurs A, B et C. Les trois clés commencent à la case 5. Cette règle provoque volontairement des collisions pour faciliter le calcul ; elle ne fournit pas l’hypothèse de distribution uniforme nécessaire aux performances et ne reproduit pas le sondage de CPython.

EMPTY désigne une case qui n’a jamais contenu d’entrée depuis la construction du tableau actuel. DEL désigne une case qui en a contenu une, ensuite supprimée.

Opération	Cases examinées	Résultat
Insérer 5	5	Placer à la case 5
Insérer 13	5, 6	Placer à la case 6
Insérer 21	5, 6, 7	Placer à la case 7
Supprimer 13	5, 6	Marquer la case 6 avec DEL
Chercher 21	5, 6, 7	Passer DEL ; trouver C à la case 7
Chercher 29	5, 6, 7, 0	La case 0 est EMPTY, ce qui prouve l’absence
Mettre 21 à jour avec C2	5, 6, 7	Mettre à jour la case 7 ; conserver la marque à la case 6
Insérer 29	5, 6, 7, 0	Après avoir établi l’absence, réutiliser la case 6

Si la suppression de 13 remplaçait la case 6 par EMPTY, la recherche de 21 s’y arrêterait et conclurait à tort que la clé est absente. La marque de suppression demande de poursuivre la recherche. L’insertion peut mémoriser la première case supprimée, mais doit encore chercher une clé égale déjà présente, pour ne pas transformer une mise à jour en doublon.

Ce programme Python 3 exécute toute la trace, puis réinsère les entrées restantes dans une table de capacité 16. Les clés sont des entiers et les valeurs des chaînes ; get renvoie None en cas d’absence. put renvoie la case choisie, l’existence préalable de la clé et les cases examinées. Si la clé est absente et qu’aucune case vide ou supprimée n’est disponible, il lève OverflowError ; une clé déjà présente peut encore être mise à jour dans une table pleine. La reconstruction est explicite à la fin ; « Pourquoi amortir le redimensionnement » décrit une politique de croissance automatique. Chaque sondage parcourt au plus une fois le tableau entier.

EMPTY = None
DELETED = object()


def locate(table, key):
    first_deleted = None
    visited = []
    for step in range(len(table)):
        index = (key + step) % len(table)
        visited.append(index)
        entry = table[index]
        if entry is EMPTY:
            target = index if first_deleted is None else first_deleted
            return target, False, visited
        if entry is DELETED:
            if first_deleted is None:
                first_deleted = index
        elif entry[0] == key:
            return index, True, visited
    return first_deleted, False, visited


def put(table, key, value):
    index, found, visited = locate(table, key)
    if index is None:
        raise OverflowError("table full")
    table[index] = (key, value)
    return index, found, visited


def get(table, key):
    index, found, visited = locate(table, key)
    return (table[index][1] if found else None), visited


def delete(table, key):
    index, found, visited = locate(table, key)
    if found:
        table[index] = DELETED
    return found, visited


def snapshot(table):
    return ["EMPTY" if x is EMPTY else "DEL" if x is DELETED
            else x[0] for x in table]


table = [EMPTY] * 8
for key, value in [(5, "A"), (13, "B"), (21, "C")]:
    print("put", key, put(table, key, value))
print("slots", snapshot(table))
print("delete", 13, delete(table, 13))
print("slots", snapshot(table))
print("get", 21, get(table, 21))
print("get", 29, get(table, 29))
print("update", 21, put(table, 21, "C2"))
print("put", 29, put(table, 29, "D"))
print("slots", snapshot(table))
larger = [EMPTY] * 16
for entry in table:
    if entry is not EMPTY and entry is not DELETED:
        put(larger, *entry)
print("resized", snapshot(larger))
print("get", 21, get(larger, 21))

Sortie :

put 5 (5, False, [5])
put 13 (6, False, [5, 6])
put 21 (7, False, [5, 6, 7])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 13, 21]
delete 13 (True, [5, 6])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 'DEL', 21]
get 21 ('C', [5, 6, 7])
get 29 (None, [5, 6, 7, 0])
update 21 (7, True, [5, 6, 7])
put 29 (6, False, [5, 6, 7, 0])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 29, 21]
resized ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 21, 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 29, 'EMPTY', 'EMPTY']
get 21 ('C2', [5, 6])

À la capacité 16, les clés 5, 21 et 29 commencent respectivement à 5, 5 et 13. La réinsertion dans l’ordre des anciennes cases les place à 5, 6 et 13 ; chercher 21 n’examine plus que 5 et 6. Le redimensionnement doit recalculer les positions. Copier l’ancien tableau et lui ajouter des cases libres ne rétablirait pas les règles de recherche.

Facteur de charge et marques de suppression

Notons $n$ le nombre d’entrées actives et $m$ le nombre de compartiments ou de cases. Le facteur de charge est $\alpha=n/m$. Avec le chaînage séparé, il donne aussi la longueur moyenne d’un compartiment et peut dépasser 1. Sous un modèle de hachage aléatoire adapté, le coût de recherche en espérance est $O(1+\alpha)$ ; borner la charge permet d’obtenir $O(1)$ en espérance. Une moyenne faible n’exclut pas un compartiment particulièrement long.

L’adressage ouvert doit aussi compter les marques de suppression. Notons $d$ leur nombre et $q=n+d$ le nombre de cases non vides. Avant la suppression de l’exemple, $n=3$ et $\alpha=3/8=0.375$. Après, $n=2$ et $d=1$ : la charge active descend à $2/8=0.25$, tandis que la proportion non vide reste $q/m=3/8=0.375$. Comme la recherche ne peut s’arrêter sur DEL, compter seulement les entrées actives sous-estime le travail de sondage.

L’implémentation par sondage linéaire d’Open Data Structures maintient $m\ge 2q$, donc au moins la moitié des cases sont EMPTY. Son analyse suppose d’abord des positions de hachage indépendantes et uniformément distribuées, puis examine le hachage par tabulation adapté au sondage linéaire. Dans ces conditions, recherche, insertion et suppression coûtent $O(1)$ en espérance, hors reconstruction. Le seuil de remplissage à moitié appartient à cette implémentation ; il ne s’applique pas universellement aux tables de hachage ou aux dictionnaires Python.

Reconstruire consiste à réinsérer uniquement les entrées actives et à éliminer les marques. On augmente la capacité si l’espace manque ; une reconstruction à capacité identique peut nettoyer un excès de marques. Dans cette trace, l’insertion de 29 a déjà réutilisé la seule marque. Le passage à 16 donne une charge de $3/16=0.1875$, mais 5 et 21 entrent toujours en collision.

Pourquoi amortir le redimensionnement

Considérons une autre table, de capacité initiale 4, qui ne reçoit que de nouvelles clés et double avant qu’une insertion ne la remplisse au-delà de la moitié. Pour 20 insertions, elle grandit avant les insertions 3, 5, 9 et 17, en réinsérant respectivement 2, 4, 8 et 16 entrées existantes. Cela représente $2+4+8+16=30$ réinsertions, plus 20 écritures de nouvelles entrées, soit 50 placements. Ce compte ne mesure ni la durée ni le nombre de sondages : collisions, parcours de l’ancien tableau, initialisation du nouveau et calcul des hachages restent à prendre en compte.

Les nombres de réinsertions forment une série géométrique. Pour $N$ insertions à partir d’une table vide, cette politique effectue moins de $2N$ réinsertions ; le volume total d’initialisation et de parcours des tableaux croît lui aussi linéairement avec $N$. Si le coût en espérance de chaque placement est borné, le travail total est $O(N)$ en espérance, et l’insertion coûte $O(1)$ amorti en espérance. Le raisonnement rejoint la croissance géométrique des tableaux dynamiques, mais la table de hachage doit aussi rétablir la position de recherche de chaque clé.

L’espérance mesure le coût moyen sur les choix aléatoires du hachage ; l’amortissement répartit les reconstructions occasionnelles sur une suite d’opérations. La complexité temporelle explique cette distinction. Avec une capacité proportionnelle au nombre d’entrées, un coût fixe de hachage et de comparaison et un sondage de coût borné en espérance, une reconstruction coûte $O(n)$ en espérance. L’insertion qui la déclenche peut néanmoins prendre sensiblement plus de temps. Si toutes les clés s’agglomèrent, leur réinsertion une à une par sondage linéaire peut même demander un nombre quadratique de sondages.

Si la table peut rétrécir, il faut séparer les seuils de croissance et de réduction pour éviter que l’ajout et le retrait alternés d’une clé provoquent sans cesse une reconstruction. Open Data Structures reconstruit lorsque plus de la moitié des cases sont non vides ou que les entrées actives représentent moins d’un huitième de la capacité ; il choisit ensuite la plus petite capacité puissance de deux qui soit au moins égale à $3n$.

Ce que le temps constant doit encore payer

Pour les implémentations ordinaires par chaînage ou sondage, un hachage adapté, une charge maîtrisée et un traitement des clés à coût fixe donnent une recherche et une suppression hors reconstruction en $O(1)$ en espérance. L’insertion et la suppression susceptibles de reconstruire demandent des bornes amorties en espérance, avec une politique de reconstruction adaptée. De fortes collisions peuvent faire examiner $O(n)$ entrées lors d’une seule recherche. Pour un parcours intégral en adressage ouvert, la borne plus précise est $O(m)$ ; elle devient $O(n)$ seulement si $m=O(n)$.

La clé elle-même a un coût. Si hacher la clé $k$ demande $H(k)$, que la recherche examine $p$ cases et compare des clés candidates, on peut écrire :

$$T(k)=H(k)+O(p)+\sum_{j\in C}E(k,k_j).$$

L’ensemble $C$ contient les entrées effectivement comparées, et $E(k,k_j)$ est le coût d’un test d’égalité. Les marques de suppression comptent dans $p$, pas dans $C$. Hacher en parcourant intégralement une clé de longueur $L$ demande un travail en $O(L)$ ; comparer de longues clés peut aussi nécessiter de les lire jusqu’au bout. Réduire le nombre de candidats ne supprime pas automatiquement ce travail. Réutiliser un hachage en cache économise des calculs si la clé reste stable et si l’implémentation conserve et exploite réellement ce cache.

Lorsque l’ordre ou les intervalles comptent

Le contrat des dictionnaires Python garantit l’ordre d’insertion à partir de Python 3.7. L’ordre d’insertion et l’ordre trié des clés répondent à deux besoins distincts ; les positions dans les compartiments de hachage n’expriment pas de relation d’ordre.

Besoin principal	Structure possible	Coûts à prendre en compte
Recherche répétée par clé complète, dédoublonnage ou comptage	Dictionnaire ou ensemble fondé sur le hachage	Hachage, collisions, capacité libre et reconstruction
Positions triées ou bornes d’un intervalle dans des données statiques	Tableau trié avec recherche binaire	Trier d’abord ; chercher les bornes demande $O(\log n)$ comparaisons, puis énumérer $r$ résultats ajoute $O(r)$ ; Python bisect fournit ces recherches de bornes
Mises à jour fréquentes avec requêtes de prédécesseur, de successeur ou d’intervalle	Arbre de recherche équilibré	Maintenir l’équilibre ; une requête d’intervalle avec énumération coûte typiquement $O(\log n+r)$ si les comparaisons ont un coût fixe

« La clé 21 existe-t-elle ? » convient à une table de hachage. « Quelles clés se trouvent entre 10 et 30 ? » demande généralement de parcourir les entrées d’une table ordinaire ou de maintenir un autre index ordonné. La carte des algorithmes de recherche rapproche ces besoins pour choisir la méthode de requête selon les informations que la structure conserve.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.