Collision Handling Using Open Addressing Linear Probing in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is collision in a hash table?

Collision happens when two different keys hash to the same index in the hash table.

beginner

What does 'open addressing' mean in collision handling?

Open addressing means finding another empty spot in the hash table when a collision occurs, instead of using linked lists.

beginner

How does linear probing work in open addressing?

Linear probing checks the next slot in the table one by one until it finds an empty slot to place the new key.

intermediate

What problem can linear probing cause if many collisions happen?

Linear probing can cause clustering, where many keys group together, making search slower.

beginner

In linear probing, how do you find a key during search?

Start at the hashed index and check slots one by one until you find the key or an empty slot (meaning key not present).

What happens when a collision occurs in open addressing with linear probing?

A Discard the new key

B Create a linked list at the collided slot

C Insert the key in the next available slot sequentially

D Resize the hash table immediately

Linear probing inserts the key in the next available slot by checking slots one by one.

Which of these is a downside of linear probing?

A It can cause clustering of keys

B It never handles collisions

C It uses extra memory for linked lists

D It requires complex data structures

Linear probing can cause clustering, where many keys group together, slowing down operations.

How do you know a key is not in the hash table when searching with linear probing?

A When the table is full

B When you reach the end of the table

C When you find a different key

D When you find an empty slot during probing

Finding an empty slot during probing means the key was never inserted.

What is the first step in inserting a key using linear probing?

A Search the entire table

B Hash the key to get an index

C Resize the table

D Delete an existing key

You first hash the key to find the initial index to try inserting.

If the hashed index is occupied, what does linear probing do next?

A Check the next index (index + 1)

B Stop and fail insertion

C Jump to a random index

D Use a linked list at that index

Linear probing checks the next index sequentially until it finds an empty slot.

Explain how collision handling works using open addressing with linear probing.

Think about what happens when two keys want the same spot and how linear probing finds a new spot.

Describe the main advantage and disadvantage of using linear probing for collision handling.

Consider memory use and performance impact.