Collision handling (chaining) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Collision handling (chaining)

Start: Insert key

↓

Compute hash index

↓

Check bucket at index

↓

Bucket empty?

Yes→Create new chain with key

↓

Insert key

↓

Bucket not empty?

No→Add key to existing chain

↓

Insertion done

When inserting a key, compute its hash index. If the bucket is empty, create a new chain with the key. If not, add the key to the existing chain at that bucket.

Execution Sample

Data Structures Theory

hash_table = [[] for _ in range(5)]
keys = [12, 7, 17]
for key in keys:
    index = key % 5
    hash_table[index].append(key)

Insert keys 12, 7, and 17 into a hash table of size 5 using chaining to handle collisions.

Analysis Table

Step	Key	Computed Index	Bucket State Before	Action	Bucket State After
1	12	2	[]	Bucket empty, create chain and insert 12	[12]
2	7	2	[12]	Bucket not empty, append 7 to chain	[12, 7]
3	17	2	[12, 7]	Bucket not empty, append 17 to chain	[12, 7, 17]
4	-	-	All buckets processed	Insertion complete	Final state: [[], [], [12, 7, 17], [], []]

💡 All keys inserted; chaining handled collisions by storing multiple keys in the same bucket list.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
hash_table	[[], [], [], [], []]	[[], [], [12], [], []]	[[], [], [12, 7], [], []]	[[], [], [12, 7, 17], [], []]	[[], [], [12, 7, 17], [], []]
index	-	2	2	2	-
key	-	12	7	17	-

Key Insights - 3 Insights

Why do multiple keys end up in the same bucket?

Because their hash indexes are the same (see execution_table steps 1-3 where index is 2), chaining stores them in a list at that bucket.

What happens if the bucket is empty when inserting a key?

A new list (chain) is created to hold the key, as shown in step 1 where the bucket was empty and key 12 was inserted.

How does chaining help with collisions?

Chaining stores all keys with the same hash index in a list, so no keys are lost or overwritten (see bucket state changes in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the bucket state after inserting key 7?

A [12]

B [12, 7]

C [7]

D []

💡 Hint

Check the 'Bucket State After' column at step 2 in execution_table.

At which step does the bucket first become non-empty?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'Bucket State Before' column; initially empty, then filled at step 1.

If the hash table size changed to 7, how would the computed index for key 17 change?

A Index would be 2

B Index would be 5

C Index would be 3

D Index would be 0

💡 Hint

Use modulo operation: 17 % 7 = 3; check 'Computed Index' logic in execution_table.

Concept Snapshot

Collision handling with chaining:
- Compute hash index for key
- If bucket empty, create new list and insert key
- If bucket not empty, append key to existing list
- Allows multiple keys per bucket to handle collisions
- Simple and effective method for collision resolution

Full Transcript

This visual execution trace shows how collision handling with chaining works in a hash table. When inserting keys, the hash index is computed using modulo operation. If the bucket at that index is empty, a new list (chain) is created and the key is inserted. If the bucket already contains keys, the new key is appended to the existing list. This way, multiple keys with the same hash index are stored together, preventing data loss due to collisions. The example inserts keys 12, 7, and 17 into a hash table of size 5, all mapping to index 2, demonstrating how chaining stores them in the same bucket list.

Practice

1. What is the main idea behind collision handling by chaining in hash tables?

easy

A. Use a second hash function to find a new index

B. Overwrite the existing item when a collision occurs

C. Resize the hash table immediately after a collision

D. Store collided items in a linked list at the same index

Solution

1. Step 1: Understand collision in hash tables

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain chaining method

   Chaining stores all collided items in a linked list at that index, preserving all entries.

3. Final Answer:

   Store collided items in a linked list at the same index -> Option D

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked lists hold collisions at one spot [OK]

Common Mistakes:

• Thinking collisions overwrite existing data
• Confusing chaining with open addressing
• Assuming resizing happens immediately on collision

2. Which of the following is the correct way to represent chaining in a hash table?

easy

A. Each index holds a single value only

B. Each index holds a linked list of values

C. Each index holds a separate hash table

D. Each index holds a fixed-size array of values

Solution

1. Step 1: Recall chaining structure

   Chaining uses linked lists to store multiple items at one index.

2. Step 2: Match options to chaining

   Only Each index holds a linked list of values describes linked lists at each index, which is chaining.

3. Final Answer:

   Each index holds a linked list of values -> Option B

4. Quick Check:

   Chaining = linked list per index [OK]

Hint: Chaining means linked lists at each hash index [OK]

Common Mistakes:

• Choosing single value per index (no chaining)
• Confusing chaining with nested hash tables
• Thinking arrays are used instead of lists

3. Consider a hash table using chaining with 5 buckets. The hash function is h(key) = key % 5. Insert keys 7, 12, 17, 22. What does the bucket at index 2 contain?

medium

A. [7, 12, 17, 22]

B. [7, 17]

C. [12, 22]

D. [2]

Solution

1. Step 1: Calculate hash for each key

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2, 22 % 5 = 2. All keys map to index 2.

2. Step 2: List keys in bucket 2

   Bucket 2 contains keys 7, 12, 17, 22.

3. Step 3: Verify which keys actually hash to 2

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2, 22 % 5 = 2. All keys map to index 2.

4. Step 4: Check options carefully

   [7, 17] lists [7, 17], but keys 12 and 22 also hash to 2, so [7, 17] is incomplete. [7, 12, 17, 22] lists all keys, which is correct.

5. Final Answer:

   [7, 12, 17, 22] -> Option A

6. Quick Check:

   All keys mod 5 = 2 [OK]

Hint: Apply mod function to keys to find bucket [OK]

Common Mistakes:

• Miscomputing modulo operation
• Assuming keys distribute to different buckets
• Confusing bucket index with key values

4. A hash table uses chaining but the linked list at one index is not updated correctly after insertion. What is the likely error?

medium

A. The new node is not linked to the existing list

B. The hash function returns different values for same key

C. The table size is too small

D. The keys are not unique

Solution

1. Step 1: Understand chaining insertion

   When inserting, the new node must link to the existing list at that index.

2. Step 2: Identify error from symptoms

   If the list is not updated, likely the new node was not linked properly.

3. Final Answer:

   The new node is not linked to the existing list -> Option A

4. Quick Check:

   Missing link causes list update failure [OK]

Hint: Check if new node links to list head [OK]

Common Mistakes:

• Blaming hash function for insertion errors
• Thinking table size causes linking issues
• Confusing key uniqueness with chaining errors

5. You have a hash table with chaining. If many keys hash to the same index, what is the best way to improve performance?

hard

A. Ignore collisions and overwrite old keys

B. Use a linked list with more nodes at that index

C. Increase the table size and rehash all keys

D. Store all keys in a single bucket

Solution

1. Step 1: Understand impact of many collisions

   Many keys in one bucket slow down search because linked list grows long.

2. Step 2: Improve performance by resizing

   Increasing table size reduces collisions by spreading keys across more buckets.

3. Step 3: Rehash keys after resizing

   Rehashing redistributes keys according to new table size for better balance.

4. Final Answer:

   Increase the table size and rehash all keys -> Option C

5. Quick Check:

   Resize + rehash reduces collisions [OK]

Hint: Resize table and rehash keys to reduce collisions [OK]

Common Mistakes:

• Adding more nodes without resizing
• Overwriting keys loses data
• Putting all keys in one bucket defeats hashing