PARTIE 5 : TABLES DE HACHAGE

TP 16 : Introduction

Une Table de Hachage (Hash Table) est une structure de données qui associe des clés à des valeurs. Elle permet un accès très rapide, idéalement en O(1).

Fonction de Hachage

C’est une fonction mathématique qui convertit une clé (ex: “Alice”) en un index (entier) pour savoir où stocker la donnée dans un tableau.

Index = hash(Clé) % Taille_Tableau

Collisions

Deux clés différentes peuvent donner le même index. C’est une collision. Exemple : hash("Alice") = 5 et hash("Bob") = 5.

Gestion par Chaînage : Chaque case du tableau ne contient pas juste une valeur, mais une Liste Chaînée de valeurs. Si collision, on ajoute à la liste de cette case.

Schéma :

TP 16 : Exercice Bonus

Implémentez une table de hachage simple de taille 10 avec gestion des collisions par chaînage. Fonctions : insert(key, value) et search(key).