Collision Handling Using Chaining in DSA Go - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app. You want to store names and phone numbers. But sometimes, two names might have the same hash value. To handle this, you will use chaining, which means storing multiple entries in a list at the same spot.

🎯 Goal: You will create a hash table using chaining to handle collisions. You will add entries and then print the hash table to see how collisions are handled.

📋 What You'll Learn

Create a hash table with a fixed size using a slice of slices

Add entries (name and phone number) to the hash table

Use a simple hash function to find the index

Handle collisions by appending to the slice at the index (chaining)

Print the hash table showing all entries in each chain

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many applications like databases, caches, and phone books to store and retrieve data efficiently even when collisions happen.

💼 Career

Understanding collision handling is important for software engineers working on data storage, search engines, and performance-critical applications.

1

Create the hash table data structure

Create a variable called hashTable which is a slice of slices of strings with length 5. Initialize each inner slice as empty.

DSA Go

# Create the hashTable variable as a slice of 5 empty slices of strings
# Your code here

Hint

Use make([][]string, 5) to create the outer slice. Then loop over it to assign empty slices to each position.

2

Add a simple hash function

Create a function called hash that takes a string key and returns an int. The function should return the sum of the ASCII values of the characters in key modulo 5.

DSA Go

package main

import "fmt"

func main() {
    hashTable := make([][]string, 5)
    for i := range hashTable {
        hashTable[i] = []string{}
    }
}

// Create the hash function below
// Your code here

Hint

Loop over each character in the string, add its integer value to sum, then return sum % 5.

3

Add entries to the hash table using chaining

In the main function, add these entries to hashTable using the hash function to find the index: "Alice:12345", "Bob:67890", "Carol:54321". Append each entry string to the slice at the hashed index.

DSA Go

package main

import "fmt"

func hash(key string) int {
    sum := 0
    for _, ch := range key {
        sum += int(ch)
    }
    return sum % 5
}

func main() {
    hashTable := make([][]string, 5)
    for i := range hashTable {
        hashTable[i] = []string{}
    }
    // Add "Alice:12345", "Bob:67890", "Carol:54321" to hashTable using chaining
    // Your code here
}

Hint

Create a slice with the entries, loop over it, get the index from hash, then append the entry to hashTable[index].

4

Print the hash table chains

Use a for loop with variable i to iterate over hashTable. Inside, print the index i and the entries in the chain separated by " -> ". Format each line as: "Index i: entry1 -> entry2 -> ...". If the chain is empty, print "Index i: empty".

DSA Go

package main

import "fmt"

func hash(key string) int {
    sum := 0
    for _, ch := range key {
        sum += int(ch)
    }
    return sum % 5
}

func main() {
    hashTable := make([][]string, 5)
    for i := range hashTable {
        hashTable[i] = []string{}
    }
    entries := []string{"Alice:12345", "Bob:67890", "Carol:54321"}
    for _, entry := range entries {
        index := hash(entry)
        hashTable[index] = append(hashTable[index], entry)
    }

    // Print the hash table chains
    // Your code here
}

Hint

Use strings.Join to join the entries with " -> ". Print "Index i: empty" if no entries.

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