Une table de hachage est une structure de données qui associe des clés à des valeurs en utilisant une fonction de hachage pour calculer un index dans un tableau. Elle permet d'accéder, d'insérer et de supprimer des éléments en temps constant O(1) en moyenne.
Utilité et avantages
Résout le problème de recherche rapide dans de grandes collections de données. Contrairement aux tableaux où il faut parcourir séquentiellement, ou aux arbres qui nécessitent plusieurs comparaisons, la table de hachage calcule directement la position de stockage. Elle offre des performances constantes même avec des millions d'éléments, ce qui la rend particulièrement adaptée aux caches, bases de données et systèmes nécessitant des accès fréquents.
Exemple d'utilisation
Un système de gestion d'utilisateurs où chaque email (clé) est associé à un profil utilisateur (valeur). Quand un utilisateur se connecte avec "john@email.com", la fonction de hachage calcule instantanément où trouver ses informations sans parcourir toute la base d'utilisateurs. Également utilisée pour les caches web, les index de bases de données, ou le stockage de configurations d'applications.
Implémentation
# Table de hachage simple avec gestion des collisions
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # Chaînage pour les collisions
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self._hash(key)
# Recherche si la clé existe déjà
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
raise KeyError(key)Contexte technique
Présente nativement dans la plupart des langages : dict en Python, Map en JavaScript, HashMap en Java, unordered_map en C++, Hash en Ruby. Les implémentations varient dans leur gestion des collisions (chaînage, adressage ouvert), leurs stratégies de redimensionnement et leurs fonctions de hachage. Certaines garantissent l'ordre d'insertion (LinkedHashMap), d'autres optimisent la concurrence (ConcurrentHashMap).
Termes liés: Fonction de hachage, Collision, Dictionnaire, Map
