Chaining vs Linear Probing

Probing stores every key in the array itself and walks forward to the next free slot.

Chaining and linear probing are the two common ways a hash table handles a collision: chaining keeps a list in each bucket, and linear probing keeps every key in the array itself. This card covers probing on the keys 5, 13, 21, 37 and 8, then the two schemes side by side.

In linear probing each slot holds at most one key. An insert starts at the key's home slot, the key mod the capacity, and if that slot is taken it tries the next one, and the next, wrapping from the last slot to the first, until it finds a free slot. A lookup walks the same path and stops at the key or at an empty slot. In the trace, _ is an empty slot and probe marks the slot each step ended on.

Linear probing: keys 5, 13, 21, 37 and 8 in eight slots, then a delete

InputInsert 5, 13, 21, 37, 8; find 8; delete 13; find 21

Start: eight empty slots
1. _
2. _
3. _
4. _
5. _
6. _
7. _
8. _
Eight empty slots. A key's home slot is key % 8, and every key here except 8 has home slot 5.
Insert 5: home slot 5 is free
1. _
2. _
3. _
4. _
5. _
6. 5probe
7. _
8. _
5 % 8 = 5, and slot 5 is free.
Insert 13: home slot 5; taken: 5; placed in 6
1. _
2. _
3. _
4. _
5. _
6. 5
7. 13probe
8. _
13 % 8 is 5 as well. Slot 5 is taken, so the probe moves one slot on, to 6.
Insert 21: home slot 5; taken: 5, 6; placed in 7
1. _
2. _
3. _
4. _
5. _
6. 5
7. 13
8. 21probe
21 also starts at 5, and walks past 5 and 6 to 7.
Insert 37: home slot 5; taken: 5, 6, 7; placed in 0
1. 37probe
2. _
3. _
4. _
5. _
6. 5
7. 13
8. 21
37 starts at 5, finds 5, 6 and 7 taken, and wraps round to slot 0.
Insert 8: home slot 0; taken: 0; placed in 1
1. 37
2. 8probe
3. _
4. _
5. _
6. 5
7. 13
8. 21
8's home slot is 0, which 37 now holds, so 8 lands in 1: the run of full slots has pushed along a key from another home slot.
Find 8: probes slots 0, 1, found True
1. 37
2. 8probe
3. _
4. _
5. _
6. 5
7. 13
8. 21
A lookup follows the same path as the insert: slot 0 holds 37, so it moves on, and slot 1 holds 8.
Delete 13: slot 6 gets a DEL marker
1. 37
2. 8
3. _
4. _
5. _
6. 5
7. DELprobe
8. 21
Emptying slot 6 would cut the path from slot 5 to 21, so the delete leaves a DEL marker instead.
Find 21: probes slots 5, 6, 7, found True
1. 37
2. 8
3. _
4. _
5. _
6. 5
7. DEL
8. 21probe
The search passes the marker and finds 21 in slot 7. Without the marker it would stop at an empty slot 6 and report 21 missing.

Result21 found in slot 7, past the DEL marker in slot 6

Two things in the trace have no counterpart in chaining. Key 8 lands in slot 1 rather than its home slot 0, because the keys from slot 5 overflowed into slot 0. Taken slots run together into a block, called a cluster, and a cluster lengthens the walk of every key whose home slot falls inside it. And a delete cannot leave a slot empty, because an empty slot ends every search that reaches it: without the DEL marker, the run's search for 21 stopped at slot 6 and reported 21 missing. A marker like DEL, often called a tombstone, is skipped by a search and reused by an insert.

Four axes decide between the schemes: where keys live, what a delete must do, what happens as the table fills, and how memory is read.

Chaining and linear probing, axis by axis
Property	Chaining	Linear probing
Where a key is stored	In the list of its bucket	In one slot of the array
A collision	Joins the list in its bucket	Moves on to the next free slot
More keys than slots	Possible, as the lists grow longer	Impossible, so the table must grow before it fills
Deleting a key	Remove it from its list	Leave a marker in its slot
As the table fills	Lists lengthen gradually	Clusters merge, and walks lengthen sharply
Reading memory	Follows references to lists stored elsewhere	Reads neighbouring slots, which the processor fetches together

Both find a key in O(1) expected while the table is far from full. The decision rule: choose chaining for simplicity, for a table that may run full and for frequent deletes; Java's HashMap chains. Choose probing for speed in a table kept well below full, where a short walk over neighbouring slots beats following references; Python's dict probes, though in a scrambled order rather than one slot at a time.

← → move through sections and cards