Collision Handling Using Open Addressing Linear Probing in DSA Go

Mental Model

When two items want the same spot, we look for the next empty spot in order until we find one.

Analogy: Imagine parking cars in a row of parking spots. If your favorite spot is taken, you move forward one spot at a time until you find an empty spot to park.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Dry Run Walkthrough

Input: Insert keys 10, 20, 30 into a hash table of size 10 using linear probing

Goal: Show how collisions are handled by moving to the next free slot

Step 1: Insert 10 at index 0 (10 % 10 = 0)

0:[10] -> 1:[ ] -> 2:[ ] -> 3:[ ] -> 4:[ ] -> 5:[ ] -> 6:[ ] -> 7:[ ] -> 8:[ ] -> 9:[ ]

Why: Index 0 is free, so we place 10 there

Step 2: Insert 20 at index 0 (20 % 10 = 0), but index 0 is occupied, so move to index 1

0:[10] -> 1:[20] -> 2:[ ] -> 3:[ ] -> 4:[ ] -> 5:[ ] -> 6:[ ] -> 7:[ ] -> 8:[ ] -> 9:[ ]

Why: Collision at index 0, so we try next index 1 which is free

Step 3: Insert 30 at index 0 (30 % 10 = 0), index 0 occupied, index 1 occupied, move to index 2

0:[10] -> 1:[20] -> 2:[30] -> 3:[ ] -> 4:[ ] -> 5:[ ] -> 6:[ ] -> 7:[ ] -> 8:[ ] -> 9:[ ]

Why: Collision at 0 and 1, so we move to next free slot at index 2

Result:

0:[10] -> 1:[20] -> 2:[30] -> 3:[ ] -> 4:[ ] -> 5:[ ] -> 6:[ ] -> 7:[ ] -> 8:[ ] -> 9:[ ]

Annotated Code

DSA Go

package main

import "fmt"

const size = 10

type HashTable struct {
    table [size]int
    filled [size]bool
}

func (h *HashTable) Insert(key int) {
    index := key % size
    originalIndex := index
    for h.filled[index] {
        index = (index + 1) % size
        if index == originalIndex {
            fmt.Println("Hash table is full, cannot insert", key)
            return
        }
    }
    h.table[index] = key
    h.filled[index] = true
}

func (h *HashTable) String() string {
    result := ""
    for i := 0; i < size; i++ {
        if h.filled[i] {
            result += fmt.Sprintf("%d:[%d] -> ", i, h.table[i])
        } else {
            result += fmt.Sprintf("%d:[ ] -> ", i)
        }
    }
    result += "null"
    return result
}

func main() {
    h := HashTable{}
    h.Insert(10) // 10 % 10 = 0
    h.Insert(20) // 20 % 10 = 0, collision, move to 1
    h.Insert(30) // 30 % 10 = 0, collision, move to 2
    fmt.Println(h.String())
}

index := key % size

Calculate initial index using modulo to fit key in table size

