Table de hachage

En informatique , une table de hachage est une structure de données qui implémente un tableau associatif , également appelé dictionnaire ou simplement table de hachage ; un tableau associatif est un type de données abstrait qui associe des clés à des valeurs . Une table de hachage utilise une fonction de hachage pour calculer un index , aussi appelé code de hachage , dans un tableau de compartiments ( ou emplacements) où la valeur recherchée peut être trouvée. Lors de la recherche, la clé est hachée et le hachage résultant indique où la valeur correspondante est stockée. Une table de hachage implémentée par une table de hachage est appelée table de hachage .

La plupart des tables de hachage utilisent une fonction de hachage imparfaite . Les collisions de hachage , où la fonction de hachage génère le même index pour plusieurs clés, doivent donc généralement être gérées. Parmi les stratégies courantes pour gérer les collisions de hachage, on trouve le chaînage, qui stocke plusieurs éléments dans le même emplacement à l'aide de listes chaînées, et l'adressage ouvert, qui recherche le prochain emplacement disponible selon une séquence de sondage.

Dans une table de hachage bien dimensionnée, la complexité temporelle moyenne de chaque recherche est indépendante du nombre d'éléments stockés dans la table. De nombreuses conceptions de tables de hachage permettent également l'insertion et la suppression arbitraires de paires clé-valeur , à un coût moyen constant amorti par opération.

Le hachage est un exemple de compromis espace-temps . Si la mémoire est infinie, la clé entière peut être utilisée directement comme index pour localiser sa valeur en un seul accès mémoire. En revanche, si le temps est infini, les valeurs peuvent être stockées sans tenir compte de leurs clés, et une recherche binaire ou linéaire peut être utilisée pour récupérer l'élément.

Dans de nombreuses situations, les tables de hachage s'avèrent en moyenne plus efficaces que les arbres de recherche ou toute autre structure de consultation tabulaire . C'est pourquoi elles sont largement utilisées dans de nombreux types de logiciels , notamment pour les tableaux associatifs , l'indexation de bases de données , les caches et les ensembles . De nombreux langages de programmation proposent des structures de tables de hachage intégrées, telles que les dictionnaires de Python , HashMap de Java , unordered_map de C++ et les maps de Go , qui permettent au programmeur de s'affranchir de la complexité du hachage.

L'idée du hachage est apparue indépendamment à différents endroits. En janvier 1953, Hans Peter Luhn rédigea une note interne d'IBM utilisant le hachage avec chaînage. Le premier exemple d' adressage ouvert fut proposé par A.D. Linh, s'appuyant sur la note de Luhn. À peu près à la même époque, Gene Amdahl , Elaine M. McGraw , Nathaniel Rochester et Arthur Samuel , d' IBM Research, implémentèrent le hachage pour l' assembleur IBM 701. L'adressage ouvert avec sondage linéaire est attribué à Amdahl, bien qu'Andrey Ershov ait eu indépendamment la même idée. Le terme « adressage ouvert » fut forgé par W. Wesley Peterson dans son article traitant du problème de la recherche dans les fichiers volumineux.

Le premier travail publié sur le hachage par chaînage est attribué à Arnold Dumey , qui a présenté l'idée d'utiliser le reste modulo un nombre premier comme fonction de hachage. Le terme « hachage » a été publié pour la première fois dans un article de Robert Morris. Une analyse théorique du sondage linéaire a été initialement proposée par Konheim et Weiss.

Un tableau associatif stocke un ensemble de paires (clé, valeur) et permet l'insertion, la suppression et la recherche, sous la contrainte d' unicité des clés . Dans l'implémentation par table de hachage des tableaux associatifs, un tableau de longueur n est partiellement rempli d' éléments, où n ≥ 1. Une clé est hachée à l'aide d'une fonction de hachage pour calculer un index dans la table de hachage, où i = 1. L'efficacité d'une table de hachage dépend du facteur de charge, défini comme le rapport entre le nombre d'éléments stockés et le nombre d'emplacements disponibles ; plus le facteur de charge est faible, plus les opérations sont rapides. À cet index, la clé et sa valeur associée sont stockées. Le stockage de la clé avec la valeur garantit que les recherches peuvent vérifier la clé à l'index pour récupérer la valeur correcte, même en cas de collisions. Sous des hypothèses raisonnables, les tables de hachage présentent de meilleures bornes de complexité temporelle pour les opérations de recherche, de suppression et d'insertion que les arbres binaires de recherche auto-équilibrés .

