Table de hachage Hash table
Structure de données qui associe des clés à des valeurs en temps O(1) amorti — le bloc de base derrière dict/HashMap/object dans presque tous les langages.
Une fonction de hachage transforme une clé en index de bucket. Les collisions se gèrent par chaînage (une liste chaînée par bucket — comportement par défaut de HashMap en Java) ou par adressage ouvert (sondage linéaire, sondage quadratique — dict Python, map Go, HashBrown de Rust). Redimensionnement quand le facteur de charge dépasse ~0,75.
Pire cas en O(n) avec une mauvaise fonction de hachage. Les attaques HashDoS (2011) ont forcé tous les langages à adopter des fonctions de hachage à graine aléatoire (SipHash). Le hachage Robin Hood et le hachage hopscotch sont des variantes modernes offrant une meilleure localité de cache.