# dict en Python EST une table de hachage : O(1) en moyenne pour get/set/delete
cache = {}
cache["utilisateur:42"] = {"nom": "Alice"}   # O(1) moyen
valeur = cache.get("utilisateur:42")           # O(1) moyen
del cache["utilisateur:42"]                    # O(1) moyen

# Fonction de hachage simple (à but pédagogique -- Python utilise hash() en interne)
def hachage_simple(cle: str, taille_table: int) -> int:
    total = sum(ord(c) for c in cle)
    return total % taille_table

# --- Implémentation d'une table de hachage avec gestion de collisions par chaînage ---
class TableHachageChainage:
    def __init__(self, capacite: int = 16):
        self._capacite = capacite
        self._taille = 0
        self._buckets: list[list] = [[] for _ in range(capacite)]

    def _index(self, cle) -> int:
        return hash(cle) % self._capacite

    def inserer(self, cle, valeur) -> None:
        # facteur de charge = taille / capacité -- au-delà de ~0.75, on redimensionne
        if self._taille / self._capacite > 0.75:
            self._redimensionner()
        bucket = self._buckets[self._index(cle)]
        for i, (k, _) in enumerate(bucket):
            if k == cle:
                bucket[i] = (cle, valeur)   # met à jour une clé existante
                return
        bucket.append((cle, valeur))         # O(1) amorti ; O(n_bucket) si beaucoup de collisions
        self._taille += 1

    def obtenir(self, cle):
        bucket = self._buckets[self._index(cle)]
        for k, v in bucket:
            if k == cle:
                return v
        raise KeyError(cle)

    def supprimer(self, cle) -> None:
        bucket = self._buckets[self._index(cle)]
        for i, (k, _) in enumerate(bucket):
            if k == cle:
                del bucket[i]
                self._taille -= 1
                return
        raise KeyError(cle)

    def _redimensionner(self) -> None:
        anciens_buckets = self._buckets
        self._capacite *= 2
        self._buckets = [[] for _ in range(self._capacite)]
        self._taille = 0
        for bucket in anciens_buckets:
            for cle, valeur in bucket:
                self.inserer(cle, valeur)   # ré-hache tout dans la nouvelle capacité

    def __len__(self) -> int:
        return self._taille

t = TableHachageChainage()
t.inserer("a", 1); t.inserer("b", 2)
assert t.obtenir("a") == 1

# --- Adressage ouvert (open addressing) : sondage linéaire, sans listes par bucket ---
class TableHachageSondageLineaire:
    _VIDE = object()
    _SUPPRIME = object()

    def __init__(self, capacite: int = 16):
        self._capacite = capacite
        self._cles = [self._VIDE] * capacite
        self._valeurs = [None] * capacite
        self._taille = 0

    def inserer(self, cle, valeur) -> None:
        index = hash(cle) % self._capacite
        while self._cles[index] not in (self._VIDE, self._SUPPRIME):
            if self._cles[index] == cle:
                self._valeurs[index] = valeur
                return
            index = (index + 1) % self._capacite   # sonde la case suivante en cas de collision
        self._cles[index] = cle
        self._valeurs[index] = valeur
        self._taille += 1

    def obtenir(self, cle):
        index = hash(cle) % self._capacite
        depart = index
        while self._cles[index] is not self._VIDE:
            if self._cles[index] == cle:
                return self._valeurs[index]
            index = (index + 1) % self._capacite
            if index == depart:   # a fait le tour complet sans trouver la clé
                break
        raise KeyError(cle)

# Application classique : détecter les doublons / anagrammes avec un set/dict
def groupes_anagrammes(mots: list[str]) -> list[list[str]]:
    # O(n * k log k) où k = longueur moyenne des mots (tri de chaque mot comme clé de hachage)
    groupes: dict[str, list[str]] = {}
    for mot in mots:
        cle = "".join(sorted(mot))
        groupes.setdefault(cle, []).append(mot)
    return list(groupes.values())

assert sorted(groupes_anagrammes(["eat", "tea", "tan", "ate", "nat", "bat"]), key=len) == \
       sorted([["bat"], ["eat", "tea", "ate"], ["tan", "nat"]], key=len)