Implémentation de Tables de Hachage avec Chaînage

1. Préparation : Simulation manuelle

Avant de nous lancer dans le code, assurons-nous que la mécanique du chaînage est parfaitement claire. Une simulation manuelle est un excellent exercice pour cela.

Considérez l'exercice suivant, inspiré d'une ressource que nous allons utiliser.
Scénario :

• Vous disposez d'une table de hachage de taille $M=5$.
• Votre fonction de hachage est $h(k)=k(\mathrm{mod}5)$.
• Vous devez insérer les clés suivantes dans l'ordre : 7, 12, 17, 22, 3, 8.

Pour chaque clé, calculez l'indice et décrivez l'état de la table (quels éléments se trouvent dans chaque "seau" ou liste chaînée).

Prenez un instant pour le faire sur papier. Vous pouvez ensuite comparer votre résultat avec la solution ci-dessous.

2. Architecture de notre table de hachage

Pour une implémentation propre, nous allons utiliser une approche orientée objet. Nous aurons besoin de deux classes :

1. Une classe Node pour représenter les maillons de nos listes chaînées. Chaque nœud stockera une paire (clé, valeur) et un pointeur next.
2. Une classe HashTable qui encapsulera la logique principale : le tableau sous-jacent (une liste Python), la fonction de hachage, et les méthodes insert, search et remove.

L'article suivant sera notre guide principal pour cette implémentation. Il détaille la structure et la logique de chaque méthode de manière très claire.

3. Implémentation des opérations

Basé sur la lecture précédente, décomposons la logique de chaque méthode.

Initialisation et Hachage

Le constructeur de notre classe HashTable doit initialiser un tableau (une liste Python) d'une capacité donnée, rempli de None pour indiquer que tous les seaux sont initialement vides.

class HashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.table = [None] * capacity

La fonction de hachage privée, _hash, utilisera la fonction native hash() de Python, qui gère différents types de données, et appliquera l'opération modulo pour s'assurer que l'indice est bien dans les bornes de notre tableau.

    def _hash(self, key):
        return hash(key) % self.capacity

Insertion (insert)

L'algorithme d'insertion est le suivant :

