Resolve Collisions by Chaining

Keys that land in the same bucket share a short list there.

Chaining resolves a collision by keeping a list in each bucket, so every key that lands in a bucket is stored there. This card covers five keys inserted into a table that chains, then three lookups, one of which finds nothing.

The goal is the table's final state and the work each lookup does. The table has eight buckets, numbered 0 to 7, and its keys are whole numbers. In Python a small whole number is its own hash code, so a key's bucket is the key mod 8, its remainder after dividing by 8. The keys arrive in the order 5, 13, 21, 37, 8. The list in one bucket is called a chain, and it is written from its first key with arrows between keys, while - marks an empty bucket.

Before the steps: which bucket holds the most keys at the end, and how many?

Bucket 5, with four keys: 5, 13, 21 and 37 all leave a remainder of 5 when divided by 8.

A run printed every bucket after each insert:

Five keys inserted into eight buckets that chain

Insert 5

5 mod 8 is 5, and bucket 5 is empty, so its chain becomes the single key 5.

text

0: -
1: -
2: -
3: -
4: -
5: 5
6: -
7: -

Insert 13

13 mod 8 is also 5, so 13 collides with 5. The insert first compares 13 with each key already in the chain, because a key that is there already must have its value updated rather than be stored twice. Finding no match, it adds 13 to the end of the chain.

text

0: -
1: -
2: -
3: -
4: -
5: 5 -> 13
6: -
7: -

Insert 21

21 mod 8 is 5 again, so the chain grows to three keys.

text

0: -
1: -
2: -
3: -
4: -
5: 5 -> 13 -> 21
6: -
7: -

Insert 37

37 mod 8 is 5 as well. The chain reaches four keys while seven buckets are still empty.

text

0: -
1: -
2: -
3: -
4: -
5: 5 -> 13 -> 21 -> 37
6: -
7: -

Insert 8

8 mod 8 is 0, so 8 starts a chain of its own in bucket 0.

text

0: 8
1: -
2: -
3: -
4: -
5: 5 -> 13 -> 21 -> 37
6: -
7: -

A lookup makes the same two moves: work out the bucket, then walk its chain, comparing each key with the one it wants. The run made three lookups and printed the keys each one compared:

text

LOOKUP 37: bucket 5, compared 5 13 21 37, found
LOOKUP 29: bucket 5, compared 5 13 21 37, not found
LOOKUP 8: bucket 0, compared 8, found

The lookup for 37 compared four keys before finding it. The lookup for 29, which is not in the table, compared the same four before giving up, because 29 mod 8 is also 5, and only the end of the chain could tell it 29 was absent. The lookup for 8 compared one. A lookup therefore costs one hash code plus the length of one chain, written O(1 + chain length).

With n keys spread evenly, each chain holds about n divided by the number of buckets, and keeping that ratio small keeps every lookup close to O(1). These five keys did not spread: whenever a key is its own hash code, keys that differ by a multiple of 8 always share a bucket of eight, so four of them formed one chain. To check the result, every key can be found by repeating the calculation that placed it, and the table holds five keys in two chains.

← → move through sections and cards