06 — Hash Tables : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~55 min

---

Table des matières

1. Introduction
2. Fonctions de hachage
3. Table de hachage : opérations
4. Collisions : chaînage séparé
5. Collisions : adressage ouvert et double hachage
6. Load factor et réhachage
7. Les hash maps des langages
8. Hachage cryptographique vs hachage de table
9. Applications
10. Résumé

---

1. Introduction

La table de hachage est probablement la structure de données la plus utilisée : dictionnaire, cache, index, ensemble. Elle implémente l'interface Map (clé → valeur) avec des opérations O(1) en moyenne.

L'idée : une fonction de hachage transforme une clé quelconque (chaîne, objet) en un index de tableau. La valeur est stockée à cet index.

Diagramme en cours de génération...

---

2. Fonctions de hachage

2.1 Définition

Une fonction de hachage h : Clés → {0, …, m-1} associe à chaque clé un index.

2.2 Propriétés d'une bonne fonction

2.3 Exemples

Méthode de division (la plus simple) :

def h_division(cle, m):
    return cle % m

Méthode multiplicative (Knuth) : h = ⌊m × (a·cle mod 1)⌋ avec a ≈ (√5−1)/2 ≈ 0,618.

def h_multiplicative(cle, m):
    a = 0.6180339887
    frac = (a * cle) % 1
    return int(m * frac)

Chaînes de caractères : variante polynomiale (rolling hash) :

def h_chaîne(s, m, base=31):
    h = 0
    for c in s:
        h = (h * base + ord(c)) % m
    return h

C'est la base de hashCode de Java (String) et des rolling hashes (Rabin-Karp, chapitre 13).

2.4 Mauvaise fonction : exemple pédagogique

def mauvaise_h(cle, m):
    return len(cle) % m    # toutes les clés de même longueur → même index !

→ Dégénère en liste chaînée unique → O(n).

---

3. Table de hachage : opérations

3.1 Insertion

def insérer(table, h, cle, valeur):
    i = h(cle)
    # gestion de collision (chaînage) :
    # ajouter (cle, valeur) dans la liste du seau i

3.2 Recherche

def rechercher(table, h, cle):
    i = h(cle)
    # chercher cle dans la liste du seau i

3.3 Suppression

• Chaînage : suppression dans la liste du seau — O(1) si double chaînée + nœud.
• Adressage ouvert : suppression marquée (tombstone), pas physique — sinon les recherches se cassent.

3.4 Complexités

Le pire cas arrive quand toutes les clés hachent au même index (mauvaise fonction ou attaque).

---

4. Collisions : chaînage séparé

4.1 Principe

Chaque seau contient une liste chaînée (ou un arbre) des paires qui hachent à cet index.

Diagramme en cours de génération...

class Seau:
    def __init__(self):
        self.paires = []          # liste de (clé, valeur)

class HashTableChainee:
    def __init__(self, m=8):
        self.m = m
        self.table = [Seau() for _ in range(m)]
        self.n = 0               # nombre de paires

    def _index(self, cle):
        return hash(cle) % self.m   # Python hash + division

    def put(self, cle, valeur):
        i = self._index(cle)
        for p in self.table[i].paires:
            if p[0] == cle:
                p[1] = valeur       # mise à jour
                return
        self.table[i].paires.append((cle, valeur))
        self.n += 1

    def get(self, cle):
        i = self._index(cle)
        for p in self.table[i].paires:
            if p[0] == cle:
                return p[1]
        raise KeyError(cle)

    def remove(self, cle):
        i = self._index(cle)
        for idx, p in enumerate(self.table[i].paires):
            if p[0] == cle:
                self.table[i].paires.pop(idx)
                self.n -= 1
                return
        raise KeyError(cle)

4.2 Analyse

• Si la fonction est uniforme et le load factor α = n/m ≈ O(1), la longueur moyenne des listes est O(α) = O(1).
• En Python, on utilise hash(cle) (modulo m) ; hash intègre une seed aléatoire pour les chaînes (protection DoS).

---

5. Collisions : adressage ouvert et double hachage

5.1 Principe