Les tables de hachage sont également couramment utilisées pour implémenter des ensembles, en omettant la valeur stockée pour chaque clé et en se contentant de vérifier si la clé est présente.

Le facteur de charge est une statistique critique d'une table de hachage et est défini comme suit : où

Les performances de la table de hachage se détériorent en fonction du facteur de charge . À la limite des grandes valeurs de et , chaque compartiment a statistiquement une distribution de Poisson avec une espérance pour une fonction de hachage idéalement aléatoire .

Le logiciel veille généralement à ce que le facteur de charge reste inférieur à une certaine constante . Cela contribue à maintenir de bonnes performances. Par conséquent, une approche courante consiste à redimensionner ou à « rehacher » la table de hachage chaque fois que le facteur de charge atteint cette constante. De même, la table peut également être redimensionnée si le facteur de charge descend en dessous de cette constante .

Avec des tables de hachage à chaînage séparé, chaque emplacement du tableau de compartiments stocke un pointeur vers une liste ou un tableau de données.

Les performances des tables de hachage à chaînage séparé diminuent progressivement à mesure que le facteur de charge augmente, et il n'existe aucun point fixe au-delà duquel un redimensionnement est absolument nécessaire.

Avec un chaînage séparé, la valeur qui donne les meilleures performances se situe généralement entre 1 et 3.

Avec l'adressage ouvert, chaque emplacement du tableau de compartiments contient exactement un élément. Par conséquent, une table de hachage à adressage ouvert ne peut pas avoir un facteur de charge supérieur à 1.

Les performances de l'adressage ouvert deviennent très mauvaises lorsque le facteur de charge approche 1.

Par conséquent, une table de hachage utilisant un adressage ouvert doit être redimensionnée ou rehachée si le facteur de charge approche 1.

Avec un adressage ouvert, les valeurs acceptables du facteur de charge maximal devraient se situer entre 0,6 et 0,75.

Une fonction de hachage associe l'ensemble des clés à des indices ou des emplacements dans la table, c'est-à-dire pour . Les implémentations classiques des fonctions de hachage reposent sur l' hypothèse d'un univers entier selon laquelle tous les éléments de la table proviennent de l'univers , où la longueur en bits de est limitée à la taille des mots de l' architecture informatique .

Une fonction de hachage est dite parfaite pour un ensemble donné si elle est injective sur cet ensemble , c'est-à-dire si chaque élément de cet ensemble est associé à une valeur différente de celui-ci . Une fonction de hachage parfaite peut être créée si toutes les clés sont connues à l'avance.

Les schémas de hachage utilisés dans l'hypothèse d'un univers entier comprennent le hachage par division, le hachage par multiplication, le hachage universel , le hachage parfait dynamique et le hachage parfait statique . Cependant, le hachage par division est le schéma le plus couramment utilisé.

Le schéma de hachage par division est le suivant : où est la valeur de hachage de et est la taille de la table.

Le schéma de hachage par multiplication est le suivant : Où est une constante réelle non entière et est la taille de la table. Un avantage du hachage par multiplication est que n'est pas critique. Bien que toute valeur produise une fonction de hachage, Donald Knuth suggère d'utiliser le nombre d'or .

On utilise généralement une chaîne de caractères comme clé pour la fonction de hachage. La troisième édition de * The C++ Programming Language* décrit une fonction de hachage simple où un entier non signé, initialement nul, est décalé d'un bit vers la gauche de manière itérative, puis combiné par un OU exclusif (XOR) avec la valeur entière du caractère suivant. La valeur de hachage obtenue est ensuite calculée modulo la taille de la table. Si le décalage vers la gauche n'est pas cyclique, la longueur de la chaîne doit être inférieure d'au moins huit bits à la taille de l'entier non signé. Une autre méthode courante pour hacher une chaîne de caractères en un entier consiste à utiliser une fonction de hachage polynomiale glissante .

La distribution uniforme des valeurs de hachage est une condition essentielle pour une fonction de hachage. Une distribution non uniforme augmente le nombre de collisions et le coût de leur résolution. L'uniformité est parfois difficile à garantir par conception, mais peut être évaluée empiriquement à l'aide de tests statistiques, par exemple le test du χ² de Pearson pour les distributions uniformes discrètes.

