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.