Where Linear Probing Lands
Problem
A hash table has m slots numbered 0 to m - 1 and uses linear probing. Keys, all zero or more, are inserted in order: key k aims at slot k mod m, and if that slot is taken it tries the next one, wrapping from m - 1 back to 0, until it finds a free slot. There are never more keys than slots. Return the slot each key ends up in, and avoid re-walking long runs of taken slots, because a bad hash can pile every key onto one spot.
Examples
Input: m = 7, keys = [10, 3, 17, 24, 5]
Output: [3, 4, 5, 6, 0]
Why: 10, 3, 17 and 24 all aim at slot 3 and spread out to 3-6;
5 finds 5 and 6 taken and wraps around to 0Input: m = 5, keys = [4, 9, 14]
Output: [4, 0, 1]
Why: every key aims at slot 4, so the later ones wrap aroundInput: m = 1, keys = [42]
Output: [0]
Why: edge case, a one-slot table has only one place to goHints
0 / 3
Simulating the probes one slot at a time is correct, but when many keys aim at the same slot, the i-th of them walks past i - 1 taken slots, which adds up to quadratic work.
What a probe really wants to know is the first free slot at or after a given slot. After a slot is taken, that answer for it becomes the answer for the slot after it.
Keep a next-pointer for every slot, starting at itself. To place a key, follow pointers from its home slot until a slot points to itself, and compress the path you walked so it points straight there. Take that slot and point it at the following slot, wrapping at m.
Solution
Every taken slot is linked to the slot after it, so following links from a key's home slot always ends at the first free slot in probe order. That is a union-find structure where each free slot is the root of the run of taken slots before it. Path compression makes later walks over the same run jump straight to its end, so a pile-up is not re-walked once per key. With path compression alone, each placement costs O(log m) amortised, so time is O(m + n log m), and space is O(m).
def probe_slots(m, keys):
nxt = list(range(m)) # a slot at or after s that may still be free
def first_free(s):
root = s
while nxt[root] != root:
root = nxt[root]
while nxt[s] != root: # path compression
nxt[s], s = root, nxt[s]
return root
placed = []
for k in keys:
slot = first_free(k % m)
placed.append(slot)
nxt[slot] = (slot + 1) % m # taken: send later probes onwards
return placed
print(probe_slots(7, [10, 3, 17, 24, 5])) # -> [3, 4, 5, 6, 0]
print(probe_slots(5, [4, 9, 14])) # -> [4, 0, 1]
print(probe_slots(1, [42])) # -> [0]Stuck on the idea rather than the code? When Hashing Fails covers it.