Collision Handling Using Chaining in DSA Go

Mental Model

When two keys want the same spot in a table, we keep them in a small linked list at that spot.

Analogy: Imagine a mailbox with several slots. If two letters come for the same slot, we put them in a small pile inside that slot instead of losing one.

Hash Table:
[0] -> 15 -> 25 -> null
[1] -> null
[2] -> null
[3] -> 33 -> null
[4] -> null

Dry Run Walkthrough

Input: Insert keys 15, 25, 33 into a hash table of size 5 using chaining

Goal: Show how collisions are handled by adding nodes to linked lists at the same index

Step 1: Insert 15: compute index 15 % 5 = 0, place 15 at index 0

[0] -> 15 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We put 15 in the slot given by the hash function

Step 2: Insert 25: compute index 25 % 5 = 0, collision at index 0, add 25 to linked list at index 0

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: 25 collides with 15, so we chain it by adding to the list

Step 3: Insert 33: compute index 33 % 5 = 3, place 33 at index 3

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> null
[3] -> 33 -> null
[4] -> null

Why: 33 goes to an empty slot, no collision

Result:

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> null
[3] -> 33 -> null
[4] -> null

Annotated Code

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) // find bucket index
	newNode := &Node{key: key}
	if ht.buckets[index] == nil {
		ht.buckets[index] = newNode // place node if empty
	} else {
		curr := ht.buckets[index]
		for curr.next != nil {
			curr = curr.next // move to end of chain
		}
		curr.next = newNode // add new node at end
	}
}

func (ht *HashTable) String() string {
	result := ""
	for i, node := range ht.buckets {
		result += fmt.Sprintf("[%d] -> ", i)
		curr := node
		for curr != nil {
			result += fmt.Sprintf("%d -> ", curr.key)
			curr = curr.next
		}
		result += "null\n"
	}
	return result
}

func main() {
	ht := NewHashTable(5)
	ht.Insert(15)
	ht.Insert(25)
	ht.Insert(33)
	fmt.Print(ht.String())
}

index := ht.hash(key) // find bucket index

compute index using hash function

if ht.buckets[index] == nil { ht.buckets[index] = newNode // place node if empty } else { curr := ht.buckets[index] for curr.next != nil { curr = curr.next // move to end of chain } curr.next = newNode // add new node at end }

handle collision by chaining: add new node at the end of linked list

Output

[0] -> 15 -> 25 -> null

[1] -> null

[2] -> null

[3] -> 33 -> null

[4] -> null

Complexity Analysis

Time: O(n/k) on average, where n is number of keys and k is table size, because each bucket's chain length is n/k on average

Space: O(n) because we store all keys in linked lists inside the table

vs Alternative: Compared to open addressing, chaining uses extra memory for pointers but handles collisions more flexibly without clustering

Edge Cases

Inserting into an empty bucket

Node is placed directly without chaining

DSA Go

if ht.buckets[index] == nil {

Inserting multiple keys that hash to same index

Nodes are chained in linked list at that index

DSA Go

for curr.next != nil {

Hash table size is 0 or negative (not handled in code)

Code may panic or behave unexpectedly

When to Use This Pattern

When you see a hash table problem with collisions, think of chaining to store multiple keys at the same index using linked lists.

Common Mistakes

Mistake: Overwriting existing node on collision instead of chaining
Fix: Traverse the linked list and add the new node at the end instead of replacing

Mistake: Not handling empty bucket case separately
Fix: Check if bucket is nil before chaining

Summary

It stores multiple keys that hash to the same index by linking them in a list at that index.

Use it when hash collisions happen and you want a simple way to keep all keys without losing any.

The key insight is to keep a small linked list at each bucket to hold all collided keys.

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