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. 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.

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]$ ?

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 que le 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.