Collision Handling Using Chaining in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the hash table with empty lists for chaining.

DSA Python

hash_table = [[] for _ in [1](10)]

Drag options to blanks, or click blank then click option'

Adict

Blist

Cset

Drange

Attempts:

3 left

💡 Hint

Common Mistakes

Using dict() or set() instead of range() causes errors.

Using list() creates an empty list, not a range.

We use range(10) to create 10 empty lists for chaining in the hash table.

2fill in blank

medium

Complete the code to compute the hash index for a given key.

DSA Python

index = hash(key) [1] len(hash_table)

Drag options to blanks, or click blank then click option'

A%

B+

C//

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using + or * can produce indexes outside the table range.

Using // gives the quotient, not the remainder.

We use modulo (%) to ensure the index fits within the hash table size.

3fill in blank

hard

Fix the error in the code that inserts a key-value pair into the hash table using chaining.

DSA Python

def insert(hash_table, key, value):
    index = hash(key) % len(hash_table)
    for i, (k, v) in enumerate(hash_table[index]):
        if k == key:
            hash_table[index][i] = (key, [1])
            return
    hash_table[index].append((key, value))

Drag options to blanks, or click blank then click option'

Akey

Bvalue

Cindex

Dhash_table

Attempts:

3 left

💡 Hint

Common Mistakes

Replacing with key instead of value loses the actual data.

Using index or hash_table as value causes errors.

We update the value for the existing key, so we replace with (key, value).

4fill in blank

hard

Fill both blanks to complete the search function that returns the value for a given key or None if not found.

DSA Python

def search(hash_table, key):
    index = hash(key) [1] len(hash_table)
    for k, v in hash_table[[2]]:
        if k == key:
            return v
    return None

Drag options to blanks, or click blank then click option'

A%

B+

Cindex

Dkey

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of % causes index errors.

Using key instead of index to access the bucket causes runtime errors.

We use modulo (%) to get the index, then look in hash_table[index] for the key.

5fill in blank

hard

Fill all three blanks to complete the delete function that removes a key-value pair from the hash table.

DSA Python

def delete(hash_table, key):
    index = hash(key) [1] len(hash_table)
    for i, (k, v) in enumerate(hash_table[[2]]):
        if k == [3]:
            del hash_table[index][i]
            return True
    return False

Drag options to blanks, or click blank then click option'

A%

B+

Ckey

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of % causes wrong index.

Using key instead of index to access bucket causes errors.

Comparing k to index instead of key causes logic errors.

We compute index with %, access bucket with index, and compare k to key to delete.

Practice

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

easy

A. Store collided elements in a linked list at the same index

B. Replace the existing element with the new one

C. Resize the hash table immediately

D. Ignore the new element causing collision

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index, allowing multiple elements to share the same slot.

3. Final Answer:

   Store collided elements in a linked list at the same index -> Option A

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Remember: chaining uses linked lists to store collisions [OK]

Common Mistakes:

• Thinking collisions replace existing elements
• Assuming collisions are ignored
• Believing resizing happens immediately on collision

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

easy

A. hash_table = dict()

B. hash_table = [None] * size

C. hash_table = [0] * size

D. hash_table = [[] for _ in range(size)]

Solution

1. Step 1: Understand chaining initialization

   Chaining requires each slot to hold a list to store multiple elements.

2. Step 2: Choose correct initialization

   Using list comprehension to create a list of empty lists ensures each slot can hold multiple elements.

3. Final Answer:

   hash_table = [[] for _ in range(size)] -> Option D

4. Quick Check:

   Empty lists per slot = hash_table = [[] for _ in range(size)] [OK]

Hint: Use list of empty lists for chaining slots [OK]

Common Mistakes:

• Using [None] * size creates references to same list
• Using zeros instead of lists for chaining
• Using dict() which is not a list-based hash table

3. Consider the following code using chaining for collision handling:

hash_table = [[] for _ in range(3)]
keys = [5, 8, 11]
for key in keys:
    index = key % 3
    hash_table[index].append(key)
print(hash_table)

What is the output?

medium

A. [[5, 8, 11], [], []]

B. [[], [], [5, 8, 11]]

C. [[], [5, 8, 11], []]

D. [[], [5], [8, 11]]

Solution

1. Step 1: Calculate indices for each key

   5 % 3 = 2, 8 % 3 = 2, 11 % 3 = 2. All keys map to index 2.

2. Step 2: Append keys to corresponding lists

   All keys 5, 8, 11 are appended to hash_table[2], so hash_table = [[], [], [5, 8, 11]].

3. Final Answer:

   [[], [], [5, 8, 11]] -> Option B

4. Quick Check:

   Keys mod 3 = 2, all in last list [OK]

Hint: Calculate key % size to find index, then append [OK]

Common Mistakes:

• Miscomputing modulo operation
• Appending keys to wrong index
• Confusing list positions in output

4. Find the error in this chaining insertion code:

hash_table = [[]] * 4
key = 10
index = key % 4
hash_table[index].append(key)
print(hash_table)

medium

A. Modulo operation is incorrect

B. Append method is not valid for lists

C. Using [[]] * 4 creates references to the same list

D. Index calculation should be key % 3

Solution

1. Step 1: Understand list multiplication behavior

   Using [[]] * 4 creates 4 references to the same inner list, not 4 separate lists.

2. Step 2: Effect on append operation

   Appending to one index appends to all because all slots point to the same list.

3. Final Answer:

   Using [[]] * 4 creates references to the same list -> Option C

4. Quick Check:

   List multiplication duplicates references [OK]

Hint: Use list comprehension for separate lists, not multiplication [OK]

Common Mistakes:

• Assuming [[]] * 4 creates independent lists
• Incorrect modulo calculation
• Misunderstanding append method usage

5. You have a hash table of size 5 using chaining. Insert keys [7, 12, 17, 22, 27]. After insertion, what is the structure of the hash table?

hard

A. [[], [], [7, 12, 17, 22, 27], [], []]

B. [[], [7, 12, 17, 22, 27], [], [], []]

C. [[], [], [], [7, 12, 17, 22, 27], []]

D. [[7, 12, 17, 22, 27], [], [], [], []]

Solution

1. Step 1: Calculate index for each key using modulo 5

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

2. Step 2: Insert keys at index 2

   All keys are appended to the list at index 2, so hash_table = [[], [], [7, 12, 17, 22, 27], [], []].

3. Final Answer:

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

4. Quick Check:

   All keys mod 5 = 2, stored at index 2 [OK]

Hint: Calculate key % size to find correct bucket [OK]

Common Mistakes:

• Miscomputing modulo results
• Placing keys in wrong index
• Confusing list positions in output