Collision Handling Using Chaining in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys with collisions in chaining hash table

What is the printed state of the hash table buckets after inserting keys 1, 11, and 21 into a hash table of size 10 using chaining with hash function key % 10?

DSA Go

package main

import (
	"fmt"
)

type Node struct {
	key  int
	next *Node
}

type HashTable struct {
	size   int
	buckets []*Node
}

func NewHashTable(size int) *HashTable {
	return &HashTable{
		size:   size,
		buckets: make([]*Node, size),
	}
}

func (ht *HashTable) hash(key int) int {
	return key % ht.size
}

func (ht *HashTable) Insert(key int) {
	index := ht.hash(key)
	newNode := &Node{key: key}
	if ht.buckets[index] == nil {
		ht.buckets[index] = newNode
	} else {
		current := ht.buckets[index]
		for current.next != nil {
			current = current.next
		}
		current.next = newNode
	}
}

func (ht *HashTable) Print() {
	for i, node := range ht.buckets {
		fmt.Printf("Bucket %d: ", i)
		current := node
		for current != nil {
			fmt.Printf("%d -> ", current.key)
			current = current.next
		}
		fmt.Println("null")
	}
}

func main() {
	ht := NewHashTable(10)
	ht.Insert(1)
	ht.Insert(11)
	ht.Insert(21)
	ht.Print()
}

A

Bucket 0: null
Bucket 1: 1 -> 11 -> 21 -> null
Bucket 2: null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

B

Bucket 0: null
Bucket 1: 21 -> 11 -> 1 -> null
Bucket 2: null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

C

Bucket 0: null
Bucket 1: 11 -> 21 -> 1 -> null
Bucket 2: null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

D

Bucket 0: null
Bucket 1: 1 -> null
Bucket 2: null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

💡 Hint

Remember the hash function is key % 10 and new keys are added at the end of the linked list in the bucket.

The hash function maps keys 1, 11, and 21 to bucket 1 (since 1 % 10 = 1, 11 % 10 = 1, 21 % 10 = 1). They are inserted in order at the end of the linked list, so the bucket 1 chain is 1 -> 11 -> 21 -> null.

🧠 Conceptual

intermediate

Understanding collision handling with chaining

Why does chaining handle collisions effectively in a hash table?

A Because it rehashes the key to a new bucket until an empty one is found.

B Because it deletes the old key and replaces it with the new key in case of collision.

C Because it uses open addressing to find the next free bucket for collided keys.

D Because it stores all collided keys in a linked list at the same bucket, allowing multiple keys to share one bucket.

💡 Hint

Think about how multiple keys can be stored in the same bucket without losing data.

Chaining stores collided keys in a linked list at the bucket index, so all keys with the same hash can be stored without overwriting each other.

🔧 Debug

advanced

Find the bug in chaining insertion code

What error will occur when running this chaining insertion code snippet?

DSA Go

func (ht *HashTable) Insert(key int) {
	index := ht.hash(key)
	newNode := &Node{key: key}
	if ht.buckets[index] == nil {
		ht.buckets[index] = newNode
	} else {
		current := ht.buckets[index]
		for current.next != nil {
			current = current.next
		}
		current = newNode
	}
}

A Keys are not linked properly; newNode is not added to the list causing lost nodes.

B Compilation error due to missing return statement.

C No error; keys are inserted correctly.

D Runtime panic due to nil pointer dereference.

💡 Hint

Check how the new node is linked to the existing list in the else block.

The line 'current = newNode' only changes the local variable 'current' and does not link the new node to the list. The correct way is 'current.next = newNode'.

❓ Predict Output

advanced

Output after deleting a key from chaining hash table

What is the printed state of the hash table buckets after inserting keys 2, 12, 22 and then deleting key 12 from a hash table of size 10 using chaining with hash function key % 10?

DSA Go

package main

import (
	"fmt"
)

type Node struct {
	key  int
	next *Node
}

type HashTable struct {
	size   int
	buckets []*Node
}

