Table de hachage

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une table de hachage est, en informatique, une structure de données qui permet une association clé-élément, c'est-à-dire une implémentation du type abstrait tableau associatif ; en particulier d'une table des symboles lorsque les clés sont des chaînes.

On accède à chaque élément de la table via sa clé. Il s'agit d'un tableau ne comportant pas d'ordre (un tableau est indexé par des entiers). L'accès à un élément se fait en transformant la clé en une valeur de hachage par l'intermédiaire d'une fonction de hachage. Le hachage est un nombre qui permet la localisation des éléments dans le tableau, typiquement le hachage est l'index de l'élément dans le tableau. Une case dans le tableau est appelée « alvéole ».

Un annuaire représenté comme une table de hachage.

Le fait de créer une valeur de hashage à partir d'une clé peut engendrer un problème de « collision », c’est-à-dire que deux clés différentes, voire davantage, pourront se retrouver associées à la même valeur de hashage et donc à la même case dans le « tableau » (la fonction n'est pas injective). Pour diminuer les risques de collisions, il faut donc premièrement choisir avec soin sa fonction de hachage. Ensuite, un mécanisme de résolution des collisions sera à implémenter.

Tout comme les tableaux ordinaires, les tables de hachage permettent un accès en O(1) en moyenne, quel que soit le nombre d'éléments dans la table. Toutefois, comme plusieurs données peuvent se trouver dans une même case, le temps d'accès dans le pire des cas peut être de O(n). Comparées aux autres tableaux associatifs, les tables de hachage sont surtout utiles lorsque le nombre d'entrées est très important [réf. nécessaire].

La position des éléments dans une table de hachage est pseudo-aléatoire. Cette structure n'est donc pas adaptée au feuilletage (browsing) de données voisines. Des types de structures de données comme les arbres équilibrés, généralement plus lents (en O(log n)) et un peu plus complexes à implémenter, maintiennent une structure ordonnée.

Choix d'une bonne fonction de hachage[modifier | modifier le code]

Une bonne fonction de hachage est utile aux performances, surtout si les collisions sont résolues ensuite par des explorations séquentielles : toute fonction de hachage provoquant beaucoup de collisions (par exemple : premier caractère de la clé) ralentira nettement la recherche. Un bon compromis est à trouver entre :

  • rapidité de la fonction hachage
  • taille à réserver pour l'espace de hachage
  • réduction du risque des collisions

Un ou exclusif de toutes les lettres d'une clé fournissait souvent un compromis acceptable dans l'écriture de compilateurs au début des années 1960.

Larry Wall utilisa pour implémenter son langage Perl une fonction permettant de doubler autant de fois que nécessaire avec l'extension du nombre de clés l'espace de hachage sans autre recalcul de ces clés qu'une translation binaire.

Le calcul du hachage se fait parfois en deux temps :

  1. Une fonction de hachage particulière à l'application est utilisée pour produire un nombre entier à partir de la donnée d'origine.
  2. Ce nombre entier est converti en une position possible de la table, en général en calculant le reste modulo la taille de la table.

Les tailles des tables de hachage sont souvent des nombres premiers, afin d'éviter les problèmes de diviseurs communs, qui créeraient un nombre important de collisions. Une alternative est d'utiliser une puissance de deux, ce qui permet de réaliser l'opération modulo par de simples décalages, et donc de gagner en rapidité.

Un problème fréquent est le phénomène de grumelage (clustering) qui désigne le fait que des valeurs de hachage se retrouvent côte à côte dans la table, formant des "grumeaux". Cela pénalise ces méthodes. Les fonctions de hachage réalisant une distribution uniforme des hachages sont à rechercher, mais dès lors que le nombre de clés devient voisin du tiers de la taille de la table, ces collisions deviennent probables (voir Paradoxe des anniversaires).

Quand un attaquant essaye de pénaliser la recherche en soumettant des entrées générant un grand nombre de collisions afin de la ralentir (voire de provoquer un déni de service), une solution possible est de choisir aléatoirement une fonction de hachage au début du programme. L'adversaire n'a alors pas de moyen de connaitre le type de données qui produira des collisions. Dans la pratique, les algorithmes luttent plus souvent contre le hasard que contre un adversaire.

Résolution des collisions[modifier | modifier le code]

Lorsque deux clés ont la même valeur de hachage, ces clés ne peuvent être stockées à la même position. On doit alors employer une méthode de résolution des collisions.

Le calcul probabiliste montre que même si la fonction de hachage a une distribution parfaitement uniforme, il y a 95 % de chances d'avoir une collision dans une table de taille 1 million avant même qu'elle ne contienne 2 500 éléments. Les collisions ne posent cependant de réel problème que si elles sont nombreuses au même endroit. Même une collision unique sur chaque clé utilisée n'a pas d'effet très perceptible.

Plusieurs méthodes de traitement des collisions existent. Les plus utilisées sont le chaînage et l'adressage ouvert. Depuis le début des années 1990, les développeurs d'application n'ont plus à se préoccuper vraiment du détail de ces méthodes (celles-ci étant directement incorporées dans les langages eux-mêmes - Perl, PHP, REXX… - ou au pire dans les objets de la bibliothèque qu'ils utilisent.

Chaînage[modifier | modifier le code]

Résolution des collisions par chaînage.

Cette méthode est la plus simple. Chaque case de la table est en fait une liste chaînée des clés qui ont le même hachage. Une fois la case trouvée, la recherche est alors linéaire en la taille de la liste chaînée. Dans le pire des cas où la fonction de hachage renvoie toujours la même valeur de hachage quelle que soit la clé, la table de hachage devient alors une liste chaînée, et le temps de recherche est en O(n). L'avantage du chaînage est que la suppression d'une clé est facile, et que l'agrandissement de la table peut être retardé plus longtemps que dans l'adressage ouvert, les performances se dégradant moins vite.