La distribution doit être uniforme uniquement pour les tailles de table rencontrées dans l'application. En particulier, si l'on utilise un redimensionnement dynamique avec un doublement et une division par deux exacts de la taille de la table, la fonction de hachage doit être uniforme uniquement lorsque la taille est une puissance de deux . Dans ce cas, l'index peut être calculé comme une plage de bits de la fonction de hachage. Par ailleurs, certains algorithmes de hachage préfèrent que la taille soit un nombre premier .

Pour les systèmes d'adressage ouverts , la fonction de hachage doit également éviter les séquences , c'est-à-dire l'association de deux clés ou plus à des emplacements consécutifs. De telles séquences peuvent faire exploser le coût de recherche, même si le facteur de charge est faible et les collisions peu fréquentes. Le hachage multiplicatif, très répandu, est réputé pour son comportement particulièrement problématique face aux séquences.

Le hachage K-indépendant permet de prouver qu'une fonction de hachage donnée ne présente pas de mauvais ensembles de clés pour un type de table de hachage donné. Plusieurs résultats de K-indépendance sont connus pour les schémas de résolution de collisions tels que le sondage linéaire et le hachage du coucou. Puisque la K-indépendance permet de prouver qu'une fonction de hachage fonctionne, on peut alors se concentrer sur la recherche de la fonction de hachage la plus rapide possible.

Un algorithme de recherche utilisant le hachage se compose de deux parties. La première consiste à calculer une fonction de hachage qui transforme la clé de recherche en un index de tableau . Idéalement, deux clés de recherche ne devraient pas correspondre au même index de tableau après hachage. Cependant, ce n'est pas toujours le cas et il est impossible de le garantir pour des données inconnues. La seconde partie de l'algorithme concerne donc la résolution des collisions. Les deux méthodes courantes de résolution des collisions sont le chaînage séparé et l'adressage ouvert.

Dans le chaînage séparé, le processus consiste à construire une liste chaînée avec une paire clé-valeur pour chaque index du tableau de recherche. Les éléments en collision sont chaînés par une seule liste chaînée, qui peut être parcourue pour accéder à l'élément avec une clé de recherche unique. La résolution des collisions par chaînage avec une liste chaînée est une méthode courante d'implémentation des tables de hachage. Soient et la table de hachage et le nœud respectivement, l'opération se déroule comme suit :

Chained-Hash-Insert( T , k ) insérer x en tête de la liste chaînée T [ h ( k )] Recherche de hachage enchaîné( T , k ) recherche un élément avec la clé k dans la liste chaînée T [ h ( k )] Chained-Hash-Delete( T , k ) supprimer x de la liste chaînée T [ h ( k )] 

Si l'élément est comparable numériquement ou lexicalement , et inséré dans la liste en conservant l' ordre total , les recherches infructueuses s'arrêtent plus rapidement.

Si les clés sont ordonnées , il pourrait être efficace d'utiliser des concepts « auto-organisés » tels qu'un arbre de recherche binaire auto-équilibré , grâce auquel le pire cas théorique pourrait être réduit à , bien que cela introduit des complexités supplémentaires.

Dans le hachage parfait dynamique , des tables de hachage à deux niveaux sont utilisées pour réduire la complexité de recherche et la garantir dans le pire des cas. Dans cette technique, les compartiments d' entrées sont organisés sous forme de tables de hachage parfaites dont les emplacements assurent un temps de recherche constant dans le pire des cas et un temps d'insertion amorti faible. Une étude montre que le chaînage séparé basé sur un tableau est 97 % plus performant que la méthode standard des listes chaînées sous forte charge.

Des techniques telles que l'utilisation d'un arbre de fusion pour chaque compartiment permettent également d'obtenir un temps constant pour toutes les opérations avec une forte probabilité.

Dans une implémentation de chaînage séparé, la liste chaînée peut ne pas être optimisée pour le cache en raison de la localité spatiale ( localité de référence ) lorsque les nœuds de la liste sont dispersés en mémoire ; par conséquent, le parcours de la liste lors des opérations d'insertion et de recherche peut entraîner des inefficacités du cache du processeur .

