Aller au contenu principal

Tables de hachage

Progression

#Tables de hachage

Fonctions de hachage, collisions, sondage/chaînage, et complexités moyennes/pires cas.

Objectifs d’apprentissage

  • Comprendre clé → hash → bucket, facteur de charge et redimensionnement.
  • Comparer chaînage (separate chaining) vs adressage ouvert (linear/quadratic probing, double hashing).
  • Identifier les cas pathologiques et choisir de bons hachages.

#Animation interactive

Voici une animation qui illustre le fonctionnement d'une table de hachage avec gestion des collisions par adressage ouvert :

[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Table de hachage initialisée avec 10 emplacements
Étape 1 / 1 | Taille: 10

#Exemple (Python — dictionnaires)

Chargement de l’éditeur...

#Exercice : Implémentation d'une table de hachage

Implémentez une table de hachage simple en Python avec gestion des collisions par chaînage.

#Instructions

  1. Créez une classe HashTable avec une taille fixe.
  2. Implémentez une fonction de hachage simple (par exemple, modulo la taille de la table).
  3. Utilisez des listes pour gérer les collisions (chaînage).
  4. Implémentez les méthodes put(key, value), get(key) et remove(key).

#Exemple de code

pythonpython
1class HashTable:2    def __init__(self, size=10):3        self.size = size4        self.table = [[] for _ in range(size)]5    6    def _hash(self, key):7        return hash(key) % self.size8    9    def put(self, key, value):10        index = self._hash(key)11        bucket = self.table[index]12        13        # Vérifier si la clé existe déjà14        for i, (k, v) in enumerate(bucket):
Chargement de l’éditeur...
Collisions

Inévitables quand l’espace de clés est plus grand que la table; gérées par chaînage (listes) ou sondage (open addressing).

Facteur de charge (load factor)

α = n / m (éléments / buckets). Maintenir α dans une plage (ex: ≤ 0.75) et redimensionner ×2 pour conserver O(1) amorti.

Fonction de hachage

Une mauvaise fonction de hachage peut concentrer les clés et dégrader les performances, voire exposer à des attaques par collisions. Utilisez des fonctions solides et, côté serveur, défendez‑vous contre des données hostiles.

#Filtres de Bloom (approximation)

Présent ? non
Faux positifs estimés: 0% (m=64, k=3, n=0)

Un filtre de Bloom répond « possiblement présent » ou « certainement absent ». Paramètres: m bits, n éléments, k fonctions de hachage. Le taux de faux positifs ≈ (1 - e^{-kn/m})^k ; pour un α donné, on choisit k ≈ (m/n) ln 2.

Usages

Fronts de cache, pré‑filtrage d’URL/spam, joints à large échelle. Complétez par un store exact pour les hits.

Quelle garantie un filtre de Bloom fournit‑il ?
Quelle garantie un filtre de Bloom fournit‑il ?

#Pièges fréquents

Une mauvaise fonction de hachage concentre les clés et dégrade les performances vers O(n). En adressage ouvert, les suppressions nécessitent un marqueur « tombstone » pour conserver la propriété de recherche; sans lui, des éléments deviennent inaccessibles. Des clés mutables modifiées après insertion provoquent des incohérences; préférez des clés immuables. En contexte hostile (serveur), la résistance aux attaques par collisions compte autant que la vitesse moyenne; l’aléa dans le hachage ou des choix de fonctions plus robustes rendent le comportement moins prédictible pour un attaquant.

#Mini‑quiz

Quel paramètre pilote le redimensionnement ?
Quel paramètre pilote le redimensionnement ?