Collision handling (open addressing) in Data Structures Theory - Full Explanation

Introduction

Imagine you have a box with many compartments to store your keys, but sometimes two keys want to go into the same compartment. This problem is called a collision. We need a way to find another empty compartment quickly without losing any keys.

Explanation

What is a collision?

A collision happens when two different items are assigned to the same spot in a storage system, like a hash table. Since each spot can hold only one item, we must find a way to handle this conflict.

A collision means two items want the same storage spot.

Open addressing method

Open addressing handles collisions by looking for another empty spot in the storage. Instead of using extra space, it searches through the storage itself to find a free compartment for the new item.

Open addressing finds a new spot inside the storage when a collision occurs.

Linear probing

Linear probing checks the next compartments one by one until it finds an empty one. If the first spot is taken, it tries the next, then the next, and so on, wrapping around to the start if needed.

Linear probing searches sequentially for the next free spot.

Quadratic probing

Quadratic probing jumps through compartments using a formula that squares the step number. This means it checks spots farther away in a pattern like 1, 4, 9 steps away, reducing clustering compared to linear probing.

Quadratic probing uses squared steps to spread out searches for free spots.

Double hashing

Double hashing uses a second formula to decide how far to jump when searching for an empty spot. This makes the search pattern less predictable and helps avoid clusters of filled spots.

Double hashing uses two formulas to find empty spots and reduce clustering.

Limitations of open addressing

Open addressing works well when the storage is not too full. If it gets crowded, finding empty spots takes longer, and performance drops. Also, deleting items can be tricky because empty spots might break the search chain.

Open addressing slows down when storage is nearly full and deletion is complex.

Real World Analogy

Imagine a parking lot where each car has a preferred parking spot. If that spot is taken, the driver looks for the next available spot nearby, either by checking spots one by one, jumping farther away in a pattern, or using a special rule to find a free space.

Collision → Two cars arriving at the same parking spot at the same time

Open addressing → Driver searching for another empty parking spot within the lot

Linear probing → Driver checking each parking spot one by one until finding an empty one

Quadratic probing → Driver skipping spots in a pattern like 1, 4, 9 spots away to find a free space

Double hashing → Driver using a second rule to decide how far to jump to find an empty spot

Limitations of open addressing → Parking lot getting full, making it harder and slower to find empty spots

Diagram

Diagram

┌───────────────┐
│ Hash Table    │
├───────────────┤
│ [0] Item A    │
│ [1] Item B    │
│ [2] Collision │
│ [3] Empty     │
│ [4] Empty     │
│ [5] Empty     │
└───────────────┘

Collision at [2] → check next spots:
[3] empty → place item here (linear probing)

Search pattern:
[2] → [3] → [4] → [5] ...

This diagram shows a hash table with a collision at position 2 and how linear probing finds the next empty spot at position 3.

Key Facts

Collision → When two items are assigned to the same storage location.

Open addressing → A collision handling method that searches for empty spots within the storage.

Linear probing → A technique that checks the next slots one by one to resolve collisions.

Quadratic probing → A technique that checks slots at increasing squared distances to reduce clustering.

Double hashing → A technique that uses a second hash function to determine jump steps for collision resolution.

Code Example

Data Structures Theory

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

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

    def linear_probe(self, key):
        index = self.hash(key)
        start_index = index
        while self.table[index] is not None:
            index = (index + 1) % self.size
            if index == start_index:
                raise Exception('Hash table is full')
        return index

    def insert(self, key):
        index = self.hash(key)
        if self.table[index] is None:
            self.table[index] = key
        else:
            new_index = self.linear_probe(key)
            self.table[new_index] = key

    def __str__(self):
        return str(self.table)

# Example usage
ht = OpenAddressingHashTable(5)
ht.insert(1)
ht.insert(6)  # Collision with 1, linear probe to next spot
ht.insert(11) # Collision again, linear probe further
print(ht)

Common Confusions

Believing open addressing uses extra storage space to handle collisions.

Believing open addressing uses extra storage space to handle collisions. Open addressing resolves collisions by searching within the existing storage, not by using extra space like separate chaining.

Thinking linear probing always finds an empty spot quickly regardless of table fullness.

Thinking linear probing always finds an empty spot quickly regardless of table fullness. Linear probing slows down significantly as the table gets full because it may need to check many spots sequentially.

Assuming deletion in open addressing is as simple as clearing a spot.

