Structures de données élémentaires et tables de hachage

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• distinguer un type abstrait de données — un contrat d'opérations — de ses implémentations, et choisir l'implémentation à partir du profil d'opérations d'une application plutôt qu'à partir d'une habitude;
• démontrer le coût amorti $\Theta (1)$ de l'ajout en fin d'un tableau dynamique par les trois méthodes classiques — agrégat, comptable, potentiel — et dire pourquoi «amorti» n'est ni «moyen» ni «dans le pire des cas pour une opération»;
• comparer honnêtement tableau, liste simplement chaînée et liste doublement chaînée, y compris sur ce que le modèle RAM ne voit pas: la localité en mémoire;
• implémenter une pile, une file, et la file par deux piles, et justifier son coût par un argument amorti;
• énoncer ce qu'on demande à une fonction de hachage, appliquer la méthode de la division et celle de la multiplication, et dérouler à la main le chaînage et le sondage linéaire sur la table témoin du cours;
• démontrer que la longueur moyenne d'une chaîne vaut le facteur de charge $\alpha$ sous l'hypothèse de hachage uniforme simple, expliquer l'amas primaire et dire ce que le double hachage y change.

Le type abstrait et son implémentation

Un contrat, puis une réalisation

Jusqu'ici ce cours a analysé des algorithmes: des méthodes qui transforment une entrée en une sortie. Ce chapitre change d'objet. Une structure de données ne calcule pas une réponse une fois pour toutes: elle conserve un état entre les appels, et elle répond à une suite d'opérations qui la consultent et la modifient. Son analyse change en conséquence, et c'est précisément pour cela que la notion de coût amorti, annoncée au chapitre 1, devient ici centrale plutôt qu'anecdotique.

La première chose à séparer est le quoi du comment. Un programme qui a besoin d'une file d'attente a besoin d'un objet qui accepte des éléments d'un côté et les rend de l'autre dans le même ordre; il n'a pas besoin de savoir si cet objet est un tableau circulaire, deux piles ou une liste chaînée. Cette séparation porte un nom.

L'exemple le plus parlant est celui de la séquence. Le type abstrait «séquence d'éléments» propose, au minimum: lire l'élément d'indice $i$, écrire à l'indice $i$, insérer à l'indice $i$, supprimer l'indice $i$, et connaître la longueur. Voilà le contrat. Il ne dit rien du coût. Or selon qu'on l'implémente par un tableau contigu ou par une liste chaînée, les cinq opérations n'ont pas du tout les mêmes coûts, et l'une est $\Theta (1)$ dans un cas et $\Theta (n)$ dans l'autre — dans les deux sens.

Les deux dernières lignes appartiennent aux chapitres 5 et suivants; les quatre premières sont l'objet de celui-ci.

Pourquoi la séparation vaut d'être faite

On pourrait voir là une précaution de génie logiciel sans conséquence algorithmique. C'est le contraire. La séparation a trois effets concrets.

D'abord, elle rend le choix visible. Tant que vous écrivez «une liste», vous ne choisissez rien: vous prenez ce que votre langage appelle ainsi. Dès que vous écrivez «j'ai besoin d'une séquence dont je ne modifierai que la fin, et que je parcourrai souvent du début à la fin», vous avez formulé un profil d'opérations, et ce profil désigne une implémentation.

Ensuite, elle permet de changer d'avis. Un programme écrit contre le contrat d'une file, et non contre la représentation d'une file, se convertit d'une implémentation à l'autre sans que rien d'autre ne bouge. C'est exactement la situation dans laquelle on veut être quand une mesure montre qu'on s'est trompé.

Enfin, elle oblige à énoncer le coût de chaque opération séparément. Une structure de données n'a pas «une complexité»: elle a un coût par opération, et l'on compare deux implémentations en confrontant leurs deux tableaux de coûts au profil d'opérations réel de l'application. Une structure dont la recherche est $\Theta (\log n)$ et l'insertion $\Theta (n)$ bat une structure toute en $\Theta (\sqrt{n})$ si l'application fait mille recherches par insertion, et perd dans le cas contraire.

Le tableau dynamique et le coût amorti

Une capacité, une taille

Un tableau occupe en mémoire un bloc contigu de cases. Ce bloc a une capacité $c$, fixée au moment de l'allocation, et le tableau contient à un instant donné une taille $s\le c$ d'éléments utiles. La lecture et l'écriture de l'indice $i$ coûtent $\Theta (1)$: l'adresse de la case $i$ se calcule par une addition, et le modèle RAM facture un accès à une adresse quelconque au prix d'une unité.

L'ajout en fin est trivial tant que $s<c$: on écrit dans la case $s$ et on incrémente $s$. Quand $s=c$, il n'y a plus de place, et il n'est pas question d'«agrandir sur place» un bloc contigu dont le voisin est occupé par autre chose. Il faut allouer un bloc plus grand et y recopier tout le contenu.

