Dictionnaires et tables de hachage

Dictionnaires et tables de hachage

Définition

Un dictionnaire (ou tableau associatif) associe à chaque clé une valeur. Opérations attendues : insertion, recherche et suppression par clé.

En Python : d = {"alice": 17, "bob": 12} ; accès d["alice"], ajout d["chloé"] = 15, test "bob" in d, suppression del d["bob"].

Table de hachage

Une fonction de hachage $h : \text{Clés} \to \{0, \dots, m-1\}$ transforme une clé en un indice dans un tableau de taille $m$. Une bonne fonction de hachage est rapide à calculer et distribue uniformément les clés.

Le couple (clé, valeur) est rangé dans la case T[h(clé)]. La recherche, l'insertion et la suppression sont alors en $O(1)$ en moyenne.

Gestion des collisions

Deux clés distinctes peuvent avoir le même haché : c'est une collision.

Chaînage : chaque case contient une liste des couples ayant ce haché.

class TableHachage:
    def __init__(self, m=16):
        self.m = m
        self.T = [[] for _ in range(m)]
    def _h(self, cle):
        return hash(cle) % self.m
    def ajouter(self, cle, val):
        seau = self.T[self._h(cle)]
        for i, (c, _) in enumerate(seau):
            if c == cle:
                seau[i] = (cle, val); return
        seau.append((cle, val))
    def chercher(self, cle):
        for c, v in self.T[self._h(cle)]:
            if c == cle: return v
        raise KeyError(cle)

Adressage ouvert : on cherche une case libre suivante (sondage linéaire, quadratique, double hachage).

Facteur de charge

$\alpha = n / m$ (nombre d'éléments / taille du tableau). Quand $\alpha$ dépasse un seuil (≈ 0,7), on redimensionne (rehashing) le tableau en doublant $m$, ce qui amortit le coût.

Complexités

Opération	Moyenne	Pire cas
Insertion	$O(1)$	$O(n)$
Recherche	$O(1)$	$O(n)$
Suppression	$O(1)$	$O(n)$

Le pire cas survient quand toutes les clés tombent dans le même seau (mauvaise fonction de hachage ou attaque).