Assuming deletion in open addressing is as simple as clearing a spot. Deleting items requires special handling to avoid breaking the search chain, often using markers instead of clearing spots.

Summary

Collisions happen when two items want the same storage spot, and open addressing solves this by searching for empty spots inside the storage.

Linear probing checks spots one by one, quadratic probing uses squared steps, and double hashing uses a second formula to find free spots.

Open addressing works best when the storage is not too full, and deleting items requires careful handling to keep searches working.

Practice

1. What is the main idea behind open addressing in collision handling?

easy

A. Find another empty spot in the hash table when a collision occurs

B. Store collided elements in a separate linked list

C. Use multiple hash functions to avoid collisions

D. Resize the hash table immediately after a collision

Solution

1. Step 1: Understand collision handling methods

   Open addressing handles collisions by searching for another empty slot inside the hash table itself.

2. Step 2: Compare with other methods

   Unlike chaining (which uses linked lists), open addressing keeps all data inside the array by probing for free spots.

3. Final Answer:

   Find another empty spot in the hash table when a collision occurs -> Option A

4. Quick Check:

   Open addressing = find empty spot inside table [OK]

Hint: Open addressing means searching inside the table for free spots [OK]

Common Mistakes:

• Confusing open addressing with chaining
• Thinking collisions are ignored
• Assuming resizing happens immediately on collision

2. Which of the following is the correct syntax to start linear probing from index i in a hash table of size m?

easy

A. next_index = (i - 1) % m

B. next_index = (i * 2) % m

C. next_index = (i + 1) % m

D. next_index = (i + m) % 2

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index and wrapping around using modulo.

2. Step 2: Apply modulo with table size

   To stay within the table size, use (i + 1) % m, where m is the table size.

3. Final Answer:

   next_index = (i + 1) % m -> Option C

4. Quick Check:

   Linear probing = increment index by 1 modulo table size [OK]

Hint: Linear probing adds 1 and wraps with modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Incorrect modulo divisor
• Subtracting instead of adding

3. Given a hash table of size 5 and a hash function h(k) = k % 5, if keys 7, 12, and 17 are inserted using linear probing, what will be the final index of key 17?

medium

A. 3

B. 2

C. 0

D. 4

Solution

1. Step 1: Calculate initial hash indices

   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 3 (free). Insert 12 at 3. For 17, indices 2 and 3 are taken, try 4 (free). Insert 17 at 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Linear probing moves to next free slot: 17 at index 4 [OK]

Hint: Check initial hash, then probe next slots until free [OK]

Common Mistakes:

• Assuming all keys go to same index
• Not probing after collision
• Miscomputing modulo

4. What is the main problem with this linear probing insertion code snippet?

table = [None]*5
key = 12
index = key % 5
while table[index] is not None:
    index = (index + 1) % 5
# Missing insertion step here

medium

A. It never inserts the key into the table

B. It causes an infinite loop even if the table has empty slots

C. It uses wrong modulo operation

D. It overwrites existing keys without checking

Solution

1. Step 1: Analyze the loop behavior

   The loop finds the next free slot by incrementing index until it finds None.

2. Step 2: Check for insertion after loop

   After the loop, the code does not insert the key into the found free slot, so the key is never stored.

3. Final Answer:

   It never inserts the key into the table -> Option A

4. Quick Check:

   Missing insertion step means key not stored [OK]

Hint: Always insert key after finding free slot [OK]

Common Mistakes:

• Forgetting to insert after probing
• Ignoring full table infinite loop
• Wrong modulo usage

5. In a hash table using open addressing with linear probing, what happens if the table becomes completely full and you try to insert a new key?

hard

A. The new key overwrites the oldest key in the table

B. The insertion fails because no empty slot is available

C. The table automatically resizes and rehashes all keys

D. The insertion loops infinitely without stopping

Solution

1. Step 1: Understand open addressing limits

   Open addressing requires an empty slot to insert a new key by probing.

2. Step 2: Consider full table scenario

   If the table is full, no empty slot exists, so insertion cannot proceed and must fail or trigger resizing externally.

3. Final Answer:

   The insertion fails because no empty slot is available -> Option B

4. Quick Check:

   Full table means no free slot, insertion fails [OK]

Hint: Full table means no free slot, insertion fails [OK]

Common Mistakes:

• Assuming automatic resizing always happens
• Thinking keys get overwritten silently
• Ignoring infinite loop possibility