def ajouts(n, facteur=2):
    """Simule n ajouts en fin et compte les ecritures elementaires."""
    capacite, taille = 0, 0
    recopies, ecritures = 0, 0
    for _ in range(n):
        if taille == capacite:                  # debordement
            recopies += taille                  # tout le contenu est recopie
            ecritures += taille
            capacite = max(1, facteur *

L'opération barométrique est ici l'écriture élémentaire: une case remplie, que ce soit par un ajout ou par une recopie. Un ajout isolé coûte donc $1$ écriture dans le cas ordinaire et $s+1$ écritures quand il déclenche un agrandissement. Dans le pire des cas, un ajout coûte $\Theta (n)$, et cet énoncé est exact — il est aussi parfaitement inutile, parce qu'il ne dit rien du prix d'une suite d'ajouts, qui est la seule chose qu'on veuille savoir.

for n in [16, 17, 1000, 1000000]:
    recopies, ecritures, capacite = ajouts(n)
    print(f"n = {n:>7} : {recopies:>7} recopies, {ecritures:>8} ecritures, "
          f"capacite {capacite:>7}, {ecritures / n:.3f

n =      16 :      15 recopies,       31 ecritures, capacite      16, 1.938 ecriture par ajout
n =      17 :      31 recopies,       48 ecritures, capacite      32, 2.824 ecriture par ajout
n =    1000 :    1023 recopies,     2023 ecritures, capacite    1024, 2.023 ecriture par ajout
n = 1000000 : 1048575 recopies,  2048575 ecritures, capacite 1048576, 2.049 ecriture par ajout

Le chapitre 1 s'était arrêté là, en constatant que le nombre moyen d'écritures par ajout reste inférieur à 3 quelle que soit la valeur de $n$, et en promettant la démonstration pour ce chapitre. La voici, par trois chemins différents — et si l'on prend la peine d'en donner trois, ce n'est pas par goût de la redondance: la troisième méthode, celle du potentiel, est la seule qui se transporte telle quelle aux structures plus compliquées, et elle ne s'apprend qu'en la voyant coïncider avec les deux autres sur un cas où l'on sait déjà la réponse.

Première méthode: l'agrégat

La méthode de l'agrégat consiste à calculer le coût total d'une suite de $n$ opérations, puis à le diviser par $n$. Elle ne distingue pas les opérations entre elles: elle donne un coût amorti unique, le même pour toutes.

Partons d'un tableau vide de capacité nulle. Les agrandissements ont lieu lorsque la taille vaut $0,1,2,4,8,\dots$, et l'agrandissement qui a lieu à la taille $2^j$ recopie $2^j$ éléments. Si l'on effectue $n$ ajouts, le dernier agrandissement est celui de taille $2^k$ avec , donc le nombre total de recopies vaut

La somme géométrique est l'ingrédient actif, et elle mérite qu'on s'y arrête une seconde: le total d'une suite géométrique est du même ordre que son dernier terme. C'est ce qui fait que les $k$ agrandissements antérieurs, tous ensemble, coûtent moins cher que le dernier. En ajoutant les $n$ écritures des ajouts eux-mêmes, le coût total d'une suite de $n$ ajouts est

Le coût amorti d'un ajout est donc au plus $3$ écritures, c'est-à-dire $\Theta (1)$. La borne est serrée: en $n=2^k+1$, c'est-à-dire juste après un agrandissement, le total vaut exactement $3\cdot 2^k=3(n-1)$, et le rapport tend vers 3 par valeurs inférieures. Pour , le programme donne , soit écriture par ajout.

Deuxième méthode: le comptable

La méthode du comptable — on dit aussi «méthode des acomptes» — attribue à chaque opération un prix affiché, qui peut différer de son coût réel. Quand le prix affiché dépasse le coût réel, la différence est mise en réserve, sous forme de crédits posés sur des éléments précis de la structure. Quand le coût réel dépasse le prix affiché, la différence est prélevée sur les crédits accumulés. Si l'on peut démontrer que le solde ne devient jamais négatif, alors la somme des prix affichés majore le coût réel total, et le prix affiché est un coût amorti valable.

Affichons 3 écritures pour chaque ajout, et répartissons-les ainsi:

• 1 paie l'écriture de l'élément qu'on ajoute, c'est-à-dire son coût réel ordinaire;
• 1 est déposé sur l'élément qu'on vient d'ajouter, pour payer sa propre recopie lors du prochain agrandissement;
• 1 est déposé sur un élément de la première moitié du tableau, qui, lui, a déjà été recopié une fois et n'a plus de crédit.

Il reste à vérifier que la caisse est toujours suffisante. Considérons l'agrandissement qui fait passer la capacité de $2c$ à $4c$: il a lieu au moment où la taille atteint $2c$ et doit recopier $2c$ éléments. Depuis l'agrandissement précédent — celui qui avait porté la capacité de $c$ à $2c$ et laissé le tableau avec $c+1$ éléments —, on a effectué les ajouts qui ont fait passer la taille de $c+1$ à $2c$, soit ajouts, plus celui qui a déclenché l'agrandissement précédent, soit ajouts au total. Chacun a déposé crédits. La caisse contient donc exactement crédits, et la recopie coûte exactement écritures. Le solde retombe à zéro, sans jamais être passé en dessous.

Le raisonnement est d'une élégance particulière parce qu'il localise le paiement: chaque élément recopié a un payeur identifié. C'est aussi ce qui en fait la limite — il faut inventer la répartition, et rien ne la souffle.

Troisième méthode: le potentiel

La méthode du potentiel remplace les crédits, attachés à des éléments, par une seule fonction numérique de l'état global de la structure. C'est la méthode la plus mécanique des trois et la seule qui s'étende sans effort aux structures compliquées — le chapitre 8 dira que c'est elle qui démontre le coût amorti d'union-find, sans la dérouler, la démonstration de Tarjan étant hors de portée d'un premier cours.

Autrement dit: si l'on trouve un $\Phi$ pour lequel chaque ${\hat{c}}_i$ est borné par une constante, alors le coût réel total de n'importe quelle suite de $m$ opérations est au plus cette constante fois $m$. Le potentiel joue le rôle d'une réserve: il monte quand une opération bon marché prépare un futur coûteux, et il redescend d'un coup pour payer ce futur quand il arrive.

Démonstration. Notons $s$ la taille et $c$ la capacité, et posons

Le potentiel est admissible. Dans l'état initial, $s=c=0$, donc $\Phi (D_0)=0$. Montrons que $\Phi \ge 0$ après chaque ajout, c'est-à-dire que l'invariant $2s\ge c$ est maintenu. Après le premier ajout, $s=c=1$ et . Supposons l'invariant vrai après un certain ajout. Si l'ajout suivant ne déclenche pas d'agrandissement, croît de 1 et ne bouge pas: croît de 2, donc reste positif. S'il en déclenche un, c'est que ; après coup la taille vaut et la capacité , donc . L'invariant est donc vrai après chaque ajout, et .

Le coût amorti de chaque ajout est au plus 3. Trois cas, et trois seulement.

Cas 1 — le tout premier ajout. Ici $s=c=0$. La condition de débordement est vérifiée mais il n'y a rien à recopier: le coût réel est $c_i=0+1=1$. Après, $s=c=1$ et passe de à . Donc .

Cas 2 — un ajout sans agrandissement, c'est-à-dire $s<c$ avant l'opération. Le coût réel est $c_i=1$. La taille passe de $s$ à $s+1$ et la capacité ne change pas, donc la variation de potentiel vaut $(2(s+1)-c)-(2s-c)=2$. Donc

Cas 3 — un ajout avec agrandissement, c'est-à-dire $s=c\ge 1$ avant l'opération. Le coût réel comprend la recopie des $c$ éléments et l'écriture du nouveau: $c_i=c+1$. Avant l'opération, $\Phi =2c-c=c$. Après, la taille vaut et la capacité , donc . La variation vaut , d'où

Remarquez ce qui s'est passé: le potentiel accumulé pendant les $c/2$ ajouts ordinaires a servi, d'un seul coup, à payer les $c$ recopies. C'est très exactement le rôle qu'on attendait de lui.

Conclusion. Chaque ${\hat{c}}_i$ vaut au plus 3, donc, par la propriété de télescopage,

Les trois méthodes donnent la même constante, 3, ce qui n'est pas une coïncidence: elles décrivent la même comptabilité dans trois langages. L'agrégat la voit globalement, le comptable la voit élément par élément, le potentiel la voit comme une fonction d'état. Sur un tableau dynamique les trois sont également commodes; dès que les opérations se diversifient — insertions et suppressions, comme ci-dessous —, seule la troisième reste maniable.

Supprimer sans osciller

Si l'on ajoute la suppression du dernier élément, une question se pose: quand rendre la mémoire? La réponse naïve — «réduire de moitié la capacité dès que la taille descend à la moitié» — est fausse, et d'une façon instructive.

Supposons la table pleine, $s=c=2^k$. L'ajout suivant double la capacité et recopie $2^k$ éléments. La suppression suivante ramène la taille à $2^k$, soit la moitié de la nouvelle capacité $2^{k+1}$: la règle naïve réduit donc la capacité de moitié et recopie encore éléments. L'ajout d'après double à nouveau, et ainsi de suite. Une suite alternée ajout, suppression, ajout, suppression coûte , soit au total — précisément ce que l'amortissement devait éviter.

La correction tient en un mot: laisser un jeu. On réduit la capacité de moitié seulement lorsque la taille descend au quart de la capacité. Après une réduction, la taille vaut la moitié de la nouvelle capacité; il faut donc, pour provoquer la réduction suivante, supprimer la moitié des éléments restants, et pour provoquer un agrandissement, en ajouter autant. Dans les deux cas, le travail effectué entre deux recopies est proportionnel à la taille de la recopie, ce qui est exactement la condition d'un amortissement constant. L'exercice 4.5 vous demande de le démontrer proprement, avec la fonction de potentiel adaptée.

Listes chaînées

Une suite de maillons

La liste chaînée abandonne la contiguïté. Chaque élément est rangé dans un maillon alloué séparément, qui contient la valeur et l'adresse du maillon suivant. La liste elle-même n'est rien de plus qu'une référence sur son premier maillon.

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant


def parcourir(tete):
    """Renvoie la liste des valeurs, du premier maillon au dernier."""
    valeurs = []
    courant = tete
    while courant is not None:
        valeurs.append(courant.valeur)
        courant = courant.suivant
    return valeurs

Ce que cette représentation gagne est immédiat: insérer un maillon entre deux maillons connus coûte $\Theta (1)$, quelles que soient la taille de la liste et la position. Deux affectations de champ suivant suffisent, et rien n'est déplacé. Dans un tableau, la même insertion oblige à décaler tous les éléments qui suivent, donc $\Theta (n)$ dans le pire des cas.

def inserer_apres(maillon, valeur):
    """Insere un nouveau maillon juste apres celui qui est donne: deux affectations."""
    maillon.suivant = Maillon(valeur, maillon.suivant)

Ce qu'elle perd est tout aussi immédiat: il n'y a plus d'accès par indice. Pour atteindre l'élément d'indice $i$, il faut suivre $i$ liens, donc $\Theta (i)$ déréférencements, et $\Theta (n)$ dans le pire des cas. Une liste chaînée ne se trie pas par tri rapide, ne se cherche pas par dichotomie, et ne se parcourt pas à l'envers.

La liste doublement chaînée

Ajoutons à chaque maillon un champ precedent. La liste doublement chaînée se parcourt dans les deux sens, et surtout elle permet de supprimer un maillon dont on tient la référence en $\Theta (1)$: il suffit de raccorder son prédécesseur à son successeur, alors qu'en simple chaînage il faut d'abord retrouver le prédécesseur, donc reparcourir la liste.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.precedent = None
        self.suivant = None


def supprimer(noeud):
    """Detache un noeud dont on tient la reference: quatre affectations au plus."""
    if noeud.precedent is not None:
        noeud.precedent.suivant = noeud.suivant
    if noeud.suivant is not None:
        noeud.suivant.precedent =

Le prix est de deux pointeurs par élément au lieu d'un, donc trois mots de mémoire par valeur stockée au lieu de deux, et de deux fois plus d'affectations à tenir cohérentes — ce qui est une source d'erreurs réelle, surtout sur les bords. L'astuce d'implémentation classique consiste à ajouter une sentinelle, un maillon fictif qui boucle la liste sur elle-même, de sorte qu'aucun pointeur ne soit jamais None et que les cas particuliers du premier et du dernier maillon disparaissent.

La comparaison, honnêtement

Voici le tableau des coûts. Il est à lire en regard d'un profil d'opérations, jamais isolément.

Le tableau dit une partie de la vérité. L'autre partie, le modèle RAM est incapable de la voir, et il faut la dire.

Piles et files

Deux disciplines d'accès

La pile et la file sont deux types abstraits qui restreignent volontairement l'accès aux extrémités, et cette restriction est leur intérêt: elle rend les deux opérations réalisables en $\Theta (1)$, et elle exprime une discipline que le reste du programme n'a plus à surveiller.

Une pile s'implémente en trois lignes sur un tableau dynamique: on empile en ajoutant en fin, on dépile en retirant la fin. Le coût est $\Theta (1)$ amorti pour l'empilement, par le théorème 4.1, et $\Theta (1)$ exact pour le dépilement si l'on ne rend jamais la mémoire. En Python, liste.append(x) et liste.pop() sont exactement cela, et c'est pourquoi ce cours n'écrira jamais de classe Pile: une list est une pile.

La file, elle, pose un vrai problème. Sur un tableau, enfiler en fin coûte $\Theta (1)$ amorti, mais defiler en tête coûte $\Theta (n)$, puisqu'il faut décaler tout le reste — c'est exactement ce que fait liste.pop(0) en Python, et c'est un piège classique, parce que le programme fonctionne parfaitement et qu'il est simplement quadratique. Deux réparations existent: le tableau circulaire, qui garde deux indices, celui de la tête et celui de la queue, et les fait tourner modulo la capacité; et la file par deux piles, qui est plus jolie et dont l'analyse est instructive.

La file par deux piles

L'idée tient en une phrase: on garde deux piles, entree et sortie. Enfiler, c'est empiler sur entree. Défiler, c'est dépiler sortie — et si sortie est vide, transvaser d'abord tout entree dedans, ce qui inverse l'ordre et remet le plus ancien élément au sommet.

class FileDeuxPiles:
    def __init__(self):
        self.entree = []
        self.sortie = []
        self.operations = 0        # empilements et depilements elementaires

    def enfiler(self, x):
        self.entree.append(x)
        self.operations += 1

    def defiler(self):
        if not self.sortie:
            while self.entree:                       # transvasement

L'opération barométrique est l'opération élémentaire de pile: un empilement ou un dépilement. Un defiler isolé peut en coûter $2j+1$, où $j$ est la taille de entree — autrement dit $\Theta (n)$ dans le pire des cas pour une opération. Et pourtant:

Démonstration. L'argument par agrégat tient en une ligne et donne déjà la conclusion: chaque élément est empilé sur entree une fois, dépilé de entree une fois, empilé sur sortie une fois et dépilé de sortie une fois — jamais plus, puisqu'un élément ne retourne jamais dans entree. Un élément coûte donc au plus 4 opérations élémentaires sur toute sa vie, et comme il y a au plus $m$ éléments enfilés, le total est majoré par $4m$.

La méthode du potentiel donne la constante 3 et, surtout, un coût amorti par type d'opération. Posons

qui vaut 0 dans l'état initial et n'est jamais négatif. Examinons les trois cas.

Un enfiler. Le coût réel est $1$ (un empilement) et $|\text{entree}|$ croît de 1, donc $\Phi$ croît de 2. Le coût amorti vaut $1+2=3$.

Un defiler avec sortie non vide. Le coût réel est $1$ (un dépilement) et $\Phi$ ne change pas, car entree n'est pas touchée. Le coût amorti vaut $1$.

Un defiler avec sortie vide et $|\text{entree}|=j\ge 1$. Le transvasement effectue $j$ dépilements et $j$ empilements, puis le dépilement final: coût réel $2j+1$. Après l'opération, entree est vide, donc $\Phi$ passe de $2j$ à $0$, soit une variation de . Le coût amorti vaut

Chaque coût amorti vaut donc au plus 3, et la propriété de télescopage donne le total annoncé, $\sum c_i\le 3m$. $\square$

Le potentiel a ici une lecture concrète que la fonction $\Phi =2s-c$ du tableau dynamique n'avait pas: il compte les opérations déjà payées d'avance. Chaque élément posé sur entree a laissé deux unités en réserve, exactement ce qu'il coûtera à transvaser. Le transvasement, si effrayant qu'il paraisse, ne coûte donc rien de plus que ce qui a déjà été perçu.

Tables de hachage

L'idée: calculer l'adresse au lieu de la chercher

Le type abstrait dictionnaire associe des valeurs à des clés: insérer un couple, chercher la valeur associée à une clé, supprimer une clé. Sur un tableau non trié, la recherche est $\Theta (n)$; sur un tableau trié, la dichotomie la ramène à $\Theta (\log n)$ mais l'insertion redevient $\Theta (n)$; l'arbre de recherche du chapitre 5 équilibre les deux à $\Theta (\log n)$. La table de hachage fait autre chose, et de façon radicale: elle calcule l'endroit où la clé doit se trouver.

Imaginons d'abord le cas favorable. Si les clés sont des entiers compris entre 0 et $U-1$, avec $U$ modeste, il suffit d'un tableau de $U$ cases, la clé $k$ occupant la case $k$: c'est l'adressage direct, et toutes les opérations sont $\Theta (1)$ dans le pire des cas. Le problème est que l'univers des clés est presque toujours immense devant le nombre de clés réellement présentes: on n'alloue pas un tableau de $2^{64}$ cases pour y ranger dix mille identifiants, et on n'en alloue pas un indexé par toutes les chaînes de caractères possibles.

L'idée du hachage est de remplacer l'univers par un tableau de $m$ cases, avec $m$ de l'ordre du nombre de clés attendues, et de calculer l'indice par une fonction.

Les collisions ne sont pas un accident: elles sont inévitables. Dès que $|U|>m$, le principe des tiroirs garantit l'existence de deux clés de même image. Toute la théorie des tables de hachage consiste donc, d'une part, à choisir $h$ pour que les collisions soient rares, et d'autre part à décider quoi en faire quand elles surviennent.

Ce qu'on demande à une fonction de hachage

Trois exigences, dans cet ordre.

Elle doit être déterministe. La même clé doit donner la même case, sans quoi on ne retrouve rien. Cela paraît évident; cela interdit pourtant de hacher un objet sur son adresse mémoire ou sur un champ qu'on modifiera ensuite. En Python, c'est la raison pour laquelle une list n'est pas hachable: elle est modifiable, et une clé dont la valeur change après l'insertion est une clé perdue.

Elle doit être calculable en temps constant, ou du moins en temps proportionnel à la taille de la clé et non au nombre de clés. Une fonction de hachage qui coûterait $\Theta (\log n)$ annulerait tout l'intérêt.

Elle doit répartir. C'est l'exigence de fond, et la seule qui soit difficile. Une bonne fonction de hachage envoie des clés «voisines» dans des cases éloignées, et ne laisse aucune régularité des données se transformer en régularité des indices. L'hypothèse théorique qui formalise l'idéal porte un nom, et nous en aurons besoin pour le théorème 4.3.

La méthode de la division

La plus simple: $h(k)=k\mathrm{mod}m$. Elle coûte une division entière et rien d'autre.

Son défaut est que la qualité de la répartition dépend entièrement du choix de $m$. Si $m=2^p$, alors $k\mathrm{mod}m$ ne conserve que les $p$ bits de poids faible de $k$: toute régularité de ces bits — des clés toutes paires, des adresses alignées sur 8 ou 16 octets, des identifiants terminés par un code de contrôle — devient une collision systématique. De même, si $m=10^p$, seuls les derniers chiffres décimaux comptent.

La règle d'usage est donc: prendre pour $m$ un nombre premier, éloigné d'une puissance de 2 et d'une puissance de 10. Un nombre premier n'a pas de diviseur commun non trivial avec les périodes qui pourraient exister dans les données, ce qui répartit les régularités au lieu de les concentrer. La table témoin de ce chapitre utilise $m=11$, premier, avec $h(k)=k\mathrm{mod}11$.

La méthode de la multiplication

La méthode de la multiplication affranchit du choix de $m$. On fixe une constante $A$ avec $0<A<1$, et l'on pose

c'est-à-dire: on multiplie la clé par $A$, on ne garde que la partie fractionnaire, et on la dilate sur $\{0,\dots ,m-1\}$. La partie fractionnaire de $kA$ balaie l'intervalle $[0,1)$ de façon d'autant plus régulière que $A$ est mal approché par les rationnels, et Knuth recommande pour cette raison

l'inverse du nombre d'or. L'intérêt pratique est double: $m$ redevient libre — on peut prendre une puissance de 2, ce qui remplace la division par un décalage de bits —, et la méthode utilise tous les bits de la clé, pas seulement les derniers.

En pratique on l'écrit en arithmétique entière, en travaillant sur $w$ bits: on pose $W=\lfloor A\cdot 2^w\rfloor$, on calcule $kW$ modulo $2^w$, et on retient les bits de poids fort. L'explorateur de ce chapitre implémente exactement cela, avec $w=32$ et .

La résolution par chaînage

La première réponse aux collisions est la plus naturelle: chaque case du tableau ne contient pas une clé mais une liste des clés qui ont cette image. C'est le chaînage.

def table_par_chainage(cles, m):
    """Range les cles dans m paquets, chacune a la fin de la liste d'indice k % m."""
    paquets = [[] for _ in range(m)]
    for k in cles:
        paquets[k % m].append(k)
    return paquets

Insérer coûte $\Theta (1)$: on calcule $h(k)$ et on ajoute en tête ou en fin de la liste. Chercher coûte le calcul de $h(k)$ plus le parcours de la chaîne, donc $\Theta (1+n_j)$ où $n_j$ est la longueur du paquet . Supprimer coûte pareil, et si la chaîne est doublement chaînée et qu'on tient la référence du maillon — c'est le seul endroit de ce cours où la liste doublement chaînée gagne franchement.

Démonstration. Notons $k_1,\dots ,k_n$ les clés présentes et fixons un indice de paquet $j$. Pour chaque $i$, introduisons la variable indicatrice

L'hypothèse de hachage uniforme simple dit exactement que $\mathrm{Pr}[h(k_i)=j]=1/m$, donc l'espérance d'une indicatrice, qui est la probabilité de l'événement qu'elle indique, vaut

La longueur du paquet $j$ est le nombre de clés qui y tombent, c'est-à-dire $n_j={\sum }_{i=1}^n{X}_i$. Par linéarité de l'espérance — qui vaut pour toute famille de variables aléatoires, indépendantes ou non, et c'est ce qui rend l'argument si économique —,

Ce théorème demande qu'on dise ce qu'il ne dit pas, sans quoi on lui fera dire n'importe quoi.

Premièrement, la moyenne des longueurs sur les $m$ paquets vaut $\alpha$ de façon triviale et inconditionnelle: les longueurs somment à $n$, donc leur moyenne arithmétique vaut $n/m$, hypothèse ou pas. Ce n'est pas cela que le théorème affirme. Il affirme que l'espérance de la longueur d'un paquet donné, avant de regarder les clés, vaut $\alpha$ — c'est-à-dire qu'aucun paquet n'est privilégié. L'hypothèse porte toute cette affirmation.

Deuxièmement, l'espérance n'est pas le maximum, et c'est le maximum qui décide du pire des cas d'une recherche. Sur la table témoin, l'espérance vaut $0,73$ et la plus longue chaîne en compte 3. Pour $n=m$, c'est-à-dire $\alpha =1$, on démontre — et ce résultat-là, qui relève d'un cours de probabilités, est admis ici — que la plus longue chaîne est de l'ordre de $\log n/\log \log n$ avec forte probabilité. Une simulation le rend visible: pour $m=1021$ et $n=1021$, sur cinquante tirages de clés distinctes, la plus longue chaîne mesure en moyenne maillons, alors que l'espérance d'une chaîne vaut 1.

Démonstration. La recherche d'une clé $k$ absente calcule $h(k)$, puis parcourt intégralement la chaîne du paquet $h(k)$, sans trouver, et échoue. Le nombre de comparaisons de clés vaut donc $n_{h(k)}$. Sous l'hypothèse de hachage uniforme simple, $h(k)$ est uniforme sur les $m$ paquets et indépendante des clés déjà rangées, donc, en conditionnant sur la valeur de $h(k)$,

par le théorème 4.3. En ajoutant le calcul de $h$ et l'accès au paquet, qui coûtent $\Theta (1)$, le coût total est $\Theta (1+\alpha )$. $\square$

Le coût d'une recherche fructueuse vaut, sous la même hypothèse, $1+\alpha /2-\alpha /(2n)$ comparaisons en moyenne: on s'arrête en moyenne au milieu de la chaîne, et la correction en $\alpha /(2n)$ vient de ce que la clé cherchée ne se compare pas à elle-même. La démonstration est du même type — une somme d'indicatrices sur les clés insérées après celle qu'on cherche — et nous l'admettons pour ne pas alourdir; elle figure dans le chapitre 11 de Cormen et al.

La conclusion pratique est celle-ci: si l'on maintient $\alpha$ borné par une constante, toutes les opérations du dictionnaire coûtent $\Theta (1)$ en moyenne. C'est le plus beau résultat du chapitre, et c'est aussi celui dont il faut retenir chaque mot: «en moyenne», et «sous l'hypothèse de hachage uniforme simple».

L'adressage ouvert et le sondage linéaire

Le chaînage alloue un maillon par clé, hors du tableau. L'adressage ouvert refuse cette allocation: toutes les clés vivent dans le tableau, à raison d'une par case, ce qui impose $n\le m$, donc $\alpha \le 1$. Quand la case visée est occupée, on en essaie une autre, selon une suite de sondage $h(k,0),h(k,1),h(k,2),\dots$ qui doit parcourir toutes les cases.

La suite la plus simple est le sondage linéaire: on essaie la case suivante, puis celle d'après, en bouclant.

def sondage_lineaire(cles, m):
    """Insere les cles par sondage lineaire et compte les sondes."""
    table = [None] * m
    sondes = 0
    for k in cles:
        i = 0
        while True:
            case = (k + i) % m
            sondes += 1                    # une case essayee, libre ou non
            if table[case] is None:

L'opération barométrique est la sonde: une case examinée, qu'elle soit libre ou occupée. Chercher une clé suit la même suite jusqu'à la trouver ou jusqu'à rencontrer une case libre, qui prouve son absence. Supprimer, en revanche, pose un problème que le chaînage n'a pas: vider une case briserait la suite de sondage de toutes les clés qui l'ont traversée, et les rendrait introuvables. On marque donc la case d'un témoin de suppression, une valeur spéciale qui n'arrête pas une recherche mais qu'une insertion peut réutiliser. Les témoins s'accumulent, et c'est une des raisons pour lesquelles une table en adressage ouvert doit être reconstruite périodiquement.

L'amas primaire

Ce que l'exemple 4.4 montre porte un nom.

C'est un mécanisme de renforcement, et il est visible sur la table témoin: les cases 4 à 9 forment un amas de longueur 6, c'est-à-dire que six cases sur onze sont collées, alors que les cases 2, 3 et 10 restent libres. Toute clé dont l'image tombe entre 4 et 9 devra traverser la fin de cet amas.

Quantitativement, le prix est connu — le résultat est dû à Knuth et sa démonstration relève d'un cours de probabilités, aussi ce chapitre l'admet. Sous l'hypothèse de hachage uniforme simple, le nombre moyen de sondes du sondage linéaire vaut approximativement

à comparer, pour une suite de sondage idéale dans laquelle chaque clé aurait une permutation de sondage uniforme — c'est ce qu'on appelle le hachage uniforme —, à

Le carré au dénominateur de (4.6) est le prix des amas, et il est féroce: à $\alpha =0,9$, la recherche infructueuse demande $50,5$ sondes en sondage linéaire contre $10$ en hachage uniforme.

Le double hachage

La parade consiste à faire dépendre le pas du sondage de la clé, pour que deux clés de même image n'aient pas la même suite de sondage et cessent de se suivre.

Pour que la suite parcoure les $m$ cases, il faut que $h_2(k)$ soit premier avec $m$; le plus simple est de prendre $m$ premier et $h_2(k)=1+(k\mathrm{mod}(m-1))$, qui est compris entre 1 et et donc premier avec . Deux clés en collision sur n'avancent alors plus du même pas, et les amas cessent de se renforcer: on parle de disparition de l'amas . Il subsiste un effet résiduel, dit amas , lorsque deux clés partagent à la fois et ; il est négligeable en pratique.

Sur la table témoin, avec $m=11$, $h_1(k)=k\mathrm{mod}11$ et $h_2(k)=1+(k\mathrm{mod}10)$, l'insertion des huit clés coûte au lieu de 15 — un gain d'une seule sonde, et il faut le dire ainsi: sur huit clés dans onze cases, l'amas n'a pas le temps de se former, et l'exemple est trop petit pour montrer le phénomène. C'est en simulant qu'on le voit.

Le facteur de charge et le redimensionnement

Tout ce qui précède se résume à une variable: $\alpha$. Le chaînage coûte $\Theta (1+\alpha )$ et se dégrade linéairement; l'adressage ouvert coûte $\Theta (1/(1-\alpha ))$ au mieux et explose quand $\alpha$ approche 1.

Il faut donc maintenir $\alpha$ borné, et la seule façon de le faire quand $n$ grandit est d'agrandir $m$. C'est le redimensionnement: lorsque $\alpha$ dépasse un seuil fixé — typiquement $0,75$ en chaînage, $0,5$ à $0,7$ en adressage ouvert —, on alloue une table de taille environ double et l'on réinsère toutes les clés. Réinsérer, et non recopier: la fonction de hachage dépend de $m$, donc chaque clé change de case.

Le redimensionnement coûte $\Theta (n)$, et l'on retrouve exactement la situation du tableau dynamique: une opération rare et chère au milieu d'opérations fréquentes et bon marché. L'analyse est la même, et le résultat aussi — énonçons-le pour pouvoir le démontrer. Dans une table de hachage initialement vide, de taille nulle, qui double sa taille et réinsère toutes ses clés dès que le facteur de charge dépasse un seuil fixé $\lambda$, toute suite de $n$ insertions coûte $O(n)$: le coût amorti d'une insertion est $\Theta (1)$.

Démonstration. Reprenons la fonction de potentiel du théorème 4.1, transposée: $\Phi =2n-\lambda m$, où $n$ est le nombre de clés et $m$ la taille de la table. Elle vaut 0 sur la table vide de taille nulle, et reste positive ensuite, puisque juste après un redimensionnement la table contient $\lambda m+1$ clés dans $2m$ cases, d'où $\Phi =2$. Une insertion sans redimensionnement coûte 1 et fait croître $\Phi$ de 2, donc coûte 3 en amorti. Une insertion qui déclenche le redimensionnement se produit quand ; elle coûte opérations — la réinsertion de clés, chacune en , plus l'insertion nouvelle — et le potentiel passe de à , soit une variation de . Le coût amorti vaut donc . Par télescopage, toute suite de insertions dans une table initialement vide coûte , et le coût amorti d'une insertion reste .

L'énoncé complet d'une table de hachage bien dimensionnée est donc: insertion, recherche et suppression en $\Theta (1)$ en moyenne sous l'hypothèse de hachage uniforme simple, et amorti pour l'insertion à cause du redimensionnement. Les deux qualificatifs sont de natures différentes — l'un probabiliste, l'autre non — et il faut les deux. C'est le seul endroit de ce cours où ils apparaissent ensemble, et c'est une bonne raison de ne pas les confondre.

L'explorateur ci-dessous met tout cela sous vos doigts. Réglez le nombre de cases, le nombre de clés et la fonction de hachage, et surveillez la ligne horizontale en tirets: c'est la longueur moyenne de chaîne, c'est-à-dire $\alpha$, et elle ne bouge pas quand vous changez de fonction de hachage. Ce qui bouge, c'est la plus longue chaîne. Tout le théorème 4.3 est dans cette dissociation.

Ce que sont vraiment le dict et le set de Python

Vous utilisez des tables de hachage depuis le chapitre 7 d'Introduction à la programmation sans qu'on vous l'ait dit. Le dict et le set de Python sont des tables de hachage, et quelques-uns de leurs comportements, qui paraissent arbitraires quand on les rencontre, sont des conséquences directes de ce chapitre.

Les deux utilisent l'adressage ouvert, pas le chaînage. La suite de sondage de CPython n'est ni linéaire ni un double hachage classique: elle combine un pas pseudo-aléatoire dérivé des bits de poids fort du haché, précisément pour éviter les amas primaires tout en restant bon marché. Le facteur de charge d'un dict est maintenu en dessous d'environ deux tiers, et la table est agrandie et réinsérée dès que ce seuil est dépassé — exactement le mécanisme démontré ci-dessus, avec ses insertions en $\Theta (1)$ amorti.

Une clé doit être hachable, c'est-à-dire posséder un __hash__ cohérent avec son __eq__. C'est pourquoi hash([1, 2]) lève une TypeError: une liste est modifiable, donc son haché pourrait changer après l'insertion, et la clé deviendrait introuvable dans sa propre table. Les tuples, eux, sont hachables si leurs éléments le sont.

La contrainte de cohérence produit une bizarrerie célèbre. La spécification exige que $x=y$ implique hash(x) == hash(y). Or, en Python, 1 == 1.0 == True. Donc ces trois objets ont le même haché et occupent la même case:

print(hash(1) == hash(1.0) == hash(True))
print({1: "a", 1.0: "b", True: "c"})
print(len({1, 1.0, True}))

True
{1: 'c'}
1

Le dictionnaire ne contient qu'une entrée. La clé conservée est celle qui a été insérée en premier — l'entier 1 — et la valeur est celle de la dernière affectation, 'c', parce que les deux affectations suivantes ont été comprises comme des mises à jour de la même clé. Ce n'est pas un défaut de Python: c'est le contrat des tables de hachage appliqué à un langage où ces trois valeurs sont égales.

L'ordre d'insertion est conservé depuis la version 3.7, où il est devenu une garantie du langage. Ce n'est pas une propriété des tables de hachage en général — une table de hachage n'a aucune raison d'avoir un ordre —, mais une conséquence de l'implémentation dite compacte de CPython, qui range les entrées dans un tableau dense, dans l'ordre d'arrivée, et n'utilise la table de hachage que comme un index vers ce tableau. Ne comptez pas là-dessus dans un autre langage.

Le hachage des chaînes est randomisé par un sel tiré au démarrage du processus, depuis Python 3.3 et par défaut, précisément pour la raison exposée plus haut: sans cela, un attaquant pourrait fabriquer des clés en collision et transformer un dictionnaire en liste chaînée. Une conséquence pratique: hash("bonjour") ne donne pas la même valeur d'une exécution à l'autre, et un programme qui dépendrait de cette valeur serait non reproductible.

Synthèse

• Un type abstrait de données est un contrat d'opérations; une structure de données en est une réalisation, avec ses coûts. On ne choisit pas une structure en soi, on la choisit contre un profil d'opérations: la même séquence, implémentée par un tableau ou par une liste chaînée, échange $\Theta (1)$ et $\Theta (n)$ sur l'accès par indice et sur l'insertion au milieu.
• Le tableau dynamique qui double sa capacité paie moins de 3 écritures par ajout, quelle que soit la suite d'ajouts: 2023 écritures pour mille ajouts, 2 048 575 pour un million. Les trois méthodes — agrégat, comptable, potentiel $\Phi =2s-c$ — donnent la même constante 3, et la borne est serrée, atteinte asymptotiquement en $n=2^k+1$. Le caractère de la croissance est l'ingrédient actif: agrandir de 100 en 100 rend le total quadratique, puis écriture par ajout pour puis .

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 10 pour les piles, files et listes chaînées; chapitre 11 pour les tables de hachage, le hachage universel et l'analyse complète du chaînage et de l'adressage ouvert; chapitre 16 pour les trois méthodes d'analyse amortie et les tableaux dynamiques.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour fixer en français le vocabulaire de l'amortissement («méthode de l'agrégat», «méthode comptable», «méthode du potentiel»).
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — sections 1.3 et 3.4, avec des mesures détaillées du redimensionnement et une discussion soignée du choix entre chaînage et adressage ouvert.
• Knuth, The Art of Computer Programming, vol. 3, 2ᵉ éd., Addison-Wesley — section 6.4, source originale des formules de coût du sondage linéaire et du hachage uniforme utilisées aux relations (4.6) et (4.7).
• Kleinberg & Tardos, Algorithm Design, Pearson — section 13.6, pour le hachage universel présenté comme un usage de l'aléatoire plutôt que comme une hypothèse sur les données.
• Documentation de référence de Python, The Python Language Reference, section «Data model», pour le contrat entre __hash__ et __eq__, et les notes de version de CPython 3.3, 3.6 et 3.7 pour la randomisation du hachage des chaînes et l'implémentation compacte du dictionnaire.