Handling collisions: chaining, linear probing and rehashing

Separate chaining

Each slot holds a list (chain) of entries. Insert appends to the chain at the hashed index; find and remove search only that short chain. The table never fills up, but long chains slow it down.

class ChainedTable:
    def __init__(self, size):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def hash(self, key):
        return key % self.size

    def insert(self, key, value):
        bucket = self.buckets[self.hash(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])

    def find(self, key):
        for k, v in self.buckets[self.hash(key)]:
            if k == key:
                return v
        return None

    def remove(self, key):
        bucket = self.buckets[self.hash(key)]
        for pair in bucket:
            if pair[0] == key:
                bucket.remove(pair)
                return True
        return False

t = ChainedTable(5)
for k in [12, 7, 22, 4, 17]:
    t.insert(k, "item" + str(k))
print(t.buckets[2])
print(t.find(22), t.remove(7), t.buckets[2])

Output:

[[12, 'item12'], [7, 'item7'], [22, 'item22'], [17, 'item17']]
item22 True [[12, 'item12'], [22, 'item22'], [17, 'item17']]

Keys 12, 7, 22 and 17 all give 2 mod 5, so they share one chain.

Linear probing

Each slot holds one entry. If the hashed slot is taken, try the next slot, (i + 1) % size, until a free one is found. Find follows the same path and stops at an empty slot.

• Keys tend to bunch into runs of filled slots (clustering), lengthening searches.
• Removing a key must leave a tombstone marker (here 'DELETED'), not an empty slot; otherwise a later find would stop early and miss keys that probed past it.

Rehashing

When the load factor passes a threshold (0.7 below), create a larger table (often about double, ideally a prime size) and insert every existing key again, because each key's index depends on the table size. Tombstones are dropped in the process.

EMPTY, DELETED = None, "DELETED"

class ProbingTable:
    def __init__(self, size):
        self.size = size
        self.keys = [EMPTY] * size
        self.count = 0

    def insert(self, key):
        if self.count / self.size >= 0.7:
            self.rehash(self.size * 2 + 1)
        i = key % self.size
        while self.keys[i] not in (EMPTY, DELETED):
            if self.keys[i] == key:
                return
            i = (i + 1) % self.size          # linear probing
        self.keys[i] = key
        self.count = self.count + 1

    def find(self, key):
        i = key % self.size
        for _ in range(self.size):
            if self.keys[i] is EMPTY:
                return None
            if self.keys[i] == key:
                return i
            i = (i + 1) % self.size
        return None

    def remove(self, key):
        i = self.find(key)
        if i is not None:
            self.keys[i] = DELETED              # a tombstone keeps probe chains intact
            self.count = self.count - 1

    def rehash(self, new_size):
        old = [k for k in self.keys if k not in (EMPTY, DELETED)]
        self.size = new_size
        self.keys = [EMPTY] * new_size
        self.count = 0
        for k in old:
            self.insert(k)

# ProbingTable class as above

t = ProbingTable(7)
for k in [10, 17, 3, 24]:
    t.insert(k)
print(t.keys)
t.remove(17)
print(t.keys, t.find(24))
t.insert(31)
print(t.size, t.keys)

Output:

[None, None, None, 10, 17, 3, 24]
[None, None, None, 10, 'DELETED', 3, 24] 6
7 [None, None, None, 10, 31, 3, 24]

Comparing the methods

Worked example

Keys 5, 12 and 19 are inserted into a 7-slot table using key % 7 and linear probing. Where does each go?

1. 5 % 7 = 5: slot 5 is free.
2. 12 % 7 = 5: taken, so try slot 6: free.
3. 19 % 7 = 5: taken; slot 6 taken; (6 + 1) % 7 = 0: free.
4. Table: [19, None, None, None, None, 5, 12]

Answer: 5 in slot 5, 12 in slot 6, 19 wraps round to slot 0.

Check yourself

1. The ProbingTable class from the lesson is included in the code below. What does this print? ```python EMPTY, DELETED = None, "DELETED" class ProbingTable: def __init__(self, size): self.size = size self.keys = [EMPTY] * size self.count = 0 def insert(self, key): if self.count / self.size >= 0.7: self.rehash(self.size * 2 + 1) i = key % self.size while self.keys[i] not in (EMPTY, DELETED): if self.keys[i] == key: return i = (i + 1) % self.size # linear probing self.keys[i] = key self.count = self.count + 1 def find(self, key): i = key % self.size for _ in range(self.size): if self.keys[i] is EMPTY: return None if self.keys[i] == key: return i i = (i + 1) % self.size return None def remove(self, key): i = self.find(key) if i is not None: self.keys[i] = DELETED # a tombstone keeps probe chains intact self.count = self.count - 1 def rehash(self, new_size): old = [k for k in self.keys if k not in (EMPTY, DELETED)] self.size = new_size self.keys = [EMPTY] * new_size self.count = 0 for k in old: self.insert(k) t = ProbingTable(10) for k in [21, 31, 41]: t.insert(k) print(t.keys.index(41)) ```
   Show answer

   3. All three hash to 1. 21 takes slot 1, 31 probes to 2, 41 probes to `3`.

