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 sa position
; on
veut que le temps de calcul de
soit indépendant de
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
, il suffirait d'utiliser un tableau
de taille
et de
ranger l'objet
dans
, solution triviale, avec
. Cela
n'est déjà plus aussi simple si au lieu de l'intervalle
, on
doit traiter un ensemble quelconque
de
entiers : comment faire
pour construire << effectivement >> une fonction injective de
dans
l'ensemble des indices du même tableau
?
Le problème se complique encore, car on veut insérer dans une table des
objets d'un ensemble de cardinal plus grand, voire beaucoup plus
grand que
. 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
, 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.