7.4.
Handling Collisions with Linked Lists
The proposed solution to implement the hash table combines
the table structure with linked lists. Each position in the table does not
store only one element, but the first element of a linked list containing
all elements such that the hash function produced identical result. A
position in the table with no elements contains a NULL pointer representing
an empty list. The following figure shows a table of size
n and the elements stored in positions 0, 1, 2, n-2 and
n-1.
Note that different positions in the table may have linked
lists with different lengths, or even empty. Given a key, the search
procedure amounts to first computing its index with the hash function and
then traverse the collision list to see if such element is present.
