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