Pas de listes : toutes les paires vivent dans le tableau lui-même. Si le slot est occupé, on probe (sonde) la séquence suivante.

5.2 Probing linéaire

class HashLinear:
    def __init__(self, m=16):
        self.m = m
        self.table = [None] * m       # None = vide, ('DEL', None) = tombstone
        self.n = 0

    def _probe(self, cle, i):
        return (hash(cle) + i) % self.m     # h(cle) + i

    def put(self, cle, valeur):
        i = 0
        while True:
            j = self._probe(cle, i)
            slot = self.table[j]
            if slot is None or (slot == ('DEL', None)):
                self.table[j] = (cle, valeur)
                self.n += 1
                return
            if slot[0] == cle:
                self.table[j] = (cle, valeur)   # mise à jour
                return
            i += 1

    def get(self, cle):
        i = 0
        while True:
            j = self._probe(cle, i)
            slot = self.table[j]
            if slot is None:
                raise KeyError(cle)
            if slot[0] == cle and slot != ('DEL', None):
                return slot[1]
            i += 1

Problème : le clustering primaire — les blocs contigus d'occupation grossissent ; les inserts doivent traverser de longs blocs.

5.3 Probing quadratique

h(cle) + c₁·i + c₂·i² — évite le clustering primaire, mais la séquence peut ne pas couvrir tout le tableau.

5.4 Double hachage

Deux fonctions : h₁(cle) + i × h₂(cle) avec h₂ coprime à m (ex. m premier).

def h1(cle, m):
    return hash(cle) % m

