Tables de hachage

#Tables de hachageCopier le lien

Fonctions de hachage, collisions, sondage/chaînage, et complexités moyennes/pires cas.

#Animation interactiveCopier le lien

Voici une animation qui illustre le fonctionnement d'une table de hachage avec gestion des collisions par adressage ouvert :

#Exemple (Python — dictionnaires)Copier le lien

#Exercice : Implémentation d'une table de hachageCopier le lien

Implémentez une table de hachage simple en Python avec gestion des collisions par chaînage.

#InstructionsCopier le lien

1. Créez une classe HashTable avec une taille fixe.
2. Implémentez une fonction de hachage simple (par exemple, modulo la taille de la table).
3. Utilisez des listes pour gérer les collisions (chaînage).
4. Implémentez les méthodes put(key, value), get(key) et remove(key).

#Exemple de codeCopier le lien

1class HashTable:2    def __init__(self, size=10):3        self.size = size4        self.table = [[] for _ in range(size)]5    6    def _hash(self, key):7        return hash(key) % self.size8    9    def put(self, key, value):10        index = self._hash(key)11        bucket = self.table[index]12        13        # Vérifier si la clé existe déjà14        for i, (k, v) in enumerate(bucket):