func NewHashTable(size int) *HashTable {
	return &HashTable{
		size:   size,
		buckets: make([]*Node, size),
	}
}

func (ht *HashTable) hash(key int) int {
	return key % ht.size
}

func (ht *HashTable) Insert(key int) {
	index := ht.hash(key)
	newNode := &Node{key: key}
	if ht.buckets[index] == nil {
		ht.buckets[index] = newNode
	} else {
		current := ht.buckets[index]
		for current.next != nil {
			current = current.next
		}
		current.next = newNode
	}
}

func (ht *HashTable) Delete(key int) {
	index := ht.hash(key)
	current := ht.buckets[index]
	var prev *Node = nil
	for current != nil {
		if current.key == key {
			if prev == nil {
				ht.buckets[index] = current.next
			} else {
				prev.next = current.next
			}
			return
		}
		prev = current
		current = current.next
	}
}

func (ht *HashTable) Print() {
	for i, node := range ht.buckets {
		fmt.Printf("Bucket %d: ", i)
		current := node
		for current != nil {
			fmt.Printf("%d -> ", current.key)
			current = current.next
		}
		fmt.Println("null")
	}
}

func main() {
	ht := NewHashTable(10)
	ht.Insert(2)
	ht.Insert(12)
	ht.Insert(22)
	ht.Delete(12)
	ht.Print()
}

A

Bucket 0: null
Bucket 1: null
Bucket 2: 2 -> 12 -> 22 -> null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

B

Bucket 0: null
Bucket 1: null
Bucket 2: 2 -> 22 -> null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

C

Bucket 0: null
Bucket 1: null
Bucket 2: 22 -> 2 -> null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

D

Bucket 0: null
Bucket 1: null
Bucket 2: 12 -> 2 -> 22 -> null
Bucket 3: null
Bucket 4: null
Bucket 5: null
Bucket 6: null
Bucket 7: null
Bucket 8: null
Bucket 9: null

💡 Hint

Deleting key 12 removes it from the linked list in bucket 2.

Keys 2, 12, and 22 all hash to bucket 2. After deleting 12, the linked list in bucket 2 contains 2 -> 22 -> null.

🚀 Application

expert

Analyzing time complexity of chaining under heavy collisions

If a hash table uses chaining and all keys hash to the same bucket, what is the worst-case time complexity for searching a key in the table with n keys?

A O(log n) because linked list search is optimized with binary search.

B O(1) because chaining always provides constant time search.

C O(n) because all keys are in one linked list, so search is linear.

D O(n^2) because each search requires scanning all keys multiple times.

💡 Hint

Consider what happens if all keys collide into one bucket's linked list.

When all keys collide into one bucket, the linked list contains all n keys, so searching requires checking each node, resulting in O(n) time.

Practice

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

easy

A. Use open addressing to find another empty slot

B. Resize the hash table to avoid collisions

C. Store multiple elements in a linked list at the same index when collisions occur

D. Ignore collisions and overwrite existing data

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index.

3. Final Answer:

   Store multiple elements in a linked list at the same index when collisions occur -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

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

Common Mistakes:

• Thinking chaining resizes the table
• Confusing chaining with open addressing
• Assuming collisions are ignored

2. Which of the following is the correct way to declare a hash table with chaining in Go using slices of linked lists?

easy

A. var table [10]*Node

B. var table = make([]*Node, 10)

C. var table = make(map[int]*Node)

D. var table = [10]Node{}

Solution

1. Step 1: Understand Go slice declaration for chaining

   Chaining uses a slice of pointers to linked list nodes for dynamic size.

2. Step 2: Identify correct syntax

   Using make([]*Node, 10) creates a slice of 10 pointers to Node, suitable for chaining.

3. Final Answer:

   var table = make([]*Node, 10) -> Option B

4. Quick Check:

   Slice of pointers = make([]*Node, size) [OK]

Hint: Use make([]*Node, size) for chaining table [OK]

Common Mistakes:

• Using arrays instead of slices limits flexibility
• Using map instead of slice for chaining
• Declaring slice without make causes nil slice

3. Consider the following Go code snippet for inserting keys into a hash table with chaining. What will be the output after inserting keys 5 and 15 if the hash function is key % 10?

type Node struct {
    key  int
    next *Node
}

func insert(table []*Node, key int) {
    index := key % 10
    newNode := &Node{key: key}
    newNode.next = table[index]
    table[index] = newNode
}

func printTable(table []*Node) {
    for i, node := range table {
        print(i, ": ")
        for n := node; n != nil; n = n.next {
            print(n.key, " -> ")
        }
        println("nil")
    }
}

func main() {
    table := make([]*Node, 10)
    insert(table, 5)
    insert(table, 15)
    printTable(table)
}

medium

A. 15 -> 5 -> nil at index 5

B. 15 -> nil at index 5 and 5 -> nil at index 5

C. 5 -> nil at index 5 and 15 -> nil at index 5

D. 5 -> 15 -> nil at index 5

Solution

1. Step 1: Calculate hash index for keys 5 and 15

   Both 5 % 10 and 15 % 10 equal 5, so both keys go to index 5.

2. Step 2: Trace insertion order in chaining

   First insert 5 at index 5, then insert 15 which becomes new head pointing to 5.

3. Final Answer:

   15 -> 5 -> nil at index 5 -> Option A

4. Quick Check:

   New nodes added at head = 15 first [OK]

Hint: New nodes go to head of list in chaining [OK]

Common Mistakes:

• Assuming insertion appends at tail
• Mixing up hash index calculation
• Printing nodes in wrong order

4. The following Go code tries to insert keys into a hash table with chaining but causes a runtime panic. What is the error?

type Node struct {
    key  int
    next *Node
}

func insert(table []*Node, key int) {
    index := key % len(table)
    if table[index] == nil {
        table[index].key = key
    } else {
        newNode := &Node{key: key, next: table[index]}
        table[index] = newNode
    }
}

func main() {
    table := make([]*Node, 10)
    insert(table, 7)
}

medium

A. Nil pointer dereference when assigning to table[index].key

B. Index out of range error due to wrong hash calculation

C. Infinite loop in insert function

D. Compilation error due to missing return statement

Solution

1. Step 1: Analyze the nil check and assignment

   If table[index] is nil, trying to assign table[index].key causes nil pointer dereference.

2. Step 2: Understand pointer initialization requirement

   Must create a new Node and assign pointer to table[index] before setting key.

3. Final Answer:

   Nil pointer dereference when assigning to table[index].key -> Option A

4. Quick Check:

   Assigning field on nil pointer causes panic [OK]

Hint: Initialize pointer before assigning fields [OK]

Common Mistakes:

• Ignoring nil pointer before field assignment
• Assuming slice elements auto-initialize
• Confusing compile error with runtime panic

5. You want to implement a hash table with chaining in Go that supports deletion of keys. Which approach correctly removes a key from the chain at the hashed index?

hard

A. Replace the key with zero but keep the node in the list

B. Set the entire linked list at the index to nil to remove the key

C. Resize the hash table and rehash all keys except the one to delete

D. Traverse the linked list at the index, keep track of previous node, and adjust pointers to skip the node with the key

Solution

1. Step 1: Understand deletion in chaining

   To delete a key, find it in the linked list and remove its node by adjusting pointers.

2. Step 2: Why other options fail

   Setting entire list to nil removes all keys, replacing key with zero keeps node, resizing is inefficient.

3. Final Answer:

   Traverse the linked list at the index, keep track of previous node, and adjust pointers to skip the node with the key -> Option D

4. Quick Check:

   Proper deletion adjusts pointers in linked list [OK]

Hint: Delete by pointer adjustment in linked list [OK]

Common Mistakes:

• Removing entire chain instead of one key
• Leaving empty nodes with zero keys
• Rehashing unnecessarily on deletion