L'ensemble, dictionnaire sans valeurs

(a)

def ens_creer(m: int) -> list:
    return [[] for _ in range(m)]

def ens_ajouter(ensemble: list, cle) -> None:
    alv = ensemble[hash(cle) % len(ensemble)]
    if cle not in alv:
        alv.append(cle)

def ens_contient(ensemble: list, cle) -> bool:
    alv = ensemble[hash(cle) % len(ensemble)]
    return cle in alv

def premiere_repetition(t: list):
    # On crée un ensemble avec une taille suffisante pour éviter trop de collisions
    vus = ens_creer(2 * len(t))
    for x in t:
        if ens_contient(vus, x):
            return x
        ens_ajouter(vus, x)
    return None

(b) Pour une liste de taille $n=10^4$ sans doublons (pire cas) :

• La version avec liste de déjà-vus effectue environ $n^2/2\approx 5\times 10^7$ comparaisons de clés, prenant plusieurs secondes.
• La version avec table de hachage effectue $n$ opérations, chacune s'exécutant dans une alvéole presque vide (longueur $\le 1$ en moyenne). Le calcul se termine en quelques millisecondes, offrant un gain de performance d'un facteur 1000. (c) Un ensemble (set) est équivalent à un dictionnaire (dict) dont on ignore les valeurs pour ne conserver que les clés. Il partage la même structure mémoire et les mêmes règles d'immuabilité pour ses éléments, permettant de réaliser des tests d'appartenance instantanés en échange d'un stockage mémoire supplémentaire.