Dans les variantes de résolution de collisions optimisées pour le cache par chaînage séparé, un tableau dynamique , jugé plus adapté au cache, est utilisé à la place d'une liste chaînée ou d'arbres binaires de recherche auto-équilibrés. En effet, le modèle d' allocation contiguë du tableau peut être exploité par des préchargeurs de cache matériel , tels que le tampon de traduction d'adresses mémoire (TLB) , ce qui réduit le temps d'accès et la consommation de mémoire.

L'adressage ouvert est une autre technique de résolution des collisions dans laquelle chaque enregistrement d'entrée est stocké dans le tableau de compartiments lui-même, et la résolution du hachage est effectuée par sondage . Lorsqu'une nouvelle entrée doit être insérée, les compartiments sont examinés, en commençant par l'emplacement de hachage et en poursuivant selon une séquence de sondage , jusqu'à ce qu'un emplacement libre soit trouvé. Lors de la recherche d'une entrée, les compartiments sont parcourus dans le même ordre, jusqu'à ce que l'enregistrement cible soit trouvé ou qu'un emplacement libre du tableau soit trouvé, ce qui indique un échec de la recherche.

Les séquences de sondes bien connues comprennent :

• Sondage linéaire , dans lequel l'intervalle entre les sondages est fixe (généralement 1).
• Sondage quadratique , dans lequel l'intervalle entre les sondages est augmenté en ajoutant les sorties successives d'un polynôme quadratique à la valeur donnée par le calcul de hachage initial.
• Double hachage , dans lequel l'intervalle entre les sondes est calculé par une fonction de hachage secondaire.

Les performances de l'adressage ouvert peuvent être inférieures à celles du chaînage séparé, car la séquence de sondage augmente lorsque le facteur de charge approche 1. Le sondage entraîne une boucle infinie si le facteur de charge atteint 1, dans le cas d'une table complètement remplie. Le coût moyen du sondage linéaire dépend de la capacité de la fonction de hachage à répartir uniformément les éléments dans la table afin d'éviter les séquences , car la formation de séquences augmenterait le temps de recherche.

Étant donné que les emplacements sont situés dans des emplacements successifs, le sondage linéaire pourrait conduire à une meilleure utilisation du cache du processeur en raison de la localité des références, ce qui entraîne une latence mémoire réduite .

Le hachage coalescent est une technique hybride combinant le chaînage séparé et l'adressage ouvert, dans laquelle les compartiments ou nœuds sont liés au sein de la table. Cet algorithme est parfaitement adapté à une allocation de mémoire fixe . En cas de collision, l'emplacement vide le plus grand de la table de hachage est identifié, puis la valeur en collision y est insérée. Le compartiment est également lié à l'emplacement du nœud inséré, qui contient son adresse de hachage en collision.

Le hachage coucou est une technique de résolution de collisions à adressage ouvert qui garantit une complexité de recherche dans le pire des cas et un temps amorti constant pour les insertions. La collision est résolue grâce à deux tables de hachage, chacune possédant sa propre fonction de hachage. L'emplacement en collision est remplacé par l'élément donné, et l'élément occupé est déplacé dans l'autre table. Le processus se poursuit jusqu'à ce que chaque clé ait sa place dans les emplacements vides des tables. Si la procédure entre dans une boucle infinie (détectée par un compteur de boucle à seuil), les deux tables de hachage sont réinitialisées avec de nouvelles fonctions de hachage et la procédure continue.

Le hachage Hopscotch est un algorithme d'adressage ouvert qui combine les éléments du hachage Cuckoo , du sondage linéaire et du chaînage grâce à la notion de voisinage de seaux — les seaux adjacents à un seal occupé donné, également appelés seaux « virtuels ». Cet algorithme est conçu pour offrir de meilleures performances lorsque le taux de remplissage de la table de hachage dépasse 90 % ; il offre également un débit élevé en environnement concurrent , et est donc bien adapté à la mise en œuvre de tables de hachage concurrentes redimensionnables . La caractéristique de voisinage du hachage Hopscotch garantit que le coût de recherche de l'élément souhaité dans n'importe quel seal du voisinage est très proche du coût de sa recherche dans le seal lui-même ; l'algorithme tente d'introduire un élément dans son voisinage — quitte à déplacer d'autres éléments.

