Nous avons vu plusieurs méthodes de recherche dans un tableau, en particulier la recherche linéaire dans le cas d'un tableau quelconque puis la recherche dichotomique dans le cas d'un tableau trié. Une méthode qui semble plus efficace dans le cas des chaînes de caractères a été introduite à propos de la table des symboles lors de la conception des compilateurs et réutilisée souvent depuis. Il s'agit de la méthode des tables de hachage (hash table en anglais).

Le principe en est simple. Considérons un ensemble A de N éléments, sous-ensemble d'un ensemble B de cardinal important (ce qui est le cas de celui des chaînes de caractères de longueur maximale max). On considère un tableau d'éléments de B de dimension un peu plus grande que ce qui est vraiment nécessaire, par exemple un tableau de dimension 2N et une fonction de hachage f qui, à tout élément de B, associe un entier (l'index dans le tableau) compris entre 0 et 2N-1. Le premier élément a1 de A est placé à l'index f(a1). Le deuxième élément a2 est placé à l'index f(a2) si celui-ci est différent de f(a1). Sinon on dit qu'il y a collision et on le place un peu plus loin. On appelle numéro de hachage l'index retenu.

Il existe plusieurs méthodes de hachage, chacune se différençiant par sa fonction de hachage et surtout par son traitement des collisions.