Table de hachage

Description

Une table de hachage est un type concret utilisé pour stocker des objets, chacun associé à une clé unique. Typiquement, la clé est un objet relativement simple comme un nombre ou une chaîne de caractères.

Les tables de hachages sont très fréquemment utilisé, car elles sont très efficace. La complexité moyenne d'une opération (performance amortie) est constante.

Le domaine des clés doit permettre deux opérations. D'abord, il doit être possible de tester l'égalité entre deux clés. Puis, il doit être possible d'appliquer une fonction de hachage à une clé, afin d'obtenir un entier non négatif (potentiellement très grand). Cette fonction de hachage doit être rapide. Si les clés sont déjà des entiers non négatifs, la fonction de hachage peut être la fonction d'identité. Pour les chaînes de caractères, c'est un peu plus difficile. Une technique typique est de calculer ne combinaison du code (Unicode, par exemple) de chaque caractère et de la position de celui-ci dans la chaîne. La fonction de hachage doit, autant que possible, éviter de renvoyer le même nombre pour un grand nombre de clés.

Implémentation

L'implémentation typique d'une table de hachage utilise un tableau dont chaque élément est une liste contenant des couples clé, objet.

Pour déterminer si un objet associé à une clé est dans la table, on commence par appliquer la fonction de hachage sur la clé. Cela donne un entier non négatif. On calcule alors ce nombre modulo la taille du tableau afin d'obtenir un index valide du tableau. Finalement, on parcours la liste stockée à cet index du tableau, en comparant la clé stocké dans chaque élément de la liste avec la clé cherchée. Si pour une couple clé, objet, la comparaison renvoie vrai, alors l'objet correspondant est renvoyé.

Pour insérer un objet associé à une clé dans la table, on procède de manière similaire. On applique la fonction de hachage pour obtenir un index, et on parcours la liste pour vérifier si un objet avec cette clé existe déjà. Si c'est le cas on remplace l'objet. Sinon, on stocke une nouvelle couple clé, objet dans la liste.

La suppression d'un objet associé à une clé est similaire. Encore une fois, la fonction de hachage est appliqué à la clé, et la liste à l'index obtenu est parcourue. Si la clé n'existe pas on ne fait rien. Sinon, on supprime la couple de la liste.

Choix de la taille du tableau

La taille du tableau doit être choisie pour que le taux de remplissage soit faible. Le taux de remplissage est défini comme le nombre total d'objets stockés dans la table, divisé par la taille du tableau. Un bon taux maximal permis est environ 5.

Lorsque des objets sont rajouté au fur et à mesure à la table, le taux de remplissage de celle-ci augmente. Il faut alors modifier la taille du tableau afin de diminuer le taux de remplissage. Pour ce faire, on commence par allouer un nouveau tableau. Puis on parcours chaque liste de l'ancien tableau, et pour chaque couple clé, objet on applique à nouveau la fonction de hachage à la clé, mais cette fois-ci le modulo est fait avec la taille du nouveau tableau. Le résultat de cette opération détermine l'index dans le nouveau tableau où doit être stockée la couple. Chaque couple est ainsi déplacé de l'ancien tableau au nouveau. On termine l'opération en libérant la place occupé par l'ancien tableau.

Cette opération étant très coûteuse, il faut éviter de l'exécuter trop souvent. Pour cela, on peut par exemple doubler la taille du tableau à chaque fois que le taux de remplissage dépasse une certaine valeur (5, par exemple). Si l'on se content d'augmenter la taille d'un nombre constant de places, cette opération risque d'être exécuter trop souvent.

L'opération inverse peut être envisageable lorsque le taux de remplissage devient inférieur à un certain seuil. Le déroulement est identique à celui indiqué ci-dessus, sauf que la taille du nouveau tableau est inférieure à celle de l'ancien. Par contre, il faut choisir le seuil considérablement plus petit que le précédent. En fait, si lors de l'augmentation de la taille du tableau, on multiplie sa taille par k > 1, alors le taux de remplissage immédiatement après cette augmentation est t/kt est l'ancien taux de remplissage. Si par exemple k = 2, alors le taux de remplissage diminue de moitié. Si dans cette situation, on diminue la taille du tableau à chaque fois que le taux est inférieur à t/k, on risque d'avoir des oscillations très coûteuses. En effet, une suite d'opération d'insertions et de suppressions en alternance, risque de déclencher une modification de la taille du tableau. Si la taille du tableau est doublée à chaque dépassage du taux de remplissage, alors, un bon seul pour déclencher une diminution de la taille du tableau est t/4. Si t = 5, cela donne un taux de 1.2.

Variations

Lors de l'insertion d'un objet associé à une clé, si un objet associé à la clé existe déjà, au lieu de remplacer l'objet existant, on peut imaginer de déclencher une erreur.

De la même manière, lors de la suppression d'un objet associé à une clé, si aucun objet associé à la clé n'existe, au lieu de ne rien faire, on peut imaginer de déclencher une erreur.