Hachage par chaînage

La méthode de hachage par adressage ouvert avec sondage linéaire a l'inconvénient d'effectuer des comparaisons avec plusieurs cases successives de la table, qui n'ont pourtant pas la même valeur de hachage que l'objet recherché. Pour éviter ces comparaisons inutiles, on va chaîner les objets ayant la même valeur de hachage.   La table de hachage est également implémentée par un tableau, l'élément du tableau d'indice iétant une référence à un objet rassemblant des associations dont les clés ont i pour valeur de hachage. Cet objet peut être une liste chaînée ou plus simplement, un tableau d'Association ; le type ArrayList de l'API Java convient à cette implémentation :

  List[] tableau = new ArrayList[N];

Les opérations d'insertion, de recherche et de suppression se font en deux étapes : le calcul de la valeur de hachage, h, puis la délégation de l'opération à la liste tableau[h].

 

Le taux de chargement (voir § 2.10) $\alpha = n/N$ est la longueur moyenne des listes chaînées. Sous une hypothèse d'uniformité de la fonction de hachage, on montre que le nombre moyen d'accès nécessaires pour une recherche, négative ou positive, est d'au plus $1+\alpha$.