Hash table with chaining

Each slot of the table holds a list, and keys that hash to the same slot line up in that list; a collision never runs out of room.

The hash function h(key) = key mod m sends each key to one of m slots. Two keys may land in the same slot (a collision). With chaining, each slot holds a list, and all the keys of that slot go into its list.

Read the full explanation ↓

Time: O(1 + n/m) on average per operation
Space: O(n + m)
CLRS, section 11.2
Horowitz–Sahni, chapter 8
Johnsonbaugh, chapter 3

Input:

n=10PDF export

Ten keys in a 7-slot table; a few collisions happen and the chains grow.

def hash_chaining(keys):
m = 7
table = [[] for _ in range(m)]
for key in keys:
slot = key % m
table[slot].append(key)
longest = max(len(chain) for chain in table)
return table

Invariant: Every key sits in the list of slot h(key); so a search only has to walk that one list.

Start

key—

slot—

The table is still empty.

Local variables

Orange = changed in this step

`keys` list

102231415281788593

Call stack

hash_chaining()line 1

Step 1 of 36

Explanation

The idea

Cost

With the load factor α = n / m (the average chain length), a search costs O(1 + α) on average, as long as the hash function spreads the keys well. If they all land in one slot, a search costs O(n) (the "all in one slot" input).

Compared with open addressing

With linear probing the keys sit in the table itself and the table can fill up; here the table never fills, but the lists need extra memory.

What to watch in the trace

Each table row is a slot; the row that just got a key is highlighted.