Table de hachage

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 la fonction qui à une clé associe la valeur ASCII de son premier caractère) ralentira nettement la recherche. Un bon compromis est à trouver entre :

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

Un ou exclusif de tous les caractères 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 nouveau calcul des clés qu'une translation binaire.

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 autre possibilité 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 valeurs de hachage 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[note 1].

Quand un attaquant essaye de pénaliser la recherche en soumettant des clés 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 connaître le type de données qui produira des collisions. Dans la pratique, les algorithmes sont le plus souvent conçus pour affronter des données réparties de manière aléatoire que contre un adversaire.

Une fonction de hachage est dite parfaite si elle n'engendre aucune collision. Si toutes les clés sont connues, une fonction de hachage parfaite peut être utilisée pour créer une table de hachage parfaite sans aucune collision.

Une fonction de hachage est dite minimale si elle est parfaite et répartit n entrées dans une table de exactement n alvéoles.

Une fonction de hachage parfaite permet un accès en temps constant dans tous les cas.

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 (c'est-à-dire le nombre d'alvéoles) sitôt atteint ce taux, tout en maintenant cette taille à un nombre premier ou à une puissance de 2 selon que l'on travaille par division (lent) ou modulo (bien plus rapide). S'il y a des dizaines de milliers de clés ou davantage, le calcul d'une nouvelle valeur doit être aussi rapide que possible — il doit si possible se déduire à 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 à deux 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.

Résolution des collisions par chaînage.

Cette méthode est la plus simple. Chaque alvéole de la table est une liste chaînée des paires clé–valeur qui ont la même valeur de hachage. Une fois l'alvéole 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 de paires clé–valeur est petit.

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

L'adressage ouvert consiste dans le cas d'une collision à stocker les paires clé–valeur dans d'autres alvéoles. La position des alvéoles est déterminée par une méthode de sondage. Lors d'une recherche, si l'alvéole obtenue par hachage direct ne permet pas d'obtenir la bonne clé, une recherche sur les alvéoles 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 alvéoles est fixe, souvent 1 ;
• le sondage quadratique : l'intervalle entre les alvéoles augmente linéairement (les indices des alvéoles augmentent donc quadratiquement), ce qui peut s'exprimer par la formule : ${\displaystyle h_{i}(x)=\left(h(x)+(-1)^{i+1}\cdot \left\lceil {\frac {i}{2}}\right\rceil ^{2}\right){\bmod {k}}}$ où k est le nombre d'alvéoles ;
• le double hachage : l'indice de l'alvéole est donné 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 hachage au niveau des performances.

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 compression faibles ne sont pas pour autant synonymes de bonnes performances, une mauvaise fonction de hachage pouvant générer un grumelage. L'indexation par la valeur ASCII du premier caractère d'une variable laisserait par exemple nombre de cases inutilisées, tout en assurant un maximum de collisions sur des noms de variables tels que x1, x2, … en calcul scientifique ou sur des prénoms répandus tels que Martin, Michel, … en traitement d'annuaires.

• (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition], partie 6, chap. 4 (« Hashing »), p. 513-558
• (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique [« Introduction to Algorithms »], MIT Press et McGraw-Hill, 2001, 2^e éd., 1180 p. (ISBN 978-0-262-03293-3, lire en ligne), chap. 11 (« Hash Tables »), p. 221-252
• (en) Michael T. Goodrich (en) et Roberto Tamassia (en), Data Structures and Algorithms in Java, John Wiley & Sons, 2005, 4^e éd., 720 p. (ISBN 978-0-471-73884-8), 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 978-2-84074-023-0)

• Filtre de Bloom, une autre structure de données fondée sur les fonctions de hachage