Hash Table

Une table de hachage associe des clés à un tableau de compartiments via une fonction de hachage, offrant recherche/insertion/suppression en O(1) en moyenne ; c'est l'une des structures de données les plus utilisées.

Objectif

Fournir un accès clé-valeur en temps constant moyen, implémentant efficacement dictionnaires et ensembles.

Mécanisme

hash(clé) % capacité localise le compartiment. Gestion des collisions : chaînage séparé (le compartiment contient une liste) ou adressage ouvert (sondage du prochain emplacement libre). Facteur de charge = éléments / compartiments ; dépasser le seuil déclenche redimensionnement et rehachage. Une bonne fonction de hachage répartit les clés uniformément.

Cas d’usage

Implémentations de dictionnaires et maps
Index de bases de données
Caches (LRU)
Déduplication et ensembles

Exemples

entrée

{"name":"Ada"} → hash("name")=5

Output

Value stored in bucket 5

O(1) on average

Erreurs courantes

A poorly distributed hash function causes collision pile-ups: Use a high-quality hash function and a suitable load factor

Termes associés

Un filtre de Bloom approxime l'appartenance à un ensemble avec k fonctions de hachage et un tableau de bits, offrant une efficacité spatiale au prix d'un taux de faux positifs.

La notation grand O décrit la borne supérieure asymptotique d'une fonction, utilisée pour analyser la complexité temporelle/spatiale des algorithmes en ignorant les constantes et les termes d'ordre inférieur.

Outils associés

Djb2 — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

Sdbm — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

Zobrist — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

Pearson — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

Elfhash — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

References