Collision handling (open addressing) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is collision handling in open addressing?

Collision handling in open addressing is a method to resolve conflicts when two keys hash to the same index by finding another open slot within the hash table itself.

beginner

Name three common probing techniques used in open addressing.

The three common probing techniques are linear probing, quadratic probing, and double hashing.

beginner

How does linear probing work in open addressing?

Linear probing checks the next slot sequentially (index + 1, index + 2, etc.) until it finds an empty slot to place the new key.

intermediate

What problem can occur with linear probing and how is it called?

Linear probing can cause clustering, where groups of filled slots form, increasing search time. This is called primary clustering.

intermediate

Explain double hashing in open addressing.

Double hashing uses a second hash function to calculate the step size for probing, reducing clustering by spreading out keys more evenly.

What does open addressing do when a collision occurs?

A Finds another empty slot in the hash table

B Stores the key in a linked list

C Deletes the existing key

D Ignores the new key

Open addressing resolves collisions by searching for another empty slot within the hash table.

Which probing method checks slots sequentially after a collision?

A Linear probing

B Double hashing

C Quadratic probing

D Separate chaining

Linear probing checks the next slots one by one in order.

What is the main disadvantage of linear probing?

A Slow hash function

B Secondary clustering

C High memory usage

D Primary clustering

Linear probing can cause primary clustering, where filled slots group together and slow down operations.

Which technique uses a second hash function to find the next slot?

A Quadratic probing

B Linear probing

C Double hashing

D Separate chaining

Double hashing uses a second hash function to calculate the step size for probing.

In open addressing, what happens if the table is full?

A Keys are stored outside the table

B Insertion fails because no empty slot is available

C The table automatically expands

D Old keys are overwritten

If the hash table is full, open addressing cannot insert new keys because no empty slots remain.

Describe how open addressing handles collisions in a hash table.

Think about how the table itself is used to resolve conflicts.

Compare linear probing and double hashing as collision handling methods.

Focus on how they find the next slot and their impact on clustering.