2. The ChainedTable class from the lesson is included in the code below. What does this print? ```python class ChainedTable: def __init__(self, size): self.size = size self.buckets = [[] for _ in range(size)] def hash(self, key): return key % self.size def insert(self, key, value): bucket = self.buckets[self.hash(key)] for pair in bucket: if pair[0] == key: pair[1] = value return bucket.append([key, value]) def find(self, key): for k, v in self.buckets[self.hash(key)]: if k == key: return v return None def remove(self, key): bucket = self.buckets[self.hash(key)] for pair in bucket: if pair[0] == key: bucket.remove(pair) return True return False t = ChainedTable(4) for k in [3, 7, 11, 8, 12]: t.insert(k, k) print([len(b) for b in t.buckets]) ```
   Show answer

   [2, 0, 0, 3]. mod 4: 3, 7 and 11 go to bucket 3; 8 and 12 to bucket 0. Output: `[2, 0, 0, 3]`

3. The ProbingTable class from the lesson is included in the code below. What does this print? ```python EMPTY, DELETED = None, "DELETED" class ProbingTable: def __init__(self, size): self.size = size self.keys = [EMPTY] * size self.count = 0 def insert(self, key): if self.count / self.size >= 0.7: self.rehash(self.size * 2 + 1) i = key % self.size while self.keys[i] not in (EMPTY, DELETED): if self.keys[i] == key: return i = (i + 1) % self.size # linear probing self.keys[i] = key self.count = self.count + 1 def find(self, key): i = key % self.size for _ in range(self.size): if self.keys[i] is EMPTY: return None if self.keys[i] == key: return i i = (i + 1) % self.size return None def remove(self, key): i = self.find(key) if i is not None: self.keys[i] = DELETED # a tombstone keeps probe chains intact self.count = self.count - 1 def rehash(self, new_size): old = [k for k in self.keys if k not in (EMPTY, DELETED)] self.size = new_size self.keys = [EMPTY] * new_size self.count = 0 for k in old: self.insert(k) t = ProbingTable(10) for k in [5, 15, 25]: t.insert(k) t.remove(15) print(t.find(25)) ```
   Show answer

   7. 25 probed from 5 past 15 to slot 7. The tombstone at slot 6 lets find keep going, so it returns `7`.

4. The ProbingTable class from the lesson is included in the code below. What does this print? ```python EMPTY, DELETED = None, "DELETED" class ProbingTable: def __init__(self, size): self.size = size self.keys = [EMPTY] * size self.count = 0 def insert(self, key): if self.count / self.size >= 0.7: self.rehash(self.size * 2 + 1) i = key % self.size while self.keys[i] not in (EMPTY, DELETED): if self.keys[i] == key: return i = (i + 1) % self.size # linear probing self.keys[i] = key self.count = self.count + 1 def find(self, key): i = key % self.size for _ in range(self.size): if self.keys[i] is EMPTY: return None if self.keys[i] == key: return i i = (i + 1) % self.size return None def remove(self, key): i = self.find(key) if i is not None: self.keys[i] = DELETED # a tombstone keeps probe chains intact self.count = self.count - 1 def rehash(self, new_size): old = [k for k in self.keys if k not in (EMPTY, DELETED)] self.size = new_size self.keys = [EMPTY] * new_size self.count = 0 for k in old: self.insert(k) t = ProbingTable(5) for k in [1, 2, 3, 4, 5]: t.insert(k) print(t.size) ```
   Show answer

   11. Before each insert the load factor is checked: 0, 0.2, 0.4 and 0.6 are fine, but before the 5th insert it is 4 / 5 = 0.8, so the table is rehashed to 5 x 2 + 1 = `11` slots.

5. A 11-slot table uses key % 11 with linear probing. Slots 3, 4 and 5 are full. Into which slot does key 36 go?
   Show answer

   6. 36 % 11 = 3. Slots 3, 4 and 5 are taken, so it goes in slot 6.

6. Why does linear probing mark a removed slot as DELETED instead of emptying it?
   • An empty slot would stop a later search too early, missing keys that probed past it
   • To save memory
   • So the table never needs rehashing
   • Because Python lists cannot hold None
   Show answer

   An empty slot would stop a later search too early, missing keys that probed past it. find stops at the first empty slot, so a gap in the middle of a probe chain would hide later keys.

7. What is clustering in a hash table that uses linear probing?
   • Keys with similar values are grouped in one chain
   • The table splits into several smaller tables
   • Filled slots form long runs, so new keys hashing anywhere in a run need many probes
   • Duplicate keys are stored together
   Show answer

   Filled slots form long runs, so new keys hashing anywhere in a run need many probes. Each collision fills the next slot, lengthening the run and making future collisions more likely.

8. When a table is rehashed into a larger list, why must every key be inserted again rather than copied to the same index?
   • The keys must be sorted first
   • Python cannot copy lists
   • Copying would duplicate the keys
   • Each key's index depends on the table size, so it changes when the size changes
   Show answer

   Each key's index depends on the table size, so it changes when the size changes. key % 7 and key % 15 usually differ, so old positions are wrong in the new table.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification, Issue 1 (March 2026)
• Pearson Edexcel IAL Computer Science Unit 4 Programming Language Subset (PLS)
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 and Unit 4)

Last updated 8 November 2026. Spotted a mistake? Tell us.