1. Calculer l'indice index = self._hash(key).
2. Accéder au seau self.table[index].
3. Cas 1 : Le seau est vide (None). On crée un nouveau Node(key, value) et on le place à cet indice. On incrémente la taille.
4. Cas 2 : Le seau contient déjà une liste chaînée (collision).
   a. On parcourt la liste chaînée à partir de la tête.
   b. À chaque nœud, on vérifie si sa clé est égale à la key que l'on souhaite insérer. Si oui, cela signifie que nous mettons à jour une valeur existante. On modifie la value du nœud et on arrête l'opération.
   c. Si on atteint la fin de la liste sans trouver la clé, cela signifie que c'est une nouvelle clé qui a collisionné. On crée un nouveau Node(key, value) et on l'insère en tête de la liste chaînée. (L'insertion en tête est en $O(1)$). On incrémente la taille.

Recherche (search)

L'algorithme de recherche est plus simple :

1. Calculer l'indice index = self._hash(key).
2. Accéder au seau self.table[index].
3. Si le seau est vide (None), la clé n'existe pas. On retourne None (ou on lève une exception).
4. Si le seau contient une liste, on la parcourt. Pour chaque nœud, on compare sa clé avec la key recherchée.
5. Si on trouve une correspondance, on retourne la value associée.
6. Si on atteint la fin de la liste sans trouver la clé, elle n'est pas dans la table.

Suppression (remove)

La suppression est l'opération la plus délicate, car elle requiert une manipulation des pointeurs de la liste chaînée.

1. Calculer l'indice index = self._hash(key).
2. Accéder au seau self.table[index].
3. On parcourt la liste chaînée en gardant une référence au nœud current et au nœud previous.
4. À chaque nœud, on compare sa clé avec la key à supprimer.
5. Si on trouve la clé :
   a. Si le nœud à supprimer est la tête de la liste (previous est None). On met à jour la tête de la liste dans le tableau principal : self.table[index] = current.next.
   b. Sinon (le nœud est au milieu ou à la fin). On "court-circuite" le nœud current en faisant pointer previous.next vers current.next.
   c. On décrémente la taille et on arrête l'opération.
6. Si la fin de la liste est atteinte sans trouver la clé, on ne fait rien (ou on lève une exception).

4. Exercice de programmation

Il est temps de mettre tout cela en code. Voici le squelette de nos classes. Votre tâche est de compléter les méthodes insert, search, et remove dans la classe HashTable.

class Node:
    """Nœud pour la liste chaînée dans chaque seau."""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashTable:
    """Table de hachage avec résolution des collisions par chaînage séparé."""
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.size = 0
        self.table = [None] * capacity

    def _hash(self, key):
        """Calcule l'indice pour une clé donnée."""
        return hash(key) % self.capacity

    def insert(self, key, value):
        """Insère une paire (clé, valeur) ou met à jour la valeur si la clé existe."""



        # VOTRE CODE ICI
        # 1. Calculer l'indice
        # 2. Vérifier si le seau est vide
        # 3. Sinon, parcourir la liste pour trouver la clé (mise à jour)
        #    ou l'ajouter en tête (nouvelle insertion)
        pass

    def search(self, key):
        """Recherche une clé et retourne sa valeur, ou None si non trouvée."""



        # VOTRE CODE ICI
        # 1. Calculer l'indice
        # 2. Parcourir la liste chaînée à cet indice
        # 3. Retourner la valeur si la clé est trouvée
        pass

    def remove(self, key):
        """Supprime une clé de la table."""



        # VOTRE CODE ICI
        # 1. Calculer l'indice
        # 2. Parcourir la liste avec des pointeurs 'previous' et 'current'
        # 3. Gérer le cas où la clé est en tête
        # 4. Gérer le cas où la clé est ailleurs dans la liste
        pass

    def __str__(self):
        """Affichage pour le débogage."""
        elements = []
        for i in range(self.capacity):
            current = self.table[i]
            while current:
                elements.append((current.key, current.value))
                current = current.next
        return str(elements)




# Test
ht = HashTable()
ht.insert("France", "Paris")
ht.insert("Japon", "Tokyo")
ht.insert("Espagne", "Madrid") # Potentielle collision selon la fonction de hachage

print(ht)
print(f"Capitale du Japon : {ht.search('Japon')}")

ht.insert("Japon", "Kyoto") # Mise à jour
print(f"Nouvelle capitale du Japon : {ht.search('Japon')}")

ht.remove("France")
print(f"Après suppression de la France : {ht}")

Prenez le temps nécessaire pour implémenter ces méthodes. N'hésitez pas à vous référer à l'article de GeeksforGeeks (LINK) si vous êtes bloqué sur la logique de manipulation des pointeurs.

class Node:
    """Nœud pour la liste chaînée dans chaque seau."""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashTable:
    """Table de hachage avec résolution des collisions par chaînage séparé."""
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.size = 0
        self.table = [None] * capacity

    def _hash(self, key):
        """Calcule l'indice pour une clé donnée."""
        return hash(key) % self.capacity

    def insert(self, key, value):
        """Insère une paire (clé, valeur) ou met à jour la valeur si la clé existe."""
        index = self._hash(key)
        
        current = self.table[index]
        while current:
            if current.key == key:
                current.value = value
                return
            current = current.next
        



        # Si la clé n'a pas été trouvée, on insère un nouveau noeud en tête
        new_node = Node(key, value)
        new_node.next = self.table[index]
        self.table[index] = new_node
        self.size += 1

    def search(self, key):
        """Recherche une clé et retourne sa valeur, ou None si non trouvée."""
        index = self._hash(key)
        current = self.table[index]
        
        while current:
            if current.key == key:
                return current.value
            current = current.next
        
        return None

    def remove(self, key):
        """Supprime une clé de la table."""
        index = self._hash(key)
        
        previous = None
        current = self.table[index]
        
        while current:
            if current.key == key:
                if previous:
                    previous.next = current.next
                else: # Le noeud à supprimer est la tête
                    self.table[index] = current.next
                self.size -= 1
                return
            previous = current
            current = current.next
            



        # Si on arrive ici, la clé n'a pas été trouvée. On peut lever une exception.
        raise KeyError(f"Key '{key}' not found.")

    def __str__(self):
        """Affichage pour le débogage."""
        elements = []
        for i in range(self.capacity):
            current = self.table[i]
            if current:
                chain_str = []
                while current:
                    chain_str.append(f"({current.key}: {current.value})")
                    current = current.next
                elements.append(f"Seau {i}: -> " + " -> ".join(chain_str))
        return "\n".join(elements)




# Test
ht = HashTable()
ht.insert("France", "Paris")
ht.insert("Japon", "Tokyo")
ht.insert("Allemagne", "Berlin") # Peut entrer en collision avec Japon
ht.insert("Espagne", "Madrid")

print(ht)
print("-" * 20)
print(f"Capitale de l'Allemagne : {ht.search('Allemagne')}")

ht.insert("Japon", "Kyoto") # Mise à jour
print(f"Nouvelle capitale du Japon : {ht.search('Japon')}")
print("-" * 20)

ht.remove("Allemagne")
print(f"Après suppression de l'Allemagne :\n{ht}")

Conclusion

Félicitations ! Vous avez implémenté une table de hachage fonctionnelle à partir de zéro. Cette structure est au cœur de nombreux algorithmes et systèmes performants, et sa compréhension en profondeur est un atout majeur.

Les points clés de notre implémentation sont :

• Une classe Node pour construire les chaînes.
• Une classe HashTable qui orchestre un tableau de "seaux".
• Les méthodes insert, search et remove qui opèrent toutes en deux temps :
  1. Calcul du hachage pour trouver le bon seau en $O(1)$.
  2. Parcours de la liste chaînée dans ce seau, dont la durée dépend de la longueur de la chaîne.

Notre implémentation a une capacité fixe. Dans un système réel, si le nombre d'éléments augmente trop, les chaînes deviennent longues et les performances se dégradent. La solution est de redimensionner la table lorsque le facteur de charge $\alpha =N/M$ dépasse un certain seuil.

Cette opération de redimensionnement est coûteuse ponctuellement, mais sa fréquence est faible. Dans notre prochaine leçon, nous aborderons la complexité amortie, l'outil mathématique essentiel pour analyser formellement le coût moyen d'opérations comme celle-ci dans des structures de données dynamiques, comme le tableau dynamique ou notre future table de hachage redimensionnable.