Le hachage

Comment faire des opérations de recherche et d'insertion dans une table en temps constant ? Les mémoires associatives, étudiées en intelligence artificielle, auraient cette propriété : la position occupée par un objet est déterminée seulement par cet objet. Il suffit de calculer la position en mémoire de cet objet, donc de disposer d'une fonction qui associe à un objet x sa position h(x) ; on veut que le temps de calcul de h(x) soit indépendant de x et aussi petit que possible. On dit que h(x) est la valeur de hachage associée à x. C'est l'idée des tables de hachage, dont l'organisation s'oppose radicalement à celle des tables ordonnées, dans lesquelles la position d'un objet dépend du nombre d'objets plus petits qui ont déjà été insérés dans la table. Cette structure de données est sûrement la plus utile de toutes celles rencontrées dans ce cours. Son seul inconvénient est que l'ordre dans lequel les données sont stockées n'est pas maîtrisable. Si l'on doit énumérer les données par ordre croissant, il faut recourir à une autre implémentation des tables, à l'aide d'arbres, et renoncer au coût constant des opérations pour un coût logarithmique.

Si l'on devait insérer dans une table les éléments de l'ensemble [0,N-1], il suffirait d'utiliser un tableau t de taille N et de ranger l'objet i dans t[i], solution triviale, avec h(i) = i. Cela n'est déjà plus aussi simple si au lieu de l'intervalle [0,N-1], on doit traiter un ensemble quelconque E de N entiers : comment faire pour construire << effectivement >> une fonction injective de E dans l'ensemble des indices du même tableau [0,N-1] ? L'existence d'une fonction injective est sans doute rassurante mais pas suffisante. En effet, les fonctions injectives sont rares : il y a n^m fonctions d'un ensemble de cardinal m dans un ensemble de cardinal n, parmi lesquelles il y a $\frac{n!}{(n-m)!}$ fonctions injectives, si $m\le n$. Une estimation asymptotique du rapport $\frac{n!}{(n-m)!n^m}$, par la formule de Stirling, quand $n\to\infty$, est e^-k2/2n. Le problème se complique encore, car on veut insérer dans une table des objets d'un ensemble E de cardinal plus grand, voire beaucoup plus grand que N. Par exemple, la table de hachage qu'un compilateur construit pour les noms figurant dans un programme donné doit contenir tout au plus quelques centaines de noms, mais ces noms appartiennent au minimum à un ensemble de cardinal $27\times 37^5$, soit près de deux milliards, pour le langage C, dont la norme impose à tout compilateur d'accepter des identificateurs d'au moins 6 caractères, formés de chiffres, de lettres sans distinction de casse et de '_', et commençant par une lettre ou par '_'. Le problème est de construire une fonction, qui bien que non injective, a de bonnes propriétés de dispersion.

Voici un exemple simple de fonction de hachage sur des chaînes de longueur l à valeurs dans l'intervalle [0,N-1] :

$$h(x) = \sum_{i=0}^{l-1} x[i] B^{l-1-i} \mathop{\normalfont\mathrm{mod}}\nolimits N$$

où B est une puissance de 2 (pour faciliter le calcul, par exemple B=256) et N est un nombre premier (pour éviter des collisions << arithmétiques >>), ou en Java:

  private static final int B=256;
  private static final int N=311;

  private static int h(String x) {
    int v = 0;
    for (int i=0; i<x.length(); i++) {
      v = (v*B + x.charAt(i)) % N;
    }
    return v;
  }

L'API de Java définit une méthode hashCode() dans la classe Object, qui peut donc être utilisée pour tous les objets, et qui peut être redéfinie dans n'importe quelle classe.

Comme la fonction de hachage h n'est pas injective, il faut savoir traiter les collisions, c'est-à-dire le cas de deux clés $x\not= y$ayant la même valeur de hachage h(x) = h(y). Il existe deux sortes de techniques de résolution : le hachage ouvert et le hachage par chaînage.