#Tables de hachageCopier le lien

Prérequis: tableaux (accès indexé O(1)) et coût amorti (redimensionnement du tableau dynamique).

Objectifs:

• Dérouler la chaîne clé → hash → bucket et piloter le facteur de charge.
• Comparer chaînage et adressage ouvert, avec leurs pires cas respectifs.
• Reconnaître les situations pathologiques (mauvais hachage, clés mutables, suppressions en adressage ouvert).

#Invariant et chaîne de calculCopier le lien

Une table de hachage stocke des paires (clé, valeur) dans un tableau de m alvéoles. L'invariant de recherche: toute clé k insérée est atteignable en partant de l'alvéole h(k) mod m et en suivant la stratégie de résolution de collisions. Tant que cet invariant tient, une recherche ne visite que cette alvéole et sa suite de sondage.

La chaîne complète:

1. Calculer le hash de la clé: h(k), entier.
2. Réduire à l'indice d'alvéole: h(k) mod m.
3. Si l'alvéole est occupée par une autre clé (collision), appliquer la stratégie: liste de débordement (chaînage) ou alvéole suivante selon un pas déterministe (adressage ouvert).

#Le dictionnaire: quelles opérations exactement?Copier le lien

Une table de hachage est l'implantation de référence d'un objet plus abstrait, l'ensemble dynamique: un ensemble qui grandit, rétrécit et change au fil de l'exécution. Chaque élément y est représenté par un objet dont un attribut joue le rôle de clé identifiante; les autres attributs sont des données satellites transportées avec la clé et ignorées par la structure. Si les clés sont deux à deux distinctes, on peut identifier l'ensemble à son ensemble de clés.

Les opérations typiques forment deux familles.

Requêtes (elles ne modifient rien):

• SEARCH(S, k): renvoyer un pointeur vers l'élément de clé k, ou NIL s'il n'existe pas.
• MINIMUM(S) / MAXIMUM(S): plus petite / plus grande clé — définies seulement si les clés sont prises dans un ensemble totalement ordonné.
• SUCCESSOR(S, x) / PREDECESSOR(S, x): la clé immédiatement supérieure / inférieure à celle de x, ou NIL si elle n'existe pas.

Opérations modificatrices:

• INSERT(S, x): ajouter l'élément pointé par x (ses attributs sont supposés déjà initialisés).
• DELETE(S, x): retirer l'élément pointé par x — noter que l'argument est un pointeur, pas une clé; supprimer « la clé k » suppose donc d'abord une recherche.

Un appel à MINIMUM suivi de n − 1 appels à SUCCESSOR énumère les n éléments de l'ensemble en ordre trié: c'est la propriété qui distingue une structure ordonnée (arbre de recherche) d'une structure purement associative (table de hachage). Une table de hachage implante SEARCH, INSERT, DELETE en Θ(1) attendu, mais ne fournit aucune des quatre requêtes d'ordre — elle ne sait pas dire « quel est le plus petit » ni « quel est le suivant ». C'est le critère de choix décisif entre les deux structures.

#Ce que coûte l'implantation par tableauCopier le lien

Un ensemble dynamique peut toujours se représenter par un tableau. Les coûts dépendent alors entièrement de l'ordre dans lequel on le maintient:

Lecture: le tableau trié achète les requêtes d'ordre et la recherche logarithmique, mais paie chaque modification en Θ(n) — insérer ou retirer au milieu impose de décaler tout le reste. Le tableau non trié est le miroir exact: modification immédiate, toute interrogation linéaire. Aucune des deux lignes ne domine; c'est précisément ce manque qu'aucune structure de ce module ne comble entièrement — un arbre de recherche équilibré donne Θ(log n) partout, une table de hachage donne Θ(1) attendu sur les trois opérations du dictionnaire mais renonce à l'ordre.

#Facteur de charge et redimensionnementCopier le lien

Le facteur de charge α = n/m (n éléments, m alvéoles) mesure le remplissage. C'est lui, pas le nombre d'éléments, qui gouverne les performances:

• Chaînage: longueur moyenne d'une liste = α, recherche moyenne en O(1 + α).
• Adressage ouvert: le coût explose quand α s'approche de 1; on garde α ≤ 0.75 environ.

Quand α dépasse le seuil, on double m et on réinsère tous les éléments ( indispensable: h(k) mod m change avec m, un élément déplacé serait sinon perdu). La réinsertion coûte O(n), mais comme les doublements sont de plus en plus espacés, la séquence d'insertions reste en O(1) amorti, exactement comme le tableau dynamique.

#Animation interactiveCopier le lien

