Quelle est la différence entre une table de hachage et un dictionnaire Python ?

Un dictionnaire Python EST une implémentation de table de hachage. Le terme 'dictionnaire' est le nom du type en Python, tandis que 'table de hachage' décrit le principe algorithmique et la structure de données sous-jacente. Le dictionnaire Python est une table de hachage très optimisée.

Pourquoi une liste ne peut-elle pas être une clé de dictionnaire en Python ?

Parce que les clés d'une table de hachage doivent être immuables (hashables) pour garantir qu'elles produisent toujours le même indice de hachage. Une liste est mutable : on peut la modifier après sa création, ce qui changerait son hash et rendrait impossible sa localisation dans la table. Utilise un tuple à la place si tu as besoin d'une séquence comme clé.

Que se passe-t-il si la fonction de hachage est vraiment mauvaise (retourne toujours le même indice) ?

Les performances se dégradent énormément. Toutes les paires (clé, valeur) se retrouvent dans le même seau (la même liste). Les opérations d'accès, d'insertion et de suppression, qui devraient être en temps constant O(1), deviennent linéaires O(n) car il faut parcourir toute cette longue liste à chaque fois. C'est pourquoi une bonne répartition des indices est cruciale.

Comment Python gère-t-il l'agrandissement de la table (redimensionnement) ?

Lorsque le nombre d'éléments stockés dépasse un certain seuil (lié à la taille de la table, c'est le 'facteur de charge'), Python crée une nouvelle table plus grande (généralement le double de la taille). Il recalcule ensuite les indices de hachage de toutes les clés pour les replacer dans la nouvelle table. Cette opération, bien que coûteuse (O(n)), est rare, ce qui permet de conserver des performances moyennes excellentes.

Les tables de hachage : principe et implementation

Introduction : Pourquoi les tables de hachage sont-elles géniales ?

Imagine que tu doives retrouver le numéro de téléphone d'un ami dans un annuaire. Tu pourrais parcourir toutes les pages une par une (long et fastidieux), ou tu pourrais aller directement à la première lettre de son nom. Cette seconde méthode est bien plus rapide, n'est-ce pas ? C'est exactement l'idée derrière les tables de hachage (ou hash tables). En informatique, et particulièrement en NSI, c'est une structure de données fondamentale qui permet d'accéder à une information (une valeur) à partir d'une clé, en un temps quasi constant, quelle que soit la quantité de données stockées. En Python, le type dict (dictionnaire) est l'implémentation native d'une table de hachage. Dans cet article, on va démystifier cette structure, comprendre comment elle fonctionne sous le capot et voir comment l'implémenter toi-même.

Le principe fondamental : la fonction de hachage

Le cœur d'une table de hachage, c'est la fonction de hachage. Son rôle est de prendre une clé (qui peut être une chaîne de caractères, un nombre, un tuple, etc.) et de la transformer en un nombre entier : l'indice de hachage (ou hash code).

Déterminisme : Une même clé doit toujours produire le même indice.
Rapidité : Le calcul doit être très rapide.
Répartition uniforme : Les indices doivent être bien répartis pour éviter les accumulations.

En Python, la fonction native hash() fait ce travail. Par exemple, hash("NSI") retourne un grand nombre entier (qui peut varier d'une exécution à l'autre pour des raisons de sécurité, mais reste constant pendant l'exécution). Cet indice est ensuite utilisé pour déterminer où stocker la valeur associée dans un tableau (une liste en Python).

Un exemple simple de fonction de hachage

Prenons une fonction très basique pour une chaîne de caractères : on pourrait additionner les codes ASCII de chaque lettre. C'est une mauvaise fonction en pratique (car "ab" et "ba" donneraient le même résultat, c'est une collision), mais elle illustre le principe.

Le défi principal dans la conception d'une table de hachage est de gérer les collisions : lorsque deux clés différentes produisent le même indice de hachage. C'est inévitable si on a plus de clés possibles que d'indices disponibles.

Implémentation d'une table de hachage en Python

