Dictionnaires et tables de hachage

En clair. Clés/valeurs, complexité

Ce qu'on te demande au bac (Spé NSI) : maîtriser le vocabulaire de « Dictionnaires et tables de hachage », savoir refaire les raisonnements du cours et les réutiliser sur un sujet ou un document nouveau.

Conseil de révision. Lis d'abord cet encadré, puis fais le quiz : si tu bloques, reprends la partie du cours correspondante.

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

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