Le nid de dodo

Un article de bredelet    1 Commentaire

Table de hachage

La table de hachage est une structure de données qui permet d’implémenter une table associative (que l’on appelle aussi un index ou un dictionnaire). Son principe est de répartir les données de façon homogène à l’aide d’une fonction de hachage appliquée aux clés de la table.

La plupart des langages de programmation offrent une table de hachage comme structure de données standard, avec peut-être l’exception notable du langage C (noter que le C++ comble cette lacune).

Mais est-il possible de faire mieux que la table de hachage proposée par défaut?

Mesure du mieux

Il y a différentes mesures qui déterminent la qualité d’une table de hachage.

L’une d’elle est le taux de remplissage – est-ce que la table accommode un certain nombre d’éléments sans laisser trop de « trous »?

Une autre est l’efficacité de consultation, et l’efficacité d’insertion. Je ne parlerai pas de l’efficacité d’enlever un élément.

Un facteur clé pour améliorer le taux de remplissage est une bonne fonction de hachage. Par exemple, si la fonction de hachage ne retourne jamais que des nombres entre 0 et 100, il est inévitable que plusieurs clés aient la même valeur de hachage après une centaine d’insertions. Même si la table de hachage se redimensionne pour accommoder plus d’éléments, ce sera en vain car tous les éléments vont se retrouver aux emplacements correspondants aux nombres de 0 à 100, en fait c’est contre-productif puisque le taux de remplissage se détériore!

La solution proposée dans cet article ne permet pas de compenser une mauvaise fonction de hachage. En fait elle est plus exigeante que les solutions traditionnelles car elle fait appel à plusieurs fonctions de hachage pour chaque clé.

Le principe de la seconde chance

Utiliser deux (ou davantage) fonctions de hachage est la base de la première astuce qui va nous permettre d’écrire une table de hachage super efficace, le principe de la seconde chance.

Etant donné une fonction de hachage h1 et une clé k, comment décider où placer l’élément dans la table de hachage? Une table de hachage fait généralement appel à un tableau de taille fixe (N) pour stocker les données, donc il s’agit de faire correspondre le numéro retourné par h1(k) avec un numéro d’index dans ce tableau.

Cela se fait souvent avec l’opération modulo, c’est-à-dire le reste de la division h1(k) / N. Le modulo donne un nombre entre 0 et N-1 qui est utilisée comme valeur d’index.

Si je rappelle tout cela, c’est pour mettre en exergue le fait qu’une tâche de la table de hachage est de gérer les collisions. En effet, il y a plusieurs valeurs telles que, par exemple, x modulo 100 est égal à 13. Si la valeur de hachage est 13, 113, 213, 313 etc il faut lui trouver une place même s’il y a déjà un élément à l’emplacement prévu.

Une solution est de rechercher un autre emplacement possible pour l’élément. Le principe de la seconde change utilise une différente fonction de hachage, disons h2, pour déterminer cet autre emplacement. Il est important que h1 et h2 soient indépendants, autrement il y a des chances que les deux fonctions retournent les mêmes deux résultats pour différentes clés.

Donc l’algorithme est:

p1 = h1(k) modulo N
si libre(p1)
  alors table[p1] = paire(k, élément)
sinon
  p2 = h2(k) modulo N
  si libre(p2)
    alors table[p2] = paire(k, élément)

Il est possible d’utiliser davantage de fonctions de hachage de la même façon que h2.

Pour retrouver un élément, on regarde aux différents emplacements possible pour voir s’ils contiennent la clé recherchée.

Si tous les emplacements sont déjà pris, il peut être nécessaire de redimensionner le tableau — ce qui donne un nouvel N et permet, on l’espère, de placer l’élément.

Il n’est pas très satisfaisant de devoir compter sur un N qui a exactement la bonne valeur pour pouvoir placer un élément, d’autant plus qu’il est coûteux de redimensionner la table de hachage car tous les éléments prennent un nouvel emplacement. L’efficacité de consultation est très bonne mais utilisé seul, le principe de seconde chance donne un taux de remplissage avoisinant les 50%.

Le principe du coucou

Pour améliorer cela, on utilise une autre astuce: le principe du coucou. Le bébé coucou, il est bien connu, est né dans le nid d’autres oiseaux et se fait de la place en jetant les oeufs du nid par-dessus bord. Pour une table de hachage, l’idée est de faire de la place en déplaçant l’élément existant autre part.

Certains utilisent les fonctions de hachage pour trouver un nouvel emplacement à l’élément existant dans la table de hachage. S’il n’y a pas d’emplacement libre, il peut y avoir des déplacements en cascade. Mais une étude a montré qu’un seul déplacement par insertion est nécessaire pour une bonne efficacité.

Ma solution, de son côté, utilise une réserve pour les éléments existants déplacés. Dans mes tests, en utilisant une table de hachage de 50 à 100 éléments comme réserve, le taux de remplissage excède facilement 90% pour l’insertion de 250 à 10000 éléments jusqu’à saturation.

C’est tout bonnement excellent pour une solution aussi simple et économe en espace mémoire.

L’algorithme combinant le principe de seconde chance avec deux fonctions de hachage, le principe du coucou et une réserve est:

p1 = h1(k) modulo N
si libre(p1)
  alors table[p1] = paire(k, élément)
sinon
  p2 = h2(k) modulo N
  si libre(p2)
    alors table[p2] = paire(k, élément)
  sinon
    p = choix(p1 ou p2)
    ajoute(réserve, table[p])
    table[p] = paire(k, élément)

Si la réserve est pleine on a le choix de redimensionner le tableau ou la réserve. Je pense que l’idéal est d’augmenter les deux jusqu’à ce que la taille de la réserve soit trop grande pour être stockée dans une ligne de cache ou une page de mémoire, puis n’augmenter que la taille du tableau. Mes tests montrent qu’il n’y a pas d’avantage à avoir une très grande réserve.

Pour la réserve on peut utiliser une table de hachage comme je l’ai fait ou on peut utiliser une liste ordonnée par valeur de hachage, dont l’ordre peut être maintenu de façon efficace pour un nombre d’éléments restreint (O(log N) pour la consultation et pour l’insertion). L’avantage est que la liste ordonnée peut accepter des éléments dont toutes les valeurs de hachage sont identiques.

Problème: je n’ai qu’une seule fonction de hachage!

Souvent en standard on n’a qu’une seule fonction de hachage à disposition, par exemple en Java il y a x.hashCode(). Dans le cas d’un objet composé de plusieurs attributs, on peut simplement prendre les attributs uniques à l’objet et utiliser leurs fonctions de hachage.

Il y a un autre moyen. Puisque l’index dans le tableau est calculé à l’aide de h1(k) modulo N, le résultat non fractionnaire de la division n’entre pas en compte. Par exemple si:

N = 100
h1(k)=1113

alors l’index est 13. On n’utilise pas les deux premiers chiffres 11.

Donc on peut utiliser la partie entière de la division h1(k) / N comme seconde valeur de hachage.

Et maintenant, à vos claviers!