Chaque compartiment de la table de hachage inclut une « information de saut » supplémentaire : un tableau de H bits indiquant la distance relative de l'élément initialement haché dans le compartiment virtuel courant, parmi les H − 1 entrées. Soient et la clé à insérer et le compartiment dans lequel la clé est hachée, respectivement ; plusieurs cas interviennent dans la procédure d'insertion afin de garantir la propriété de voisinage de l'algorithme : si est vide, l'élément est inséré et le bit le plus à gauche du tableau est mis à 1 ; si n'est pas vide, un sondage linéaire est utilisé pour trouver un emplacement vide dans la table, le tableau du compartiment est mis à jour, puis l'insertion est effectuée ; si l'emplacement vide n'est pas dans la plage du voisinage, c'est -à-dire H − 1, un échange et une manipulation du tableau de bits d'information de saut de chaque compartiment sont ensuite effectués conformément à ses propriétés d'invariance de voisinage .

Le hachage Robin Hood est un algorithme de résolution de collisions basé sur un adressage ouvert ; les collisions sont résolues en privilégiant le déplacement de l’élément le plus éloigné (ou ayant la plus grande longueur de séquence de sondage [PSL]) de son emplacement d’origine, c’est-à-dire le compartiment dans lequel l’élément a été haché. Il tire son nom de Robin des Bois , un héros mythique hors-la-loi qui volait aux riches pour donner aux pauvres.

Bien que le hachage Robin Hood ne modifie pas le coût de recherche théorique , il affecte significativement la variance de la distribution des éléments dans les compartiments , c'est-à-dire la formation de longues séquences dans la table de hachage . Chaque nœud de la table de hachage utilisant le hachage Robin Hood doit être augmenté pour stocker une valeur PSL supplémentaire [ Soit la clé à insérer, la longueur PSL (incrémentale) de , la table de hachage et l'index, la procédure d'insertion est la suivante :