Voyons maintenant comment construire notre propre table de hachage simple, qu'on appellera HashTable. On va gérer les collisions par la méthode du chaînage : chaque case du tableau (appelée bucket ou seau) contient une liste de paires (clé, valeur).

La structure de base

On commence par initialiser un tableau de taille fixe (par exemple 8) rempli de listes vides.

Les opérations principales

Notre classe devra implémenter trois méthodes essentielles :

put(clé, valeur) : pour insérer ou mettre à jour une paire.
get(clé) : pour récupérer la valeur associée à une clé.
remove(clé) : pour supprimer une entrée.

Voici un squelette de code commenté :

class HashTable:
    def __init__(self, size=8):
        self.size = size
        self.table = [[] for _ in range(size)]  # Liste de listes vides

    def _hash(self, key):
        """Retourne l'indice dans le tableau pour une clé donnée."""
        # On utilise hash() et on s'assure que l'indice est dans les limites
        return hash(key) % self.size

    def put(self, key, value):
        """Insère ou met à jour la paire (clé, valeur)."""
        index = self._hash(key)
        bucket = self.table[index]
        # On parcourt le seau pour voir si la clé existe déjà
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Mise à jour
                return
        # Si la clé n'existe pas, on l'ajoute
        bucket.append((key, value))

    def get(self, key):
        """Récupère la valeur associée à la clé. Lève une erreur si non trouvée."""
        index = self._hash(key)
        bucket = self.table[index]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(f"Clé '{key}' non trouvée")

    def remove(self, key):
        """Supprime la paire associée à la clé."""
        index = self._hash(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return
        raise KeyError(f"Clé '{key}' non trouvée")

Cette implémentation, bien que simplifiée, capture l'essence d'une table de hachage. Dans la réalité, les dictionnaires Python sont bien plus optimisés (ils gèrent dynamiquement la taille du tableau pour garder un bon facteur de charge).

Complexité et applications pratiques

La puissance des tables de hachage réside dans leur complexité temporelle moyenne.

Insertion (put) : O(1) en moyenne, O(n) dans le pire des cas (si toutes les clés entrent en collision).
Accès (get) : O(1) en moyenne, O(n) dans le pire des cas.
Suppression (remove) : O(1) en moyenne, O(n) dans le pire des cas.

Ce temps constant moyen en fait un outil indispensable pour de nombreux algorithmes. Voici quelques applications concrètes que tu rencontreras en NSI et au-delà :

Caches : Mémoriser les résultats de calculs coûteux (mémoïsation).
Bases de données : Indexation rapide des enregistrements.
Vérification d'unicité : Supprimer les doublons d'une liste très efficacement.
Comptage de fréquences : Compter le nombre d'occurrences de chaque mot dans un texte.
Représentation de graphes : Liste d'adjacence où les sommets sont les clés.

Les dictionnaires Python : la table de hachage native

En Python, tu utilises déjà les tables de hachage tous les jours avec le type dict. C'est une implémentation hyper-optimisée. Quelques bonnes pratiques :

Les clés doivent être des types hashables (immutables comme les int, str, tuple). Une liste ne peut pas être une clé !
L'ordre d'insertion est préservé depuis Python 3.7.
Pour itérer efficacement, utilise les méthodes .keys(), .values() et .items().

Exemple d'utilisation avancée : comptage de mots.

texte = "le chat mange le poisson"
mots = texte.split()
compteur = {}
for mot in mots:
    compteur[mot] = compteur.get(mot, 0) + 1
print(compteur)  # Affiche {'le': 2, 'chat': 1, 'mange': 1, 'poisson': 1}

Conclusion

Les tables de hachage sont sans doute l'une des structures de données les plus élégantes et utiles en informatique. Comprendre leur principe, de la fonction de hachage à la gestion des collisions, est crucial pour ton parcours en NSI. Cela te permettra non seulement de mieux appréhender les dictionnaires Python, mais aussi de choisir la bonne structure de données pour résoudre un problème algorithmique de manière efficace. N'hésite pas à reprendre le code d'implémentation proposé, à le faire tourner et à l'enrichir (par exemple, en ajoutant un redimensionnement dynamique du tableau) pour solidifier ta compréhension.