def h2(cle):
    return 1 + (hash(cle) // 7) % 5     # h2 ∈ [1, 5], jamais 0

def probe(cle, i, m):
    return (h1(cle, m) + i * h2(cle)) % m

• Le second hachage décale différemment chaque clé → deux clés qui collident à h₁ ne collident pas à chaque étape.
• Meilleure répartition que le probing linéaire ; plus de calcul par probe.

5.5 Comparaison des stratégies

---

6. Load factor et réhachage

6.1 Load factor

Le load factor α = n/m (nombre de paires / nombre de seaux).

6.2 Réhachage (rehash)

Quand α dépasse un seuil (typiquement 0,75 en Java, 2/3 en CPython), on double m et on réinsère toutes les paires.

class HashTableResizable(HashTableChainee):
    SEUIL = 0.75

    def put(self, cle, valeur):
        super().put(cle, valeur)
        if self.n / self.m > self.SEUIL:
            self._rehash()

    def _rehash(self):
        ancien = self.table
        self.m *= 2
        self.table = [Seau() for _ in range(self.m)]
        self.n = 0
        for seau in ancien:
            for cle, valeur in seau.paires:
                self.put(cle, valeur)      # réinsérer sans re-déclencher

6.3 Coût amorti

Chaque réhachage coûte O(n) ; on double → sur n insertions, la somme des réhachages = O(n). O(1) amorti par insertion.

Même analyse que le tableau dynamique (chapitre 01), mais le réhachage réinsère réellement (recalcul des index), pas une simple copie.

6.4 Conflit avec le temps réel

Le réhachage peut geler le système (GC pause). Les systèmes temps réel utilisent des réhachages incrémentaux (progressifs) : on migre quelques seaux à chaque opération (technique de Redis et des bases).

---

7. Les hash maps des langages

7.1 Python — dict

• Adressage ouvert (open addressing, probing par indices de 5 × 2^k − 1 avec rehachage interne), valeurs compactes.
• Clés immuables uniquement (hashable) : int, str, tuple, frozenset.
• Maintient l'ordre d'insertion (depuis Python 3.7).
• Seed aléatoire par processus (protection contre les attaques par collisions).
• set = même mécanisme sans valeurs.

7.2 Java — HashMap

• Chaînage séparé : listes chaînées, promues en arbres rouge-noir si > 8 éléments (TREEIFY_THRESHOLD), puis re-linéarisées si < 6.
• Load factor par défaut 0,75.
• Non ordonné, autorise une clé null (seau 0).
• HashTable (vieux) : synchronisé ; HashMap : non.
• LinkedHashMap : maintient l'ordre d'insertion.

7.3 Go — map

• Adressage ouvert (buckets de 8 slots + overflow buckets).
• hash intégré avec seed aléatoire par map.
• Pire cas : une seule clé par slot est O(n) en amorti garanti par le runtime (rehash).
• Concurrence : non thread-safe (panic sur écriture concurrente) — sync.Map pour les cas d'usage spécifiques.

7.4 C++ — std::unordered_map

• Chaînage séparé (listes chaînées par seau).
• Load factor max 1,0 par défaut.
• Order non garanti ; buckets accessibles via bucket().
• Clés hashables via std::hash (spécialisable).
• Meilleure performance brute mais overhead mémoire plus élevé qu'un dict.

7.5 Tableau comparatif

---

8. Hachage cryptographique vs hachage de table

8.1 Pourquoi on ne les confond pas

8.2 Propriétés cryptographiques

1. Résistance à la préimage : étant donné h, ne pas retrouver x.
2. Résistance à la seconde préimage : étant donné x, ne pas trouver y ≠ x avec même hash.
3. Résistance aux collisions : ne pas trouver (x, y) avec même hash.

8.3 SHA-256 en pratique

import hashlib
print(hashlib.sha256(b"alice").hexdigest())
# 2bd806c97f0e00af1a1fc3328fa763a9269723c8db8fac4f93af71db186d6e90

• Sortie fixe 256 bits, quelle que soit la taille d'entrée.
• MD5 (128 bits) : cassé pour la collision (2004, Wang) — ne pas utiliser pour l'intégrité.
• SHA-1 (160 bits) : collision cassée (2017, SHAttered).

8.4 Table de hachage + crypto = signature, empreinte

• Empreinte de fichier : SHA-256 (vérification d'intégrité, git utilise SHA-1).
• Bloom filter (tables de bits) : k fonctions de hachage rapides, pas cryptographiques.
• Consistent hashing (distribué) : hash modulaire avec anneau (chapitre 24).

---

9. Applications

9.1 Caches

Hash map clé → valeur avec éviction (LRU chapitre 04) : caches HTTP, DNS, objets, Redis.

9.2 Dictionnaires et symbol tables

• Compilateurs : table des symboles (variables → type, adresse).
• Langages de programmation : dict, objets JavaScript ({...} = hash map), Map ES6.
• JSON parsing : dictionnaires.

9.3 Index

• Index de base de données (index hash pour égalité exacte).
• Index inversé (moteurs de recherche) : mot → liste de documents.
• Index géographique (par hachage géohash).

9.4 Ensembles et déduplication

• Set : présence O(1) (filtrer doublons, visites BFS/DFS).
• Déduplication de données (backup, stockage).
• Union-Find : souvent adossé à une hash map.

9.5 Autres

---

10. Résumé

1. Fonction de hachage : déterminisme, uniformité, rapidité — division, multiplicative, polynomiale.
2. Table de hachage : O(1) moyen pour insert/search/delete ; O(n) pire.
3. Collisions : chaînage séparé (listes), adressage ouvert (linéaire, quadratique), double hachage.
4. Suppression en adressage ouvert : tombstones.
5. Load factor α : chaînage α ≈ 1 ; ouvert α < 0,7 — sinon réhachage (O(1) amorti).
6. Langages : dict (ouvert), HashMap (chaînage+arbres), map Go (buckets), unordered_map (chaînage).
7. Crypto vs table : résistance aux collisions/préimage vs vitesse/uniformité. SHA-256 ; MD5 cassé.
8. Applications : caches, dictionnaires, index, ensembles, déduplication.

---

Exercices d'auto-évaluation

1. Pourquoi une mauvaise fonction de hachage dégénère-t-elle en O(n) ?
2. Que se passe-t-il si on supprime physiquement (sans tombstone) en adressage ouvert ?
3. À quel load factor réhache-t-on en Java ? En Python ?
4. Pourquoi les clés d'un dict Python doivent-elles être immuables ?
5. Citer 3 propriétés du hachage cryptographique absentes du hachage de table.
6. Pourquoi MD5 n'est-il plus utilisé pour l'intégrité ?

Passez au quiz puis aux TP.