Table de hachage - Définition
La liste des auteurs de cet article est disponible ici.
Résolution des collisions
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 stratégie de résolution des collisions.
Pour donner une idée de l'importance d'une bonne méthode de résolution des collisions, considérons ce résultat issu du paradoxe des anniversaires. Même si nous sommes dans le cas le plus favorable où la fonction de hachage a une distribution uniforme, il y a 95% de chances d'avoir une collision dans une table de taille 1 million avant qu'elle ne contienne 2500 éléments.
De nombreuses stratégies de résolution des collisions existent mais les plus connues et utilisées sont le chainage et l'adressage ouvert.
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
L'adressage ouvert consiste dans le cas d'une collision à stocker les valeurs de hachage dans des cases contigües. 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:
- Sondage linéaire
- l'intervalle entre les cases est fixe, souvent 1.
- 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 :
- 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 clustering décrit plus haut. Le double hachage ne permet pas d'utiliser le cache efficacement mais permet de réduire presque complètement les problèmes de clustering, en contrepartie 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 charge qui est la proportion de cases utilisées dans la table. Plus le facteur de charge 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 charge 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 bonne performances, en particulier si la fonction de hachage est mauvaise et génère du clustering.
