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

Recall & Review

beginner

What is collision in a hash table?

Collision happens when two different keys get the same index in the hash table. It means the spot is already taken.

beginner

What is open addressing in hash tables?

Open addressing is a way to handle collisions by finding another empty spot in the table instead of using linked lists.

beginner

How does linear probing work in open addressing?

Linear probing checks the next spots one by one (index + 1, index + 2, etc.) until it finds an empty spot to store the new key.

intermediate

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

Clustering can happen, where many keys group together, making searches slower because many spots are checked in a row.

intermediate

In linear probing, what happens if the table is full?

If the table is full, no empty spot is found, so insertion fails or the table needs to be resized.

What does linear probing do when a collision occurs?

A Deletes the existing key

B Creates a linked list at the same index

C Checks the next index until an empty spot is found

D Rehashes the entire table

Linear probing moves to the next index step by step to find an empty spot.

Which of these is a downside of linear probing?

A It can cause clustering of keys

B It deletes keys automatically

C It never handles collisions

D It uses extra memory for linked lists

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

In open addressing, what is stored in the hash table?

A Only keys

B Only values

C Keys and pointers to linked lists

D Keys directly in the table slots

Open addressing stores keys directly in the table slots, not using linked lists.

What happens if linear probing reaches the end of the table without finding an empty spot?

A It wraps around to the start of the table

B It stops and returns failure

C It deletes the first key

D It resizes the table automatically

Linear probing wraps around to the start of the table to continue searching for an empty spot.

Which method is NOT a collision handling technique?

A Chaining

B Binary search

C Linear probing

D Double hashing

Binary search is not used for collision handling in hash tables.

Explain how linear probing handles collisions in a hash table.

Think about what happens when the first spot is taken.

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

What happens when many keys group together?