La méthode de hachage par adressage ouvert avec résolution 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 la chaîne recherchée. Pour éviter ces comparaisons inutiles, on va << chaîner >> les objets ayant la même valeur de hachage.
Une liste chaînée étiquetée (en anglais labelled linked list), appelée désormais liste, est définie récursivement de la façon suivante : une liste est soit vide, soit formée d'une étiquette et d'une liste, appelée son successeur.
Nous utilisons l'allocation dynamique pour implémenter une liste. La liste est implémentée à l'aide d'une cellule contenant un objet et un pointeur de cellules, appelé lien, de façon analogue aux arbres binaires étiquetés (en plus simple, puisqu'il n'y a qu'un lien au lieu de deux) :
struct list_cell {
data label;
struct list_cell *next;
};
typedef struct list_cell list_cell;
Figure: Hachage ouvert avec chaînage
La table de hachage est implémentée par un tableau de pointeurs de list_cell et non comme un tableau d'enregistrements :
list_cell *t[N];
Le parcours des objets ayant la même valeur de hachage se fait de façon très classique par un for ; la condition d'exécution, c != NULL, est que la variable c << pointe >> ; l'instruction d'itération remplace un lien par le lien suivant :
list_cell *lookup(const char s[], const list_cell *t[]) {
list_cell *c;
for (c = t[h(s)]; c != NULL; c = c->next) {
if (strcmp(s, (c->label).key) == 0) {
return c;
}
}
return NULL;
}
Cette fonction retourne la cellule contenant la chaîne recherchée ou bien NULL en cas d'échec.
L'insertion d'un enregistrement d dans une table t est réalisé par la fonction suivante. On commence par appeler lookup. En cas d'échec, il y a allocation dynamique d'une nouvelle cellule dont les deux champs sont remplis et qui est placée en tête de la liste chaînée. En cas de succès de lookup, il y a remplacement de l'ancien champ info par le nouveau.
void insert(const data d, list_cell *t[]) {
list_cell *c = lookup(d.key);
unsigned int v = h(d.key);
if (c == NULL) {
c = malloc(sizeof(list_cell));
c->label = d;
c->next = t[v];
t[v] = c;
} else {
(c->label).info = d.info;
}
}
Le taux de chargement (voir §
) 
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 
.