Collision handling (open addressing) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Linear Probing in Open Addressing

In open addressing, linear probing is a collision resolution technique. What happens when a collision occurs during insertion?

A The algorithm checks the next slot sequentially until an empty slot is found.

B The algorithm immediately resizes the hash table to avoid collisions.

C The algorithm stores the new item in a linked list at the collided slot.

D The algorithm discards the new item and keeps the existing one.

💡 Hint

Think about how linear probing searches for the next available position.

Linear probing resolves collisions by checking the next slot in the table sequentially until it finds an empty slot to insert the new item.

📋 Factual

intermediate

Maximum Number of Probes in Quadratic Probing

In quadratic probing, what is the maximum number of probes needed to find an empty slot in a hash table of size m (where m is prime and the table is less than half full)?

A At most <strong>m/2</strong> probes

B At most <strong>m</strong> probes

C At most <strong>√m</strong> probes

D At most <strong>log m</strong> probes

💡 Hint

Consider the properties of quadratic probing and the load factor.

When the table size m is prime and the load factor is less than 0.5, quadratic probing guarantees finding an empty slot within at most m/2 probes.

🔍 Analysis

advanced

Analyzing Double Hashing Probe Sequence

Given a hash table of size 11, and two hash functions h1(key) = key % 11 and h2(key) = 1 + (key % 10), what is the probe sequence for inserting key 27 using double hashing?

A 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1

B 5, 2, 10, 7, 4, 1, 9, 6, 3, 0, 8

C 5, 6, 7, 8, 9, 10, 0, 1, 2, 3

D 2, 4, 6, 8, 10, 1, 3, 5, 7, 9, 0

💡 Hint

Calculate h1(27) and h2(27), then apply the formula (h1(key) + i * h2(key)) % 11 for i = 0, 1, 2, ...

Calculate h1(27) = 27 % 11 = 5 and h2(27) = 1 + (27 % 10) = 1 + 7 = 8. The probe sequence is (5 + i*8) % 11 for i = 0..10, which results in 5, 2, 10, 7, 4, 1, 9, 6, 3, 0, 8.

❓ Comparison

advanced

Comparing Clustering Effects in Open Addressing

Which collision handling method in open addressing is least prone to primary clustering?

A Linear probing

B Quadratic probing

C Double hashing

D Separate chaining

💡 Hint

Consider how the probe sequences differ and how clustering forms.

Double hashing uses a second hash function to calculate probe steps, which spreads out keys more evenly and reduces primary clustering compared to linear and quadratic probing.

❓ Reasoning

expert

Reasoning About Deletion in Open Addressing

Why is deletion in open addressing hash tables more complicated than insertion or search?

A Because deletion is not allowed in open addressing hash tables.

B Because deletion requires resizing the hash table immediately.

C Because deleted slots must be replaced with null values to maintain table size.

D Because removing an element can break the probe sequence, causing search failures for other keys.

💡 Hint

Think about how probe sequences depend on continuous slots.

Deleting an element by simply clearing its slot can break the probe sequence, causing searches for other keys that collided and were placed further along to fail. Special markers (like 'deleted' flags) are used to avoid this problem.

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