La visualisation ci-dessous insère des clés et résout les collisions par adressage ouvert: observez comment une clé tombée sur une alvéole occupée se décale vers la suivante, et comment la répartition se dégrade quand les clés s'accumulent.

Contrôle à faire: après une série d'insertions, cherchez une clé: le parcours consulte d'abord son alvéole d'origine, puis les suivantes. C'est exactement la suite de sondage de l'insertion; si elle est interrompue (voir suppressions plus bas), la clé devient introuvable alors qu'elle est bien présente.

#Exemple rapide (dictionnaire Python)Copier le lien

d.get renvoie None pour une clé absente au lieu de lever KeyError: à réserver aux absences attendues, sinon les bugs de clé se masquent.

#Exercice guidé: table par chaînageCopier le lien

Implémentez put, get, remove avec une liste de débordement par alvéole. Invariant: toutes les paires dont la clé a pour hash h sont dans la liste de table[h mod m], au plus une paire par clé.

1class HashTable:2    def __init__(self, size=10):3        self.size = size4        self.table = [[] for _ in range(size)]   # m listes vides5        self.n = 0                                # nombre de paires6 7    def _index(self, key):8        return hash(key) % self.size9 10    def put(self, key, value):11        bucket = self.table[self._index(key)]12        for i, (k, _) in enumerate(bucket):13            if k == key:14                bucket[i] = (key, value)   # mise à jour, pas de doublon

Trace: avec m = 10, supposons h("nom") mod 10 = 3 et h("age") mod 10 = 3. Après put("nom", "Alice") puis put("age", 30), l'alvéole 3 contient [("nom", "Alice"), ("age", 30)]: deux paires cohabitent dans la même liste de débordement. get("age") parcourt cette liste courte et rend 30. remove("age") retire la paire; get("age") lève ensuite KeyError.

Coûts: moyenne en O(1 + α). Une clé existante est mise à jour en place (pas de doublon), une suppression ne déplace rien (liste), contrairement à l'adressage ouvert.

#Chaînage contre adressage ouvertCopier le lien

En adressage ouvert, supprimer physiquement une alvéole brise l'invariant de recherche: une clé plus loin dans la chaîne de sondage devient inaccessible. On remplace la paire par un marqueur « supprimé » (tombstone) que la recherche traverse mais où l'insertion peut se placer; il faut périodiquement rehasher pour éliminer les marqueurs.

#Filtres de Bloom (approximation)Copier le lien

Un filtre de Bloom occupe m bits et utilise k fonctions de hachage. Insertion: mettre à 1 les k positions h_i(x). Test: si un des k bits vaut 0, l'élément est certainement absent; s'ils valent tous 1, il est possiblement présent (faux positifs possibles, jamais de faux négatifs).

Manipulez les paramètres m et k dans la visualisation et observez le taux de faux positifs:

Le taux de faux positifs vaut approximativement (1 − e^{−kn/m})^k; pour un budget de m/n bits par élément, le k optimal est (m/n) · ln 2.

#Exercice: tracer une table par adressage ouvertCopier le lien

Soit m = 7, insertion par sondage linéaire, et les indices h(a)=3, h(b)=3, h(c)=0, h(d)=4.

1. Insérez a, b, c, d dans cet ordre. Donnez le tableau final.
2. Puis supprimez b selon deux méthodes: effacement physique, marqueur tombstone. Dans chaque cas, la recherche de a réussit-elle?

Correction:

1. a → alvéole 3. b → 3 occupé, tente 4, libre: b en 4. c → 0. d → 4 occupé, tente 5, libre: d en 5. Tableau: [c, ·, ·, a, b, d, ·].
2. Après l'étape 1, la chaîne de sondage partant de l'alvéole 3 est 3 → 4 → 5 (a, b, d).
   • Effacement physique de b (alvéole 4 vidée): une recherche de d, dont le sondage part de 4, s'arrête à l'alvéole 4 vide et conclut « absent » à tort. d est pourtant bien dans la table: c'est l'invariant de recherche qui est cassé, pas la donnée. La recherche de a, elle, réussit toujours (a est trouvé en 3 avant d'atteindre le trou).
   • Marqueur tombstone en 4: la recherche de d traverse le marqueur et trouve bien d en 5. La recherche de a réussit aussi. Seul le tombstone préserve l'invariant pour toutes les clés.

À retenir: l'effacement physique ne casse pas la recherche de la clé supprimée (elle n'est plus là), mais celle des clés insérées plus loin dans sa chaîne de sondage. D'où le tombstone, à nettoyer par un rehash périodique.

#Mini-quizCopier le lien