for h.filled[index] {

Check if current index is occupied to handle collision

index = (index + 1) % size

Move to next index in circular manner for linear probing

if index == originalIndex {

Stop if we looped back to original index, table is full

h.table[index] = key h.filled[index] = true

Insert key at found free index and mark it filled

Output

0:[10] -> 1:[20] -> 2:[30] -> 3:[ ] -> 4:[ ] -> 5:[ ] -> 6:[ ] -> 7:[ ] -> 8:[ ] -> 9:[ ] -> null

Complexity Analysis

Time: O(n) in worst case because we may check every slot if many collisions happen

Space: O(n) because we store keys in an array of fixed size n

vs Alternative: Compared to chaining which uses linked lists, linear probing uses only array space but can have clustering causing slower insert/search

Edge Cases

Inserting into a full table

Insertion fails with a message because no free slot is found

DSA Go

if index == originalIndex {

Inserting keys that hash to different indices

Keys are inserted directly without probing

DSA Go

for h.filled[index] {

Inserting duplicate keys

Duplicates are inserted as new entries at next free slot

DSA Go

for h.filled[index] {

When to Use This Pattern

When you see a hash table with collisions and no extra lists, look for linear probing to find next free slot in the array.

Common Mistakes

Mistake: Not wrapping index back to start when reaching end of table
Fix: Use modulo operation to wrap index: index = (index + 1) % size

Mistake: Not checking if table is full and looping infinitely
Fix: Stop probing when index returns to original index to detect full table

Summary

It stores keys in an array and handles collisions by moving to the next free slot.

Use it when you want a simple collision handling method without extra data structures.

The key insight is to keep moving forward in the array until you find an empty spot.

Practice

1. What is the main idea behind linear probing in collision handling for hash tables?

easy

A. If a collision occurs, check the next slot sequentially until an empty slot is found.

B. Use a linked list at each slot to store multiple elements.

C. Double the size of the hash table when a collision happens.

D. Replace the existing element in the slot with the new one.

Solution

1. Step 1: Understand collision handling

   When two keys hash to the same slot, a collision occurs and must be resolved.

2. Step 2: Explain linear probing method

   Linear probing resolves collisions by checking the next slot in order until an empty one is found.

3. Final Answer:

   If a collision occurs, check the next slot sequentially until an empty slot is found. -> Option A

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing checks next slots one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing replaces existing elements
• Assuming table size doubles on collision

2. Which of the following is the correct way to calculate the next index in linear probing for a hash table of size m when current index is i?

easy

A. (i + 1) % m

B. (i + 3) % m

C. (i - 1) % m

D. (i * 2) % m

Solution

1. Step 1: Understand linear probing index calculation

   Linear probing moves to the next slot by adding 1 to the current index.

2. Step 2: Apply modulo to wrap around

   To stay within table bounds, use modulo with table size: (i + 1) % m.

3. Final Answer:

   (i + 1) % m -> Option A

4. Quick Check:

   Next index = (current + 1) mod size [OK]

Hint: Next slot = (current index + 1) mod table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo causing out-of-bound errors
• Subtracting instead of adding for next slot

3. Consider a hash table of size 5 with linear probing. Insert keys 7, 12, 17 in that order using hash function h(k) = k % 5. What is the final state of the table?

medium

A. [7, 12, 17, null, null]

B. [7, null, null, 12, 17]

C. [7, 12, null, 17, null]

D. [null, null, 7, 12, 17]

Solution

1. Step 1: Calculate initial positions

   h(7) = 7 % 5 = 2, h(12) = 12 % 5 = 2, h(17) = 17 % 5 = 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is taken, so check index 3 (empty), insert 12. For 17, indexes 2 and 3 taken, check index 4 (empty), insert 17.

3. Final Answer:

   [null, null, 7, 12, 17] -> Option D

4. Quick Check:

   All keys placed sequentially after collision [OK]

Hint: Check hash, then next slots if occupied [OK]

Common Mistakes:

• Placing keys at wrong indices ignoring collisions
• Not applying modulo for hash function
• Assuming keys overwrite existing ones

4. The following Go code snippet tries to insert keys into a hash table using linear probing. What is the error?

func insert(table []int, key int) {
    m := len(table)
    index := key % m
    for table[index] != -1 {
        index = (index + 1) % m
    }
    table[index] = key
}

// Initial table: [-1, -1, -1, -1, -1]
// Insert keys: 3, 8, 13

medium

A. The loop condition should check for zero instead of -1.

B. The code does not handle the case when the table is full, causing an infinite loop.

C. The initial table should be initialized with zeros, not -1.

D. The modulo operation should be done with key, not m.

Solution

1. Step 1: Analyze loop condition and termination

   The loop continues while the slot is occupied (not -1). If the table is full, the loop never ends.

2. Step 2: Identify missing full table check

   There is no check to stop after probing all slots, so infinite loop can occur if table is full.

3. Final Answer:

   The code does not handle the case when the table is full, causing an infinite loop. -> Option B

4. Quick Check:

   Missing full table check causes infinite loop [OK]

Hint: Always check for full table to avoid infinite loops [OK]

Common Mistakes:

• Ignoring full table condition
• Confusing initial empty slot value
• Misusing modulo operation

5. You have a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. You insert keys 10, 20, 15, 7, 32 in this order. After these insertions, you want to insert key 24. Which index will key 24 be placed at?

hard

A. Index 3

B. Index 4

C. Index 5

D. Index 6

Solution

1. Step 1: Insert keys and find their positions

   h(10)=3, insert at 3. h(20)=6, insert at 6. h(15)=1, insert at 1. h(7)=0, insert at 0. h(32)=4, insert at 4.

2. Step 2: Find position for key 24

   h(24)=3, but index 3 occupied by 10. Check next index 4 (occupied by 32), then 5 (empty), so insert at 5.

3. Final Answer:

   Index 5 -> Option C

4. Quick Check:

   Linear probe from 3 to 5 for key 24 [OK]

Hint: Probe next slots until empty found [OK]

Common Mistakes:

• Stopping at first collision without probing
• Not applying modulo for wrap-around
• Misplacing keys ignoring occupied slots