Tables de hachage

Une table de hachage implémente un dictionnaire en utilisant une fonction de hachage pour mapper les clés à des positions dans un tableau, permettant des opérations d'insertion, de suppression et de recherche en temps constant attendu lorsque les collisions sont bien gérées.

Definition

Une table de hachage est une structure de données qui stocke des paires clé-valeur dans un tableau, en utilisant une fonction de hachage pour calculer à partir de chaque clé un indice dans le tableau, avec un mécanisme de résolution des collisions pour gérer les clés distinctes qui hachent au même indice.

Scope

Ce sujet couvre les dictionnaires basés sur le hachage : les fonctions de hachage et leurs propriétés souhaitables, les stratégies de résolution des collisions (chaînage séparé et adressage ouvert), le facteur de charge et le redimensionnement, les cadres de hachage universel et parfait qui offrent des garanties prouvables, ainsi que les structures probabilistes connexes telles que les filtres de Bloom. Il exclut les structures de dictionnaire ordonnées, qui sont traitées dans le cadre des arbres de recherche.

Core questions

• Qu'est-ce qui caractérise une bonne fonction de hachage, et comment est-elle choisie pour répartir uniformément les clés ?
• Comment les collisions sont-elles résolues par chaînage ou adressage ouvert, et comment affectent-elles le coût ?
• Comment le facteur de charge régit-il le temps d'opération attendu et déclenche-t-il le redimensionnement ?
• Comment le hachage universel et parfait offre-t-il des garanties de performance prouvables ?
• Quand une structure probabiliste économe en espace comme un filtre de Bloom est-elle préférable à une table exacte ?

Key concepts

• fonction de hachage
• chaînage séparé
• adressage ouvert
• facteur de charge
• rehachage et redimensionnement
• hachage universel
• hachage parfait
• filtre de Bloom

Key theories

Hachage universel

En choisissant la fonction de hachage au hasard au sein d'une famille (universelle) soigneusement conçue, on peut garantir un faible nombre attendu de collisions pour tout ensemble fixe de clés, rendant ainsi improbables les entrées adverses du pire cas.

Résolution des collisions et facteur de charge

Le chaînage séparé stocke les clés en collision dans des listes par emplacement, tandis que l'adressage ouvert sonde des emplacements alternatifs ; le temps d'opération attendu est régi par le facteur de charge (entrées par emplacement), et les tables sont redimensionnées pour le maintenir borné.

Clinical relevance

Les tables de hachage figurent parmi les structures de données les plus utilisées en informatique : elles implémentent des dictionnaires et des ensembles dans les bibliothèques standard, alimentent l'indexation des bases de données et les caches en mémoire, prennent en charge les tables de symboles dans les compilateurs, et sont à la base de la déduplication et des tests d'appartenance. Les filtres de Bloom permettent de mettre à l'échelle les requêtes d'appartenance dans les bases de données et les réseaux où un stockage exact est irréalisable.

History

Le hachage a vu le jour dans les années 1950 avec des travaux attribués à Hans Peter Luhn chez IBM. Burton Bloom a introduit le filtre de Bloom économe en espace en 1970. Carter et Wegman ont formalisé le hachage universel, puis fortement universel, à la fin des années 1970 et au début des années 1980, conférant ainsi au hachage ses fondements théoriques rigoureux.

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

Pourquoi les opérations des tables de hachage sont-elles décrites comme O(1) attendu plutôt que O(1) garanti ?

Si de nombreuses clés entrent en collision, les opérations peuvent se dégrader vers O(n). Le temps constant est maintenu en espérance sous une bonne fonction de hachage et un facteur de charge borné ; le hachage universel rend un cas défavorable improbable, mais les garanties de pire cas nécessitent un hachage parfait ou d'autres techniques.

Qu'est-ce qu'un filtre de Bloom et en quoi diffère-t-il d'une table de hachage ?

Un filtre de Bloom est une structure probabiliste compacte qui teste l'appartenance à un ensemble en utilisant plusieurs fonctions de hachage sur un tableau de bits. Il peut produire des faux positifs mais jamais de faux négatifs, et il ne stocke aucune clé, échangeant l'exactitude contre d'importantes économies d'espace par rapport à une table de hachage.