Écrire à la main une table de hachage à seaux

class TablePauvre:
    """Table de hachage a chainage, ecrite a la main pour VOIR les collisions."""

    def __init__(self, nb_seaux=8):
        self.seaux = [[] for _ in range(nb_seaux)]

    def _indice(self, cle):
        return hash(cle) % len(self.seaux)

    def ajouter(self, cle, valeur):
        seau = self.seaux[self._indice(cle)]
        for i, (c, _) in enumerate(seau):
            if c == cle:
                seau[i] = (cle, valeur)     # la cle existait : on REMPLACE
                return
        seau.append((cle, valeur))

    def obtenir(self, cle):
        for c, v in self.seaux[self._indice(cle)]:
            if c == cle:
                return v
        raise KeyError(cle)

    def plus_long_seau(self):
        return max(len(s) for s in self.seaux)

Le chaînage, et ce qu'il coûte. Deux clés différentes peuvent tomber dans le même seau — c'est une collision, et elle est inévitable dès qu'il y a plus de clés que de seaux. La parade est ici la plus simple : on empile les couples dans une liste, et la recherche la parcourt. Le coût d'un accès n'est donc pas vraiment constant : il est constant tant que les seaux restent courts. C'est la nuance que la classe de terminale approfondira, et que la première retient sous la forme « l'accès par clé est direct ».

Les mesures. $24$ clés dans $8$ seaux : le plus long seau contient $5$ éléments — et ce nombre change d'une exécution à l'autre, puisque le hachage des chaînes est tiré au démarrage. Trois exécutions successives donnent les répartitions [4, 4, 4, 1, 6, 2, 2, 1], [3, 5, 2, 1, 2, 3, 7, 1], [4, 3, 1, 2, 3, 3, 1, 7] : jamais trois par seau, comme un partage régulier le voudrait. Le principe des tiroirs garantit seulement qu'un seau en a au moins trois.

Avec $4096$ entiers dans $4096$ seaux, en revanche, le plus long seau contient $1$ élément : aucune collision. C'est que hash(n) == n pour un petit entier, et que $n\mathrm{mod}4096$ parcourt exactement tous les seaux — un cas idéal, et trompeur. Il illustre bien pourquoi une fonction de hachage se juge sur des données réalistes et non sur celles qui l'arrangent.

Vérification.

t = TablePauvre(8)
for i in range(24):
    t.ajouter("cle%d" % i, i)
assert t.obtenir("cle7") == 7
t.ajouter("cle7", 700)
assert t.obtenir("cle7") == 700     # remplacement, pas ajout
assert t.plus_long_seau() >= 3      # principe des tiroirs : 24 clefs, 8 seaux

try:
    t.obtenir("absente")
    assert False
except KeyError:
    pass

L'assert sur plus_long_seau() >= 3 est le seul qu'on puisse écrire : toute valeur exacte serait fausse à la prochaine exécution.