• Si : l'itération passe au compartiment suivant sans tenter de sondage externe.
• Si : insérer l'élément dans le seau ; échanger avec — le laisser tel quel ; continuer la sonde à partir du ème seau à insérer ; répéter la procédure jusqu'à ce que chaque élément soit inséré.$\backslash \; T[j]\{.\}\{\; ext\{pslx.\text{psl}>T\left[j\right].\text{psl}$\ T[j]{.}{ ext{psl

Les insertions répétées augmentent le nombre d'entrées dans une table de hachage, ce qui accroît le facteur de charge. Afin de maintenir les performances amorties des opérations de recherche et d'insertion, la taille de la table de hachage est redimensionnée dynamiquement et ses éléments sont réattribués aux compartiments de la nouvelle table . En effet, la copie directe des éléments est impossible, car des tailles de table différentes entraînent des valeurs de hachage différentes en raison de l'opération modulo . Si une table de hachage devient « trop vide » après la suppression d'éléments, un redimensionnement peut être effectué pour éviter une consommation excessive de mémoire .

En général, une nouvelle table de hachage de taille double de celle de la table originale est allouée de manière privée, et chaque élément de la table originale est déplacé vers la nouvelle table en calculant sa valeur de hachage, puis en procédant à l'insertion. Le rehachage est simple, mais coûteux en calcul.

Certaines implémentations de tables de hachage, notamment dans les systèmes temps réel , ne peuvent se permettre d'agrandir la table de hachage d'un seul coup, car cela risque d'interrompre les opérations critiques. Si le redimensionnement dynamique est inévitable, une solution consiste à l'effectuer progressivement afin d'éviter une brève interruption de la mémoire (généralement à 50 % de la nouvelle taille de la table) lors du rehachage, et d'éviter la fragmentation de la mémoire qui déclenche une compaction du tas due à la libération de grands blocs de mémoire par l'ancienne table de hachage. Dans ce cas, l'opération de rehachage est réalisée de manière incrémentale en étendant le bloc de mémoire précédemment alloué à l'ancienne table de hachage , de sorte que les compartiments de la table de hachage restent inchangés. Une approche courante pour le rehachage amorti consiste à maintenir deux fonctions de hachage . Le processus de réorganisation des éléments d'un bucket selon la nouvelle fonction de hachage est appelé nettoyage . Il est implémenté à l'aide du modèle de conception Commande en encapsulant les opérations telles que et par le biais d'un wrapper, de sorte que chaque élément du bucket soit réorganisé. La procédure est la suivante :

• Seau propre .
• Seau propre .
• La commande est exécutée.

Le hachage linéaire est une implémentation de la table de hachage qui permet des agrandissements ou des réductions dynamiques de la table, un compartiment à la fois.

Les performances d'une table de hachage dépendent de la capacité de sa fonction de hachage à générer des nombres quasi-aléatoires ( ) pour les entrées de la table, où , et désignent respectivement la clé, le nombre de compartiments et la fonction de hachage telle que . Si la fonction de hachage génère les mêmes nombres pour des clés distinctes ( ), cela entraîne une collision , qui est gérée de diverses manières. La complexité temporelle constante ( ) de l'opération dans une table de hachage est présupposée sous la condition que la fonction de hachage ne génère pas d'indices en collision ; ainsi, les performances de la table de hachage sont directement proportionnelles à la capacité de la fonction de hachage choisie à disperser les indices. Cependant, la construction d'une telle fonction de hachage est pratiquement irréalisable ; de ce fait, les implémentations dépendent de techniques de résolution de collisions spécifiques à chaque cas pour obtenir de meilleures performances.

Les meilleures performances sont obtenues lorsque la fonction de hachage distribue uniformément les éléments de l'univers et que les éléments stockés dans la table sont tirés aléatoirement de cet univers. Dans ce cas, avec le hachage par chaînage, le temps moyen pour une recherche réussie est de O(n²) et le temps moyen pour une recherche infructueuse est de O(n²) .

Les tables de hachage sont couramment utilisées pour implémenter de nombreux types de tables en mémoire. Elles sont utilisées pour implémenter des tableaux associatifs .

Les tables de hachage peuvent également être utilisées comme structures de données sur disque et comme index de base de données (comme dans dbm ), bien que les arbres B soient plus populaires dans ces applications.

Les tables de hachage peuvent servir à implémenter des caches , des tables de données auxiliaires permettant d'accélérer l'accès aux données stockées principalement sur des supports plus lents. Dans ce cas, les collisions de hachage sont gérées en supprimant l'une des deux entrées en conflit ; généralement, l'ancien élément stocké dans la table est effacé et remplacé par le nouveau, de sorte que chaque élément de la table possède une valeur de hachage unique.

Les tables de hachage peuvent être utilisées dans l'implémentation de la structure de données d'ensemble , qui peut stocker des valeurs uniques sans ordre particulier ; l'ensemble est généralement utilisé pour tester l'appartenance d'une valeur à la collection, plutôt que pour la récupération d'éléments.

Une table de transposition vers une table de hachage complexe qui stocke des informations sur chaque section qui a été recherchée.

De nombreux langages de programmation offrent des fonctionnalités de table de hachage, soit sous forme de tableaux associatifs intégrés, soit sous forme de modules de bibliothèque standard .

• En JavaScript , un « objet » est une collection mutable de paires clé-valeur (appelées « propriétés »), où chaque clé est soit une chaîne de caractères, soit un « symbole » unique garanti ; toute autre valeur, lorsqu’elle est utilisée comme clé, est d’abord convertie en chaîne de caractères. Hormis les sept types de données primitifs, toute valeur en JavaScript est un objet. ECMAScript 2015 a également ajouté la Mapstructure de données `Object`, qui accepte des valeurs arbitraires comme clés.
• C++11 inclut unordered_mapdans sa bibliothèque standard des fonctions permettant de stocker des clés et des valeurs de types arbitraires .
• L'implémentation intégrée de Gomap représente un type map sous la forme d'un type , qui est souvent (mais pas nécessairement) une table de hachage.
• Le langage de programmation Java comprend les collections génériquesHashSet `map` HashMap, LinkedHashSet`filter` et `map` . LinkedHashMap
• Python implémente dictune table de hachage intégrée sous la forme d'un type .
• Ruby utilise Hashle modèle d'adressage ouvert à partir de Ruby 2.4.
• Le langage de programmation Rust inclut HashMap, HashSetdans le cadre de la bibliothèque standard Rust.
• La bibliothèque standard .NET inclut HashSetet Dictionary, elle peut donc être utilisée à partir de langages tels que C# et VB.NET .