Linear Probing
Chapter One Hundred Five
Syllabus topic Module 2, "collision avoidance techniques"; Computer Science Practical 3, "Implement a hash table with chaining or linear probing"
Pages 367 to 375 of 411
In one line
Linear probing keeps every record inside the array: if a key's slot is taken, it tries the next slot, and the next, until it finds a free one.
Open addressing
Chaining stores colliding records outside the array, in lists. Open addressing stores every record inside the array itself, so the array is the whole structure: no nodes, no pointers, no lists.
The immediate consequence: the table can fill up. The load factor cannot exceed 1, and an insertion into a full table must fail or grow the table. That is the trade for losing the pointers.
Linear probing is the simplest open addressing scheme.
probe sequence: h(k), h(k)+1, h(k)+2, h(k)+3, ... all mod m
h_i(k) = ( h(k) + i ) mod m for i = 0, 1, 2, ...
Insert: walk the sequence until an empty slot is found; put the record there. Search: walk the sequence until the key is found, or an empty slot is reached, which means the key is not in the table.
That second rule is the whole chapter. A search stops at an empty slot because an insert would have stopped there too, so the key cannot be any further along.
Built, and traced
EMPTY = None
class LinearTable:
def __init__(self, buckets=11):
self.slots = [EMPTY] * buckets
self.count = 0
def _hash(self, key):
return key % len(self.slots)
def insert(self, key, value, trace=False):
start = self._hash(key)
for i in range(len(self.slots)):
at = (start + i) % len(self.slots)
if self.slots[at] is EMPTY:
self.slots[at] = (key, value)
self.count += 1
if trace:
print(" insert %-4d h=%-3d placed at %-3d after %d probe(s)"
% (key, start, at, i + 1))
return at, i + 1
if self.slots[at][0] == key:
self.slots[at] = (key, value)
return at, i + 1
raise RuntimeError("the table is full")
def search(self, key):
start = self._hash(key)
for i in range(len(self.slots)):
at = (start + i) % len(self.slots)
if self.slots[at] is EMPTY:
return None, i + 1 # an empty slot ends the search
if self.slots[at][0] == key:
return self.slots[at][1], i + 1
return None, len(self.slots)
def show(self):
return "\n".join(
" [%2d] %s" % (i, "%-5d %s" % cell if cell else "")
for i, cell in enumerate(self.slots))
t = LinearTable(buckets=11)
print("inserting into an 11 slot table, h(k) = k mod 11:")
for k, name in ((25, "Aarti"), (36, "Bhavesh"), (14, "Chetna"),
(47, "Devdatta"), (3, "Esha"), (58, "Farhan")):
t.insert(k, name, trace=True)
print()
print("the table:")
print(t.show())
print()
print("ALL SIX keys hash to slot 3:",
", ".join("%d mod 11 = %d" % (k, k % 11) for k in (25, 36, 14, 47, 3, 58)))
print("so they filled slots 3 to 8 in a run, which is a CLUSTER.")
print()
for k in (58, 3, 99):
value, probes = t.search(k)
print("search %-4d -> %-10s in %d probe(s)"
% (k, value if value else "absent", probes))
print()
print("finding 58 took 6 probes, because it was inserted last and so sits")
print("at the far end of the cluster. finding 99 took 1, because slot 0 is")
print("empty and the search stops there at once.")Linear Probing
inserting into an 11 slot table, h(k) = k mod 11:
insert 25 h=3 placed at 3 after 1 probe(s)
insert 36 h=3 placed at 4 after 2 probe(s)
insert 14 h=3 placed at 5 after 3 probe(s)
insert 47 h=3 placed at 6 after 4 probe(s)
insert 3 h=3 placed at 7 after 5 probe(s)
insert 58 h=3 placed at 8 after 6 probe(s)
the table:
[ 0]
[ 1]
[ 2]
[ 3] 25 Aarti
[ 4] 36 Bhavesh
[ 5] 14 Chetna
[ 6] 47 Devdatta
[ 7] 3 Esha
[ 8] 58 Farhan
[ 9]
[10]
ALL SIX keys hash to slot 3: 25 mod 11 = 3, 36 mod 11 = 3, 14 mod 11 = 3, 47 mod 11 = 3, 3 mod 11 = 3, 58 mod 11 = 3
so they filled slots 3 to 8 in a run, which is a CLUSTER.
search 58 -> Farhan in 6 probe(s)
search 3 -> Esha in 5 probe(s)
search 99 -> absent in 1 probe(s)
finding 58 took 6 probes, because it was inserted last and so sits
at the far end of the cluster. finding 99 took 1, because slot 0 is
empty and the search stops there at once.Primary clustering
That run of occupied slots is the scheme's characteristic weakness, and it has a name: primary clustering.
The mechanism is worth stating exactly, because it is more than "collisions pile up". Once a cluster of length L exists, any key that hashes anywhere inside it joins its end, which makes the cluster L+1 long. So a long cluster is more likely to grow than a short one, and clusters merge. Growth feeds on itself.
def mix(i):
x = ((i + 1) * 2654435761) % (2 ** 32)
x ^= x >> 13
x = (x * 2246822519) % (2 ** 32)
x ^= x >> 17
return x
M = 1009
def fill(n, m):
slots = [None] * m
for i in range(n):
k = mix(i)
at = k % m
while slots[at] is not None:
at = (at + 1) % m
slots[at] = k
return slots
def clusters(slots):
"""Lengths of the runs of occupied slots, treating the array as a ring."""
m = len(slots)
if all(s is not None for s in slots):
return [m]
start = next(i for i in range(m) if slots[i] is None)
runs, run = [], 0
for step in range(m):
at = (start + step) % m
if slots[at] is None:
if run:
runs.append(run)
run = 0
else:
run += 1
if run:
runs.append(run)
return runs or [0]
print("%8s %10s %14s %16s %16s"
% ("alpha", "records", "clusters", "longest cluster", "average cluster"))
for alpha in (0.25, 0.5, 0.7, 0.8, 0.9, 0.95, 0.99):
n = int(alpha * M)
runs = clusters(fill(n, M))
print("%8.2f %10d %14d %16d %16.1f"
% (alpha, n, len(runs), max(runs), sum(runs) / len(runs)))
print()
print("read the longest-cluster column. between alpha 0.5 and alpha 0.9 the")
print("record count not quite doubles, and the longest cluster grows far")
print("more than that. clusters do not grow in proportion. they snowball.")Linear Probing
alpha records clusters longest cluster average cluster
0.25 252 170 7 1.5
0.50 504 187 21 2.7
0.70 706 141 46 5.0
0.80 807 102 96 7.9
0.90 908 50 213 18.2
0.95 958 28 702 34.2
0.99 998 5 981 199.6
read the longest-cluster column. between alpha 0.5 and alpha 0.9 the
record count not quite doubles, and the longest cluster grows far
more than that. clusters do not grow in proportion. they snowball.The cost, measured against the formulas
unsuccessful search : about ( 1 + 1 / (1 - alpha)^2 ) / 2
successful search : about ( 1 + 1 / (1 - alpha) ) / 2
Both blow up as alpha approaches 1, and the unsuccessful one blows up as the square.
def mix(i):
x = ((i + 1) * 2654435761) % (2 ** 32)
x ^= x >> 13
x = (x * 2246822519) % (2 ** 32)
x ^= x >> 17
return x
M = 1009
def build(n, m):
slots = [None] * m
keys = [mix(i) for i in range(n)]
for k in keys:
at = k % m
while slots[at] is not None:
at = (at + 1) % m
slots[at] = k
return slots, keys
def measure(n, m):
slots, keys = build(n, m)
hit_probes = 0
for k in keys:
at, probes = k % m, 1
while slots[at] != k:
at = (at + 1) % m
probes += 1
hit_probes += probes
absent = [mix(500000 + i) for i in range(500)]
miss_probes = 0
for k in absent:
at, probes = k % m, 1
while slots[at] is not None:
at = (at + 1) % m
probes += 1
miss_probes += probes
return hit_probes / len(keys), miss_probes / len(absent)
print("%7s %10s %12s %12s %14s %14s"
% ("alpha", "records", "hit found", "hit formula", "miss found", "miss formula"))
for alpha in (0.25, 0.5, 0.75, 0.9, 0.95):
n = int(alpha * M)
hit, miss = measure(n, M)
hit_formula = (1 + 1 / (1 - alpha)) / 2
miss_formula = (1 + 1 / (1 - alpha) ** 2) / 2
print("%7.2f %10d %12.2f %12.2f %14.2f %14.2f"
% (alpha, n, hit, hit_formula, miss, miss_formula))
print()
print("compare chaining at the same load factors, where an unsuccessful")
print("search costs alpha probes: 0.25, 0.50, 0.75, 0.90, 0.95.")
print("at alpha = 0.95 linear probing needs over a hundred probes for a")
print("failed search and chaining needs one. that gap is the price of")
print("keeping everything inside the array.")Linear Probing
alpha records hit found hit formula miss found miss formula
0.25 252 1.15 1.17 1.43 1.39
0.50 504 1.65 1.50 2.86 2.50
0.75 756 2.84 2.50 10.24 8.50
0.90 908 5.94 5.50 50.54 50.50
0.95 958 11.24 10.50 247.34 200.50
compare chaining at the same load factors, where an unsuccessful
search costs alpha probes: 0.25, 0.50, 0.75, 0.90, 0.95.
at alpha = 0.95 linear probing needs over a hundred probes for a
failed search and chaining needs one. that gap is the price of
keeping everything inside the array.Read the last two columns. At a load factor of 0.95 an unsuccessful search cost 247 probes, where chaining at the same load factor costs about one. This is why a linear probing table must be kept well under full, and chapter 107 puts a number on "well under".
Note also that the measured figures run above the formulas at high load: 11.2 against 10.5, and 247 against 200. That is expected and worth knowing. Both formulas are approximations derived for an idealised uniform hash on a large table, so they give the shape of the growth rather than an exact count for a particular 1009 slot table. The shape is what they are for, and the shape is confirmed: the failed search grows as the square.
The defect: a deleted slot cannot simply be cleared
EMPTY = None
M = 7
slots = [EMPTY] * M
# three keys that all hash to slot 1
for k in (1, 8, 15):
at = k % M
while slots[at] is not EMPTY:
at = (at + 1) % M
slots[at] = k
print("three keys, all 1 mod %d, inserted in order 1, 8, 15:" % M)
for i, cell in enumerate(slots):
print(" [%d] %s" % (i, cell if cell is not None else ""))
print()
def search(slots, key):
"""The standard search: stop at an EMPTY slot."""
m = len(slots)
at = key % m
for i in range(m):
here = (at + i) % m
if slots[here] is EMPTY:
return False, i + 1
if slots[here] == key:
return True, i + 1
return False, m
for k in (1, 8, 15):
found, probes = search(slots, k)
print(" search %-3d : found %-5s in %d probe(s)" % (k, found, probes))
print()
print("now delete 8 the obvious way, by clearing its slot:")
slots[slots.index(8)] = EMPTY
for i, cell in enumerate(slots):
print(" [%d] %s" % (i, cell if cell is not None else ""))
print()
found, probes = search(slots, 15)
print(" search 15 : found %s <-- but look at the table" % found)
print(" 15 is in the table at slot:", slots.index(15))
print(" the search stopped at the cleared slot 2 and reported absent.")
print()
print("a record is PRESENT and UNREACHABLE. nothing raised an error.")
print("this is the same class of bug as chapter 93's renumbering: the")
print("structure was changed under a rule the rest of the code relies on.")Linear Probing
three keys, all 1 mod 7, inserted in order 1, 8, 15:
[0]
[1] 1
[2] 8
[3] 15
[4]
[5]
[6]
search 1 : found True in 1 probe(s)
search 8 : found True in 2 probe(s)
search 15 : found True in 3 probe(s)
now delete 8 the obvious way, by clearing its slot:
[0]
[1] 1
[2]
[3] 15
[4]
[5]
[6]
search 15 : found False <-- but look at the table
15 is in the table at slot: 3
the search stopped at the cleared slot 2 and reported absent.
a record is PRESENT and UNREACHABLE. nothing raised an error.
this is the same class of bug as chapter 93's renumbering: the
structure was changed under a rule the rest of the code relies on.Fifteen is sitting in the table and search says it is not there, because clearing slot 2 broke the probe chain that led to it. An empty slot is a promise that nothing beyond it was displaced from before it, and clearing a slot breaks that promise.
The fix: a tombstone
Mark the slot deleted rather than empty. A search treats a deleted slot as "keep going"; an insert treats it as "you may use this". Three states, not two.
class Tombstone:
def __repr__(self):
return "DELETED"
EMPTY = None
DELETED = Tombstone()
M = 7
def build():
slots = [EMPTY] * M
for k in (1, 8, 15):
at = k % M
while slots[at] is not EMPTY and slots[at] is not DELETED:
at = (at + 1) % M
slots[at] = k
return slots
def search(slots, key):
"""A DELETED slot does not end the search. Only an EMPTY one does."""
m = len(slots)
for i in range(m):
here = (key % m + i) % m
if slots[here] is EMPTY:
return False, i + 1
if slots[here] is not DELETED and slots[here] == key:
return True, i + 1
return False, m
def delete(slots, key):
m = len(slots)
for i in range(m):
here = (key % m + i) % m
if slots[here] is EMPTY:
return False
if slots[here] is not DELETED and slots[here] == key:
slots[here] = DELETED # marked, NOT cleared
return True
return False
def insert(slots, key):
"""An insert MAY reuse a deleted slot, so space is not lost."""
m = len(slots)
for i in range(m):
here = (key % m + i) % m
if slots[here] is EMPTY or slots[here] is DELETED:
slots[here] = key
return here
raise RuntimeError("full")
slots = build()
print("delete 8 with a tombstone:", delete(slots, 8))
print("the table now:")
for i, cell in enumerate(slots):
print(" [%d] %s" % (i, cell if cell is not None else ""))
print()
for k in (1, 8, 15):
found, probes = search(slots, k)
print(" search %-3d : found %-5s in %d probe(s)" % (k, found, probes))
print()
print("15 is findable again:", search(slots, 15)[0])
print("8 is correctly absent:", search(slots, 8)[0] is False)
print()
print("and the deleted slot is reused rather than wasted:")
at = insert(slots, 22) # 22 mod 7 = 1
print(" inserted 22 at slot", at, "which held the tombstone:", at == 2)
for i, cell in enumerate(slots):
print(" [%d] %s" % (i, cell if cell is not None else ""))Linear Probing
delete 8 with a tombstone: True
the table now:
[0]
[1] 1
[2] DELETED
[3] 15
[4]
[5]
[6]
search 1 : found True in 1 probe(s)
search 8 : found False in 4 probe(s)
search 15 : found True in 3 probe(s)
15 is findable again: True
8 is correctly absent: True
and the deleted slot is reused rather than wasted:
inserted 22 at slot 2 which held the tombstone: True
[0]
[1] 1
[2] 22
[3] 15
[4]
[5]
[6]That is lazy deletion again, the same device chapter 93 used for a deleted vertex and chapter 98's heap used for a superseded distance. Three times in one module, which is why it is worth naming.
What tombstones cost
A tombstone occupies a slot for searching purposes but holds no record. So a table that has had many deletions can be mostly tombstones: searches stay slow although the table is nearly empty. The only cure is to rebuild the table, which is chapter 107's rehashing.
class Tombstone:
def __repr__(self):
return "DELETED"
EMPTY = None
DELETED = Tombstone()
M = 1009
def mix(i):
x = ((i + 1) * 2654435761) % (2 ** 32)
x ^= x >> 13
x = (x * 2246822519) % (2 ** 32)
x ^= x >> 17
return x
def fresh(n):
slots = [EMPTY] * M
keys = [mix(i) for i in range(n)]
for k in keys:
at = k % M
while slots[at] is not EMPTY:
at = (at + 1) % M
slots[at] = k
return slots, keys
def miss_probes(slots):
total = 0
absent = [mix(900000 + i) for i in range(400)]
for k in absent:
at, probes = k % M, 1
while slots[at] is not EMPTY:
at = (at + 1) % M
probes += 1
total += probes
return total / len(absent)
slots, keys = fresh(900) # alpha = 0.89
print("a table of %d slots holding %d records (alpha %.2f):" % (M, 900, 900 / M))
print(" failed search costs %.1f probes" % miss_probes(slots))
for k in keys[:800]: # delete 800 of the 900
at = k % M
while True:
if slots[at] is not DELETED and slots[at] == k:
slots[at] = DELETED
break
at = (at + 1) % M
live = sum(1 for s in slots if s is not EMPTY and s is not DELETED)
tombs = sum(1 for s in slots if s is DELETED)
print()
print("now 800 of them are deleted:")
print(" live records : %d (alpha %.2f)" % (live, live / M))
print(" tombstones : %d" % tombs)
print(" failed search costs %.1f probes" % miss_probes(slots))
print()
print("the table holds %d records in %d slots, which should be fast," % (live, M))
print("and a failed search is as slow as it was at alpha 0.89, because the")
print("tombstones still have to be walked past.")
print("only rebuilding the table clears them: chapter 107.")Linear Probing
a table of 1009 slots holding 900 records (alpha 0.89):
failed search costs 46.6 probes
now 800 of them are deleted:
live records : 100 (alpha 0.10)
tombstones : 800
failed search costs 46.6 probes
the table holds 100 records in 1009 slots, which should be fast,
and a failed search is as slow as it was at alpha 0.89, because the
tombstones still have to be walked past.
only rebuilding the table clears them: chapter 107.Advantages and disadvantages
Advantages.
No pointers at all, so no memory per record beyond the record, and the array of slots is the whole structure.
Excellent cache locality. The probe sequence walks consecutive array positions, which is the fastest possible memory access pattern. At moderate load factors this often makes linear probing faster in practice than chaining, despite chaining's better probe counts, and a good answer says so.
Simple to implement, with no second data structure.
Disadvantages.
Primary clustering, which snowballs rather than growing in proportion.
The load factor must stay below 1, and in practice well below: at 0.95 a failed search cost about two hundred probes.
Deletion needs tombstones, and tombstones accumulate, so a delete-heavy table must be rebuilt.
Linear Probing
It is far more sensitive to a poor hash function than chaining, because a cluster does not just lengthen a chain, it displaces other keys' records and spreads the damage.
Quick revision
- Linear probing is open addressing: every record lives in the array, so there are no pointers and the table can fill.
- The probe sequence is h(k), h(k)+1, h(k)+2 and so on, all mod m.
- A search stops at an EMPTY slot, because an insert would have stopped there too.
- Primary clustering: a key hashing anywhere inside a cluster joins its end, so long clusters grow faster than short ones and clusters merge.
- Costs: successful search about (1 + 1/(1-alpha))/2, unsuccessful about (1 + 1/(1-alpha) squared)/2, so a failed search blows up as the square.
- At alpha = 0.95 a failed search cost 247 probes against chaining's 1; the formulas are idealised approximations, so measured figures run above them at high load.
- Clearing a deleted slot breaks the probe chain: the chapter's listing left key 15 in the table with search reporting it absent.
- The fix is a tombstone: three states, empty, occupied and deleted. A search passes a tombstone; an insert may reuse it.
- Tombstones accumulate: a table with 100 live records and 800 tombstones searched as slowly as it did when nearly full. Only rehashing clears them.
- Advantages: no pointers and excellent cache locality, which often beats chaining in practice at moderate load.
- Disadvantages: clustering, alpha below 1, tombstones, and high sensitivity to a poor hash function.
Test yourself
1. What is open addressing, and what does it cost compared with chaining? Every record is stored inside the table array itself, with no external lists. The cost is that the table can fill up, so the load factor cannot exceed 1.
2. Give the probe sequence for linear probing. h_i(k) = (h(k) + i) mod m for i = 0, 1, 2 and so on, so h(k), then the next slot, then the next.
3. Why does a search stop at an empty slot? Because an insertion would have stopped at that slot too, so no key that hashes before it can have been placed beyond it.
4. Explain primary clustering and why it is worse than proportional growth. A cluster is a run of occupied slots. Any key hashing anywhere inside a cluster of length L is placed at its end, making it L+1, so long clusters attract more keys than short ones and adjacent clusters merge. Growth therefore accelerates.
5. Give both cost formulas and say which is worse near a full table. Successful search about (1 + 1/(1 - alpha))/2; unsuccessful about (1 + 1/(1 - alpha) squared)/2. The unsuccessful one is worse, because it grows as the square: the formula gives about 200 at alpha = 0.95 and a 1009 slot table measured 247, the formulas being idealised approximations.
Linear Probing
6. Show what goes wrong if a deleted slot is simply cleared. With 1, 8, 15 all hashing to slot 1 and placed in slots 1, 2, 3, clearing slot 2 to delete 8 makes a search for 15 stop at the now empty slot 2 and report absent, although 15 is still in slot 3.
7. What is a tombstone, and how do search and insert treat it? A marker meaning "a record was deleted here". A search passes over it and continues; an insert may place a new record in it.
8. What is the drawback of tombstones, and the cure? They occupy slots for searching but hold no record, so they accumulate and keep searches slow in a table that is nearly empty: 100 live records with 800 tombstones searched as slowly as 900 live records. The cure is to rebuild the table, which is rehashing.
9. Why is linear probing often faster than chaining in practice despite worse probe counts? Because its probes walk consecutive array positions, which suits the memory cache, while chaining follows pointers to scattered nodes.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.