D'autres structures de données que les listes chaînées peuvent être utilisées. En utilisant un arbre équilibré le coût théorique de recherche dans le pire des cas est en O(log n). Cependant, la liste étant supposée être courte, cette approche est en général peu efficace à moins d'utiliser la table à sa pleine capacité, ou d'avoir un fort taux de collisions. Un tableau dynamique peut aussi être utilisé pour réduire la perte d'espace mémoire et améliorer les performances du cache lorsque le nombre d'éléments est petit.

Adressage ouvert[modifier | modifier le code]

Résolution des collisions par adressage ouvert et sondage linéaire.

L'adressage ouvert consiste dans le cas d'une collision à stocker les valeurs de hachage dans des cases contiguës. La position de ces cases est déterminée par une méthode de « sondage ». Lors d'une recherche, si la case obtenue par hachage direct ne permet pas d'obtenir la bonne clé, une recherche sur les cases obtenues par une méthode de sondage est effectuée jusqu'à trouver la clé, ou non, ce qui indique qu'aucune clé de ce type n'appartient à la table.

Les méthodes de sondage courantes sont :

  • le sondage linéaire : l'intervalle entre les cases est fixe, souvent 1 ;
  • le sondage quadratique : l'intervalle entre les cases augmente linéairement (les indices des cases augmentent donc quadratiquement), ce qui peut s'exprimer par la formule : h_i(x) = \left(h(x) +  (-1)^{i+1} \cdot \left\lceil\frac{i}{2}\right\rceil^2\right) \bmod m
  • le double hachage : l'adresse de la case est donnée par une deuxième fonction de hachage, ou hachage secondaire.

Le sondage linéaire possède la meilleure performance en termes de cache, mais est sensible à l'effet de grumelage décrit plus haut. Le double hachage ne permet pas d'utiliser le cache efficacement, mais permet de réduire presque complètement ce grumelage, au prix d'une complexité plus élevée. Le sondage quadratique se situe entre le linéaire et le double hashing au niveau des performances.

Une indication critique des performances d'une table de hachage est le facteur de compression fc, qui est la proportion de cases utilisées dans la table. Plus le facteur de compression est proche de 100 %, plus le nombre de sondages à effectuer devient important. Lorsque la table est pleine, les algorithmes de sondage peuvent même échouer. Le facteur de compression est en général limité à 80 %, même en disposant d'une bonne fonction de hachage.

Des facteurs de charge faibles ne sont pas pour autant significatifs de bonnes performances, une mauvaise fonction de hachage générant du grumelage. L'indexation par la valeur ASCII de la première lettre d'une variable laisserait par exemple nombre de positions inutilisées, tout en assurant un maximum de collisions sur des noms de variables comme X1, X2..., I1, I2... en calcul scientifique ou autour de noms répandus comme "Martin" en traitement d'annuaires.

Hachage probabiliste[modifier | modifier le code]

Modification de la taille de la table[modifier | modifier le code]

Lorsque le facteur de compression de la table augmente au-delà de 50 %, les collisions deviennent fréquentes. Une solution est d'augmenter la taille de la table sitôt atteint ce taux, tout en maintenant cette taille à un nombre premier ou à une puissance de 2 selon qu'on travaille par division (lente) ou modulo (bien plus rapide). S'il y a des dizaines de milliers de clés ou davantage, le recalcul d'une valeur doit être aussi rapide que possible, et idéalement se déduire très vite à partir de la clé antérieure, idéalement par simple décalage binaire (shift).

Le rehachage (rehash) est une fonction qui, en général, double (au moins) l'espace mémoire alloué pour la table, et recopie parfois ses valeurs (temps d'exécution en O(n)). Cette fonction cherche le plus petit nombre premier supérieur à 2 fois sa taille.

Dans la pratique, les fonctions "idéales" dépendent des progrès relatifs des vitesses de calcul des processeurs et des temps d'accès à la mémoire : des choix bien adaptés à une génération de machines pourront ne plus l'être pour la suivante.

Fonction de hachage[modifier | modifier le code]

Article détaillé : fonction de hachage.

Une fonction de hachage permet de transformer une clé en une valeur de hachage (un index), donnant ainsi la position d'un élément dans le tableau.

Si la clé n'est pas un entier naturel, il faut trouver un moyen de la considérer comme tel. Par exemple, si la clé est de type chaine de caractères, on peut prendre la valeur numérique (ASCII ou autre) de chacun et les combiner par une fonction rapide et sans perte comme le ou exclusif (XOR), donnant un entier qui servira d'index. Dans la pratique, on cherche à éviter le recours aux divisions à cause de leur relative lenteur sur certaines machines.

Références[modifier | modifier le code]

  • (en) Donald Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, Addison-Wesley,‎ 1997, 3e éd. (ISBN 0-201-89685-0), partie 6, chap. 4 (« Hashing »), p. 513–558
  • (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press and McGraw-Hill,‎ 2001, 2e éd. (ISBN 0-262-03293-7), chap. 11 (« Hash Tables »), p. 221–252
  • (en) Michael T. Goodrich et Roberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, Inc., 4e éd. (ISBN 0-471-73884-0), chap. 9 (« Maps and Dictionaries »), p. 369–418
  • Christine Froidevaux, Marie-Claude Gaudel et Michèle Soria, Types de données et algorithmes, McGraw-Hill, coll. « Informatique »,‎ 1990, 575 p. (ISBN 2-8407-4023-0)