Les dictionnaires dévoilés : le hachage

Indices : $212\mathrm{mod}5=2$, $212\mathrm{mod}5=2$, $225\mathrm{mod}5=0$, $225\mathrm{mod}5=0$, $227\mathrm{mod}5=2$. État : alvéole $0$ : $[\text{or},\text{ro}]$ ; alvéole $2$ : $[\text{as},\text{sa},\text{un}]$ ; alvéoles $1,3,4$ : vides. Deux paires d'anagrammes sont entrées en collision (même somme, fatalement), et "un" a rejoint l'alvéole $2$ par coïncidence arithmétique. Recherches : "sa" $\to$ alvéole $2$, deuxième de la chaîne : $2$ comparaisons ; "un" : $3$ comparaisons ; "il" $\to 213\mathrm{mod}5=3$, alvéole vide : $0$ comparaison — l'absence se constate immédiatement. (Le déséquilibre saute aux yeux : cinq clés, deux alvéoles occupées sur cinq — la fonction-somme disperse mal, et l'exercice 6 chiffrera le prix ; noter aussi que l'absence est souvent moins chère que la présence : on ne parcourt que l'alvéole désignée, pas la table.)

Acceptés : 3.14, "abc", (1, 2), ((1,), "a") (tuple de hachables, récursivement), frozenset({1, 2}) (l'ensemble gelé, donc immuable). Refusés — TypeError : [1, 2] (liste, mutable), (1, [2]) (le tuple est immuable mais son contenu liste ne l'est pas : la mutabilité se propage de l'intérieur), {1, 2} (ensemble mutable). Gels : liste $\to$ tuple([1, 2]) ; tuple contaminé $\to$ (1, (2,)) ; ensemble $\to$ frozenset. (Le critère opérationnel : « cette clé pourrait-elle changer pendant qu'elle est dans le dictionnaire ? » — si oui, l'adressage par contenu n'a plus de sens, et Python préfère l'interdire à la source que vous laisser perdre vos données en silence ; on a déjà utilisé des clés-tuples sans le savoir : les sommets-cases $(i,j)$ des grilles du chapitre 12.)

moyenne = sum(notes.values()) / len(notes)            # (a) 14.75

inverse = {}                                          # (b)
for nom, note in notes.items():
    if note not in inverse:
        inverse[note] = []
    inverse[note].append(nom)
# {15: ["Ana", "Eva"], 12: ["Bob"], 17: ["Lou"]}

meilleurs, record = [], None                          # (c)
for nom, note in notes.items():
    if record is None or note > record:
        meilleurs, record = [nom], note
    elif note == record:
        meilleurs.append(nom)
# (["Lou"], 17)

(b) est le motif d'indexation inverse — regrouper par valeur — déjà vu pour les anagrammes (chapitre 2) et le GROUP BY (chapitre 16) : c'est partout le même geste, accumuler dans un dictionnaire de listes. (c) reprend le champion du chapitre 2, enrichi des ex æquo. (L'inverse d'un dictionnaire n'est un dictionnaire simple que si les valeurs sont distinctes — sinon, valeur $\to$ liste, et l'oublier écrase silencieusement Ana par Eva : le bogue d'écrasement, cousin de celui des tris non stables.)

def supprimer(table: list, cle) -> None:
    alv = table[hash(cle) % len(table)]
    for k in range(len(alv)):
        if alv[k][0] == cle:
            alv.pop(k)
            return                            # au plus une occurrence : invariant

def taille(table: list) -> int:
    return sum(len(alv) for alv in table)

T = creer(3)                                  # petite table : collisions garanties
inserer(T, "as", 1); inserer(T, "sa", 2); inserer(T, "or", 3)
assert chercher(T, "sa") == 2                 # présente, en collision
assert chercher(T, "il") is None              # absente
inserer(T, "as", 9)                           # mise à jour...
assert chercher(T, "as") == 9 and taille(T) == 3   # ...sans doublon !
supprimer(T, "or"); assert chercher(T, "or") is None and taille(T) == 2
supprimer(T, "il")                            # supprimer une absente : sans effet

L'invariant de structure — chaque clé apparaît au plus une fois dans toute la table — est ce que le test de mise à jour vérifie : c'est lui que la boucle d'inserer protège en cherchant la clé avant d'ajouter. (Choisir $m=3$, minuscule, pour le test est un art : on veut des collisions dans le jeu de tests, sinon la moitié du code — le parcours de chaîne — n'est jamais exercée ; tester une table de hachage sur une grande table presque vide, c'est tester un parapluie par beau temps.)

import random
m = 1000
longueurs = [0] * m
for _ in range(1000):
    longueurs[random.randrange(m)] += 1       # l'alvéole d'une clé "au hasard"

vides = longueurs.count(0) / m                #   0.368
occupees = [l for l in longueurs if l > 0]
moyenne_nv = sum(occupees) / len(occupees)    #   1.58
maxi = max(longueurs)                         #   5 à 7

Mesures typiques : $\approx 37\%$ d'alvéoles vides (la prédiction $(1-1/m{)}^n\approx {\mathrm{e}}^{-1}\approx 0,368$ du cours de probabilités), chaînes occupées de $1,6$ en moyenne, maximum $5$ à $7$. Lecture pour le coût : à charge $1$, une recherche parcourt en moyenne moins de deux couples — le $O(1)$ moyen est très concret — mais quelques clés malchanceuses coûtent $5$ à $7$ comparaisons : le $O(1)$ est une moyenne, pas une garantie uniforme. (Ce maximum croît très lentement avec $n$ — en $\log n/\log \log n$, dit la théorie — c'est pourquoi les tables réelles tolèrent la charge $0,75$ sans drame ; et ce petit modèle « boules dans des urnes » est exactement celui des anniversaires partagés : les collisions arrivent bien plus tôt qu'on croit, d'où l'obligation de les gérer plutôt que de les espérer rares.)

(a) Les anagrammes fournissent les collisions en série : les $200$ chaînes "a" k + "b" + "a" (199 - k) ont toutes la même somme. Insérées avec la fonction-somme, elles tombent dans la même alvéole : la table est une liste déguisée, et $1000$ recherches y coûtent $\sim 1000\times 100$ comparaisons — des millisecondes contre des microsecondes avec hash (qui les disperse, l'ordre des caractères comptant dans son calcul) : un facteur $50$ à $100$, mesuré. (b) La somme est commutative : elle ignore l'ordre des caractères, donc identifie toutes les permutations — une classe entière de clés naturelles (les anagrammes !) s'effondre sur une valeur. Une bonne fonction de hachage doit être sensible à tout : contenu, ordre, longueur — le moindre invariant ignoré devient un gisement de collisions. (c) Même avec une bonne fonction, un adversaire qui la connaît peut calculer hors ligne des milliers de clés en collision et les soumettre à un serveur (formulaires, paramètres web) : chaque requête coûte alors $O(n)$, le service s'effondre. La parade de Python : une graine secrète tirée au lancement, qui rend le haché imprévisible de l'extérieur — la dispersion redevient un pari sûr. (Moralité en deux temps : la complexité « en moyenne » suppose que les entrées ne conspirent pas contre vous ; quand elles le peuvent — le pire cas est choisi, pas tiré au sort — c'est la conception qui doit restaurer le hasard. Le tri rapide a le même talon d'Achille, chapitre 9 : pire cas sur entrée triée, pivot aléatoire en parade.)

(a) L'insertion calcule $\text{hash((1, 2))}\mathrm{mod}m$ — disons l'alvéole $4$ — et y range $[[1,2],\text{"x"}]$. Après cle.append(3), l'objet dans la table est devenu $[1,2,3]$ (c'est le même objet, partagé — chapitre 10 !). Chercher $[1,2,3]$ : l'adressage calcule $\text{hash((1, 2, 3))}$ — une autre alvéole, vide ou étrangère : introuvable. Chercher $[1,2]$ : retour à l'alvéole $4$… où la comparaison couple[0] == [1, 2] échoue, la clé stockée valant désormais $[1,2,3]$ : introuvable aussi. La valeur "x" est orpheline : présente en mémoire, inaccessible par toute recherche — ni un bogue de la table, ni une erreur d'exécution : un état incohérent silencieux.

(b) L'invariant « toute clé stockée se trouve dans l'alvéole que son haché désigne » — vrai à l'insertion, falsifié de l'extérieur par la mutation : aucune ligne de code de la table n'a fauté, et aucune ne peut s'en apercevoir sans tout re-parcourir. (c) Python interdit donc le problème à la racine : refuser les clés mutables, c'est rendre cet état inatteignable — un invariant garanti par construction plutôt que par discipline, le choix de conception le plus robuste du chapitre 10. (La table-jouet qui « accepte tout » paraissait plus libérale ; elle était seulement plus dangereuse — toute la différence entre une contrainte arbitraire et une contrainte qui encode une nécessité.)

(a)

def inserer_auto(table: list, cle, valeur) -> list:
    """Insère et renvoie la table (la même, ou une neuve agrandie)."""
    inserer(table, cle, valeur)
    if taille(table) > 0.75 * len(table):
        neuve = creer(2 * len(table))
        for alv in table:
            for c, v in alv:
                inserer(neuve, c, v)          # re-hachage : les adresses changent
        return neuve
    return table

(b) La courbe du temps cumulé est une droite — pente $O(1)$ par insertion — décorée de petites marches verticales aux tailles $\sim 0,75\cdot 2^k$ : chaque doublement se paie d'un à-coup en $O(n)$, de plus en plus rare. (c) Si la table finit avec $2^K$ alvéoles, les redimensionnements ont réinséré successivement $\sim 0,75\cdot (2^0+2^1+\cdots +2^{K-1})<0,75\cdot 2^K\le 2n$ couples : la série géométrique borne le tout par $O(n)$ — soit $O(1)$ amorti par insertion, exactement l'argument de la file à deux piles (chapitre 13, banque) et pour la même raison : chaque élément n'est déménagé qu'un nombre de fois borné par la géométrie des doublements. (C'est le doublement qui fait tout : agrandir de $+100$ alvéoles à chaque seuil donnerait $O(n^2)$ total — la croissance multiplicative est la signature des coûts amortis constants, et la liste Python elle-même grandit ainsi sous vos append depuis le premier chapitre.)

(a) C'est la table du cours, délestée des valeurs : les alvéoles stockent des clés nues, ens_ajouter ne fait rien si la clé est déjà là, ens_contient parcourt l'alvéole. Le déjà-vu :

def premiere_repetition(t: list):
    vus = ens_creer(2 * len(t))               # charge finale <= 0.5
    for x in t:
        if ens_contient(vus, x):
            return x
        ens_ajouter(vus, x)
    return None

(b) Sur $10^4$ éléments sans répétition (le pire cas) : la version liste fait $\sim n^2/2=5\cdot 10^7$ comparaisons — de l'ordre de la seconde ; la version table, $\sim n$ opérations d'alvéoles courtes — quelques millisecondes. Le facteur $\sim 1000$ est la promesse du chapitre 2, désormais expliquée de bout en bout : on sait ce qui se passe dans chaque alvéole. (c) Un set est un dict dont seules les clés existent — mêmes exigences (éléments hachables), mêmes coûts, même mécanique ; l'union de deux ensembles est une double insertion ($O(n_1+n_2)$ en moyenne), l'intersection un filtre du petit par appartenance au grand. (D'où la règle d'or des collections, maintenant fondée : « ai-je besoin d'associer une valeur ? » — oui : dict ; non, seulement d'appartenir : set ; et l'ordre, lui, n'appartient à aucun des deux — il est la spécialité des listes, et le hachage l'a sacrifié en échange du $O(1)$.)

(a)

def index_inverse(mots: list) -> dict:
    index = {}
    for i in range(len(mots)):
        if mots[i] not in index:
            index[mots[i]] = []
        index[mots[i]].append(i)
    return index

Un parcours, une opération de dictionnaire par mot : $O(n)$ en moyenne pour $n$ mots — le motif d'indexation inverse de l'exercice 3, aux positions près. (b) « Positions de m » : index.get(m, []), $O(1)$ en moyenne — contre $O(n)$ par re-parcours du texte à chaque requête. « Mots de plus de $k$ occurrences » : un parcours de l'index, $O(\text{vocabulaire})$ — c'est un GROUP BY … HAVING COUNT > k (chapitre 16) exécuté à la main, et l'index est le groupement, déjà fait. (c) L'index stocke chaque position une fois plus le vocabulaire : $O(n)$ — le texte en double, environ. L'échange est typique : payer $O(n)$ d'espace et $O(n)$ de préparation une fois, pour des requêtes en $O(1)$ à volonté ; rentable dès la deuxième requête, comme l'index du moteur SQL (chapitre 16, banque) et pour la même raison. (d) Un moteur de recherche est cet index à l'échelle du web : mot $\to$ liste de pages (et positions), construit par les robots d'indexation, interrogé en $O(1)$ par milliard de requêtes — l'intersection des listes de plusieurs mots donnant les pages qui les contiennent tous. (Que la recherche dans tout le web réponde plus vite que la recherche dans un fichier local non indexé n'est pas un paradoxe : c'est la différence entre avoir, ou non, déplacé le travail avant la question — la leçon finale du hachage, et de tout ce chapitre.)