Collision Handling Using Chaining in DSA C - 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. This means they want to be stored in the same spot.

beginner

Explain chaining as a collision handling method.

Chaining stores all elements that collide at the same index in a linked list. So, each slot in the hash table points to a list of items that share that index.

intermediate

How does chaining affect search time in a hash table?

Search time depends on the length of the linked list at the index. If many items collide, the list grows and search takes longer, but on average it stays fast if the table is sized well.

intermediate

What is the main advantage of using chaining over open addressing?

Chaining can handle any number of collisions without needing to resize the table immediately. It also makes deletion easier because items are stored in linked lists.

beginner

Describe the structure used in chaining for collision handling.

Each slot in the hash table contains a pointer to the head of a linked list. Each node in the list holds a key-value pair and a pointer to the next node.

What happens when two keys hash to the same index in chaining?

A One key overwrites the other

B The table resizes immediately

C They are stored in a linked list at that index

D The second key is discarded

In chaining, all keys that collide are stored in a linked list at the same index.

Which data structure is commonly used in chaining to handle collisions?

A Queue

B Array

C Stack

D Linked list

Chaining uses linked lists to store multiple elements at the same hash index.

What is a disadvantage of chaining?

A It wastes memory by storing empty slots

B Search time can degrade if many collisions occur

C It cannot handle collisions

D It does not allow deletion

If many keys collide, the linked list grows longer, making search slower.

In chaining, what does each node in the linked list store?

A Key, value, and pointer to next node

B Only the value

C Only the key

D Index of the hash table

Each node stores the key, value, and a pointer to the next node in the list.

Why is chaining preferred when the load factor is high?

A Because it avoids resizing the table immediately

B Because it uses less memory

C Because it stores keys in arrays

D Because it prevents collisions

Chaining allows multiple keys at the same index, so the table does not need to resize immediately when many keys are inserted.

Explain how collision handling using chaining works in a hash table.

Think about what happens when two keys want the same spot.

Describe the advantages and disadvantages of using chaining for collision handling.

Consider both performance and memory aspects.