Collision Handling Using Chaining in DSA Go - Execution Trace

Concept Flow - Collision Handling Using Chaining

Insert key

↓

Compute hash index

↓

Check bucket at index

↓

Bucket empty?

Yes→Create new linked list node with key

↓

Insert node at bucket

↓

Done

↓

Bucket not empty

No→Traverse linked list

↓

Key exists?

Yes→Update value

↓

Done

↓

Key not found

No→Insert new node at head

↓

Done

When inserting a key, compute its hash index to find the bucket. If the bucket is empty, create a new linked list node. If not, traverse the linked list to find the key; update if found, else insert a new node at the head.

Execution Sample

DSA Go

hashTable := make([]*Node, 3)
Insert("apple", 10)
Insert("banana", 20)
Insert("grape", 30)
Insert("apple", 40)

Insert keys with values into a hash table of size 3 using chaining to handle collisions.

Execution Table

Step	Operation	Bucket Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Insert("apple", 10)	hash("apple") % 3 = 0	empty	Create node with (apple,10) at bucket 0	Node(apple:10) -> null	0: apple:10 -> null 1: empty 2: empty
2	Insert("banana", 20)	hash("banana") % 3 = 1	empty	Create node with (banana,20) at bucket 1	Node(banana:20) -> null	0: apple:10 -> null 1: banana:20 -> null 2: empty
3	Insert("grape", 30)	hash("grape") % 3 = 0	Node(apple:10) -> null	Insert new node (grape,30) at head of bucket 0	Node(grape:30) -> Node(apple:10) -> null	0: grape:30 -> apple:10 -> null 1: banana:20 -> null 2: empty
4	Insert("apple", 40)	hash("apple") % 3 = 0	Node(grape:30) -> Node(apple:10) -> null	Traverse list, find apple, update value to 40	Node(grape:30) -> Node(apple:40) -> null	0: grape:30 -> apple:40 -> null 1: banana:20 -> null 2: empty
5	End	-	-	-	-	Insertion complete

💡 All keys inserted; collisions handled by chaining linked lists at buckets.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
hashTable[0]	null	Node(apple:10) -> null	Node(apple:10) -> null	Node(grape:30) -> Node(apple:10) -> null	Node(grape:30) -> Node(apple:40) -> null	Node(grape:30) -> Node(apple:40) -> null
hashTable[1]	null	null	Node(banana:20) -> null	Node(banana:20) -> null	Node(banana:20) -> null	Node(banana:20) -> null
hashTable[2]	null	null	null	null	null	null

Key Moments - 3 Insights

Why do we insert the new node at the head of the linked list in the bucket?

In step 3, when inserting "grape" at bucket 0, we add the new node at the head to keep insertion simple and fast without traversing the entire list.

What happens if the key already exists in the bucket's linked list?

In step 4, when inserting "apple" again, we traverse the list, find the existing key, and update its value instead of adding a new node.

Why do we use a linked list for each bucket instead of an array?

Linked lists allow dynamic size and easy insertion at head without shifting elements, as shown in the chaining steps in the execution table.

Visual Quiz - 3 Questions

Look at the execution table, what is the bucket 0 state after step 3?

A Node(grape:30) -> Node(apple:10) -> null

B Node(apple:10) -> null

C Node(grape:30) -> null

D empty

💡 Hint

Check the 'Bucket State After' column for step 3 in the execution table.

At which step does the value of "apple" get updated?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look for the operation that updates an existing key in the execution table.

If the hash table size was increased to 5, how would the bucket index for "banana" change?

A It would be 0

B It would remain 1

C It would be hash("banana") % 5, possibly different

D It would be 3

💡 Hint

Bucket index depends on modulo with table size; see 'Bucket Index' column.

Concept Snapshot

Collision Handling Using Chaining:
- Use a linked list at each bucket to store multiple keys.
- Compute hash index: index = hash(key) % table_size.
- If bucket empty, insert new node.
- If bucket not empty, traverse list:
  - Update value if key found.
  - Else insert new node at head.
- Efficiently handles collisions by chaining.

Full Transcript

Collision Handling Using Chaining stores multiple keys in the same bucket using a linked list. When inserting a key, we compute its hash index to find the bucket. If the bucket is empty, we create a new node. If not, we traverse the linked list to find if the key exists. If found, we update its value; otherwise, we insert a new node at the head of the list. This method handles collisions by chaining keys together in linked lists at each bucket. The example shows inserting keys "apple", "banana", "grape", and updating "apple"'s value. The hash table size is 3, so keys map to buckets 0, 1, or 2. The linked list nodes are updated accordingly, demonstrating chaining in action.

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