Collision Handling Using Open Addressing Linear Probing in DSA Python

Mental Model

When two items want the same spot in a table, we look for the next empty spot in order until we find one.

Analogy: Imagine parking cars in a row of parking spots. If your favorite spot is taken, you move forward one spot at a time until you find an empty one to park.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Table: [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Dry Run Walkthrough

Input: Insert keys 10, 20, 30 into a hash table of size 10 using linear probing. Hash function: key % 10.

Goal: Insert all keys without overwriting existing keys by finding the next free spot when collision happens.

Step 1: Insert key 10 at index 0 (10 % 10 = 0).

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Table: [10] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Index 0 is free, so we place 10 there.

Step 2: Insert key 20 at index 0 (20 % 10 = 0), but index 0 is occupied, so move to index 1.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Table: [10] -> [20] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Index 0 is taken, so linear probing moves to next index 1 which is free.

Step 3: Insert key 30 at index 0 (30 % 10 = 0), indexes 0 and 1 are occupied, so move to index 2.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Table: [10] -> [20] -> [30] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Indexes 0 and 1 are taken, so linear probing moves to next free index 2.

Result:

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Table: [10] -> [20] -> [30] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Annotated Code

DSA Python

class LinearProbingHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size

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

    def insert(self, key):
        index = self.hash_function(key)
        start_index = index
        while self.table[index] is not None:
            index = (index + 1) % self.size  # move to next index
            if index == start_index:  # table full
                raise Exception("Hash table is full")
        self.table[index] = key

    def __str__(self):
        result = []
        for i, val in enumerate(self.table):
            if val is None:
                result.append(f"[{i}]: Empty")
            else:
                result.append(f"[{i}]: {val}")
        return ' -> '.join(result)

# Driver code
hash_table = LinearProbingHashTable()
hash_table.insert(10)
hash_table.insert(20)
hash_table.insert(30)
print(hash_table)

index = self.hash_function(key)

Calculate initial index using hash function

while self.table[index] is not None:

Check if current index is occupied to handle collision

index = (index + 1) % self.size # move to next index

Move to next index using linear probing

if index == start_index: # table full

Detect full table to avoid infinite loop

self.table[index] = key

Insert key at found free index

Output

[0]: 10 -> [1]: 20 -> [2]: 30 -> [3]: Empty -> [4]: Empty -> [5]: Empty -> [6]: Empty -> [7]: Empty -> [8]: Empty -> [9]: Empty

Complexity Analysis

Time: O(n) in worst case because we may check every slot if many collisions happen.

Space: O(n) because we store up to n keys in the table array.

vs Alternative: Compared to chaining (linked lists), linear probing uses less memory but can have clustering causing slower searches.

Edge Cases

Inserting into a full table

Raises an exception to indicate no free slot is available.

DSA Python

if index == start_index:  # table full

Inserting a key when table is empty

Key is inserted directly at hashed index without probing.

DSA Python

while self.table[index] is not None:

Inserting keys that hash to the same index

Linear probing finds next free slot to avoid overwriting existing keys.

DSA Python

index = (index + 1) % self.size  # move to next index

When to Use This Pattern

When you see a hash table with collisions and need to store all keys in one array, use linear probing to find the next free slot by checking sequentially.

Common Mistakes

Mistake: Not wrapping around the table when reaching the end during probing.
Fix: Use modulo operation to wrap index back to start: index = (index + 1) % size.

Mistake: Not checking for full table and causing infinite loop.
Fix: Keep track of start index and stop probing if we return to it.

Summary

It handles collisions by moving forward to find the next empty slot in the hash table.

Use it when you want to store keys in a fixed-size array and handle collisions without extra memory.

The key insight is to keep checking the next slot until you find an empty one, wrapping around the table if needed.

Practice

1. What is the main idea behind linear probing in collision handling for hash tables?

easy

A. Double the size of the hash table when a collision occurs.

B. If a slot is occupied, check the next slot sequentially until an empty one is found.

C. Use a linked list at each slot to store multiple elements.

D. Rehash all elements using a new hash function.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in order if the original slot is taken.

2. Step 2: Compare with other methods

   Other methods like chaining use linked lists, resizing, or rehashing, which are different from linear probing.

3. Final Answer:

   If a slot is occupied, check the next slot sequentially until an empty one is found. -> Option B

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot until free [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing resizes the table
• Assuming rehashing is part of linear probing

2. Which of the following is the correct way to calculate the next index in linear probing for a hash table of size m when a collision occurs at index i?

easy

A. (i + 2) % m

B. (i * 2) % m

C. (i + 1) % m

D. (i - 1) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index and taking modulo with table size.

2. Step 2: Apply modulo for wrap-around

   Using modulo ensures the index wraps around to the start if it reaches the end of the table.

3. Final Answer:

   (i + 1) % m -> Option C

4. Quick Check:

   Next index = (current + 1) mod size [OK]

Hint: Next slot = (current index + 1) mod table size [OK]

Common Mistakes:

• Adding 2 instead of 1 for next index
• Multiplying index instead of adding
• Not using modulo for wrap-around

3. Consider a hash table of size 5 using linear probing. The hash function is h(k) = k % 5. Insert keys 7, 12, 17 in order. What is the final state of the table?

medium

A. [None, None, 7, 12, 17]

B. [7, 12, 17, None, None]

C. [None, 7, 12, 17, None]

D. [7, None, 12, 17, None]

Solution

1. Step 1: Calculate initial positions

   h(7) = 7 % 5 = 2, h(12) = 12 % 5 = 2, h(17) = 17 % 5 = 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is taken, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are taken, so insert at index 4.

3. Final Answer:

   [None, None, 7, 12, 17] -> Option A

4. Quick Check:

   Keys placed at 2, 3, 4 with linear probing [OK]

Hint: Check hash index, then next free slot sequentially [OK]

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not probing to next slot after collision
• Miscomputing hash values

4. The following code snippet tries to insert keys into a hash table using linear probing. What is the bug?

def insert(table, key):
    m = len(table)
    index = key % m
    while table[index] is not None:
        index = (index + 1) % m
    table[index] = key

hash_table = [None]*5
insert(hash_table, 5)
insert(hash_table, 10)
insert(hash_table, 15)
insert(hash_table, 20)
insert(hash_table, 25)
insert(hash_table, 30)

medium

A. Infinite loop if table is full because no stop condition in while loop.

B. No bug; code works correctly for all insertions.

C. Wrong hash function used; should be key // m.

D. Table size should be dynamic, not fixed.

Solution

1. Step 1: Analyze insertion loop

   The while loop continues probing until it finds an empty slot but has no check for full table.

2. Step 2: Identify problem when table is full

   If all slots are occupied, the loop cycles endlessly, causing infinite loop.

3. Final Answer:

   Infinite loop if table is full because no stop condition in while loop. -> Option A

4. Quick Check:

   Full table causes infinite loop without exit [OK]

Hint: Check for full table to avoid infinite loop [OK]

Common Mistakes:

• Assuming hash function is wrong
• Ignoring infinite loop possibility
• Thinking dynamic size fixes this bug

5. You have a hash table of size 7 using linear probing. Insert keys [14, 21, 28, 35, 42] using hash function h(k) = k % 7. After all insertions, what is the index of key 42 in the table?

hard

A. 5

B. 0

C. 6

D. 4

Solution

1. Step 1: Calculate initial hash indices

   h(14)=0, h(21)=0, h(28)=0, h(35)=0, h(42)=0 (all keys hash to index 0).

2. Step 2: Insert keys using linear probing

   Insert 14 at 0. For 21, index 0 taken, try 1. Insert 21 at 1. For 28, indices 0 and 1 taken, insert at 2. For 35, insert at 3. For 42, insert at 4.

3. Step 3: Find index of key 42

   Key 42 is at index 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   42 placed at first free slot after collisions [OK]

Hint: All keys collide; count steps from initial index [OK]

Common Mistakes:

• Assuming key stays at initial hash index
• Not probing sequentially after collisions
• Miscounting index after multiple collisions