La table de hachage est implémentée comme un tableau dont les cases
vont contenir les objets. Initialement, la table est vide, c'est-à-dire
chaque case contient un objet spécial vide (par exemple, un objet
dont la clé est la chaîne vide "").
const data empty_data = {""} ; bool is_empty(data d) { return d.key.length() == 0; } void init(int N, data t[]) { int i; for (i=0; i<N; i++) { t[i] = empty_data; } }
Puis des opérations d'insertion sont réalisées. Si un objet de clé
doit être inséré, et que
est vide, alors l'insertion se fait à
cette place ; si par contre
est déjà occupé, et que le contenu
a une clé différente de
, alors on calcule des valeurs de hachage
supplétives
,
, ...jusqu'à ce que l'on trouve
vide ou contenant un objet de clé
.
Pour générer ces nouvelles valeurs de hachage, la méthode la plus simple
est le hachage linéaire, qui choisit
, ce qui revient à essayer les cases suivant
. Il y a d'autres méthodes (hachage quadratique, double
hachage, hachage aléatoire) qui ont de meilleures capacités de
dispersion.
bool insert(const data& d, int N, const data t[]) { int v = h(d.key); int i; for (i=0; i<N; i++) { if (is_empty (t[(v+i)%N])) { t[(v+i)%N] = d; // insertion à la ième place disponible break; } else if (t[(v+i)%N].key == d.key) { break; // ou bien, mise à jour des autres champs } } if (i == N) { return false; // table pleine, insertion non réalisée } else { return true; // objet déjà dans la table ou inséré } }
De même, pour chercher un objet de clé , on teste les objets en
, et éventuellement en
,
, etc, jusqu'à
ce que la clé de l'objet qui s'y trouve soit égale à
, ou bien que
l'objet soit vide. Dans le cas où la table permet aussi des
suppressions, il faut remplacer un objet supprimé par un objet spécial
supprimé, distinct de l'objet vide ; en insertion, on utilisera
la première case vide ou supprimé, tandis qu'en recherche, on ne
s'arrêtera qu'à la première case vide.
data& search(const string s, int N, const data t[]) { int v = h(s); int i; for (i=0; i<N; i++) { if (is_empty (t[(v+i)%N])) { return empty_data; } else if (t[(v+i)%N].key == s) { return t[(v+i)%N]; } } return empty_data; // objet non trouvé }
Il est clair que la complexité dans le pire des cas est de
opérations,
étant la taille de la table. On définit le taux
de chargement d'une table
de hachage de taille
contenant
objets comme la fraction
; on a toujours
. Pour donner une estimation
asymptotique de la complexité des opérations, on fait tendre
et
vers l'infini, à
constant. On montre que, sous une hypothèse
d'uniformité, le nombre moyen d'accès nécessaires pour une recherche
négative est d'au plus
et pour une recherche positive de
. Par
exemple pour une table à moitié pleine, on doit s'attendre à faire 2
accès pour la recherche d'un objet ne se trouvant pas dans la table, et
et à faire 3,387 accès s'il s'y trouve. Il s'agit bien d'un algorithme
en
.