Collision Handling Using Open Addressing Linear Probing in DSA C#

Mental Model

When two items want the same spot in a table, we look for the next empty spot by moving step by step.

Analogy: Imagine parking cars in a row of parking spots. If your favorite spot is taken, you walk forward to find the next empty spot to park.

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

Dry Run Walkthrough

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

Goal: Show how collisions are handled by moving to the next empty spot

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

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

Why: Index 0 is empty, so 10 is placed there

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

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

Why: Collision at index 0, so linear probing finds next empty spot at index 1

Step 3: Insert 30 at index 30 % 10 = 0, indexes 0 and 1 are taken, move to index 2

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

Why: Collision at indexes 0 and 1, linear probing moves to next empty spot at index 2

Result:

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

Annotated Code

DSA C#

using System;

class LinearProbingHashTable
{
    private int?[] table;
    private int size;

    public LinearProbingHashTable(int size)
    {
        this.size = size;
        table = new int?[size];
    }

    public void Insert(int key)
    {
        int index = key % size; // compute initial index
        int startIndex = index; // remember start to detect full table

        while (table[index].HasValue) // while spot is taken
        {
            index = (index + 1) % size; // move to next index
            if (index == startIndex) // table full
            {
                Console.WriteLine("Hash table is full, cannot insert " + key);
                return;
            }
        }
        table[index] = key; // place key in empty spot
    }

    public void PrintTable()
    {
        for (int i = 0; i < size; i++)
        {
            if (table[i].HasValue)
                Console.WriteLine($"Index {i}: {table[i].Value}");
            else
                Console.WriteLine($"Index {i}: [empty]");
        }
    }
}

class Program
{
    static void Main()
    {
        LinearProbingHashTable hashTable = new LinearProbingHashTable(10);
        hashTable.Insert(10);
        hashTable.Insert(20);
        hashTable.Insert(30);
        hashTable.PrintTable();
    }
}

int index = key % size; // compute initial index

calculate initial position using hash function

while (table[index].HasValue)

check if current index is occupied to handle collision

index = (index + 1) % size; // move to next index

move to next index in linear probing to find empty spot

table[index] = key; // place key in empty spot

insert key at found empty index

Output

Index 0: 10

Index 1: 20

Index 2: 30

Index 3: [empty]

Index 4: [empty]

Index 5: [empty]

Index 6: [empty]

Index 7: [empty]

Index 8: [empty]

Index 9: [empty]

Complexity Analysis

Time: O(n) in worst case because in the worst case we may check every slot once during insertion

Space: O(n) because we store up to n keys in the hash table array

vs Alternative: Compared to chaining which uses linked lists, linear probing uses less memory but can have clustering causing slower lookups

Edge Cases

Inserting into a full table

Insertion fails with a message that the table is full

DSA C#

if (index == startIndex) // table full

Inserting duplicate keys

Duplicates are inserted as separate entries in next available spots

DSA C#

while (table[index].HasValue)

Inserting keys that hash to different indexes

Keys are inserted directly at their hashed index without probing

DSA C#

while (table[index].HasValue)

When to Use This Pattern

When you see a hash table with collisions and no linked lists, and the problem mentions checking next spots, use linear probing to resolve collisions by searching sequentially.

Common Mistakes

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

Mistake: Not detecting full table and causing infinite loop
Fix: Keep track of start index and stop probing if we return to it

Summary

It handles collisions in a hash table by checking the next empty slot sequentially.

Use it when you want a simple way to resolve collisions without extra data structures.

The key insight is to move step-by-step through the table to find an empty spot when a collision happens.

Practice

1. What is the main idea behind Linear Probing in collision handling for hash tables?

easy

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

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

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 methods

   Linear probing is a method where if a collision happens, the algorithm checks the next slot in the array sequentially.

2. Step 2: Compare options with linear probing definition

   If a collision occurs, check the next slot sequentially until an empty slot is found. correctly describes checking the next slot sequentially until an empty slot is found, which matches linear probing.

3. Final Answer:

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

4. Quick Check:

   Linear probing = check next slot sequentially [OK]

Hint: Linear probing means try next slot 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 tableSize when a collision occurs at index?

easy

A. nextIndex = (index * 2) % tableSize;

B. nextIndex = (index - 1) % tableSize;

C. nextIndex = (index + 1) % tableSize;

D. nextIndex = (index + 3) % tableSize;

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index and taking modulo with table size to wrap around.

2. Step 2: Match formula with options

   nextIndex = (index + 1) % tableSize; uses (index + 1) % tableSize, which is the correct formula for linear probing.

3. Final Answer:

   nextIndex = (index + 1) % tableSize; -> Option C

4. Quick Check:

   Linear probing next index = (index + 1) % size [OK]

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

Common Mistakes:

• Multiplying index instead of adding
• Subtracting instead of adding
• Adding a number other than 1

3. Consider a hash table of size 5 using linear probing. The hash function is h(key) = key % 5. Insert keys in this order: 7, 12, 17. What will be the final state of the hash table (index: value)?

medium

A. {0: null, 1: null, 2: 7, 3: 12, 4: 17}

B. {0: 12, 1: 17, 2: 7, 3: null, 4: null}

C. {0: null, 1: 7, 2: null, 3: 12, 4: 17}

D. {0: null, 1: 7, 2: 17, 3: 12, 4: null}

Solution

1. Step 1: Calculate initial indices for each key

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys initially map to index 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2 (empty). Insert 12: index 2 occupied, try index 3 (empty), insert 12. Insert 17: index 2 and 3 occupied, try index 4 (empty), insert 17.

3. Final Answer:

   {0: null, 1: null, 2: 7, 3: 12, 4: 17} -> Option A

4. Quick Check:

   Keys collide at 2, placed at 2,3,4 sequentially [OK]

Hint: All keys hash to same index, place next free slot [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Not wrapping around the table
• Inserting keys in wrong order

4. The following C# code tries to insert keys into a hash table using linear probing. What is the bug?

int tableSize = 5;
int[] hashTable = new int[tableSize];
for (int i = 0; i < tableSize; i++) hashTable[i] = -1;

int Hash(int key) => key % tableSize;

void Insert(int key) {
    int index = Hash(key);
    while (hashTable[index] != -1) {
        index = (index + 1);
    }
    hashTable[index] = key;
}

Insert(7);
Insert(12);
Insert(17);

medium

A. The hash function is incorrect for linear probing.

B. The Insert method should use recursion instead of a loop.

C. The initial hash table values should be 0, not -1.

D. The code does not wrap index back to 0 when it reaches the end of the table.

Solution

1. Step 1: Analyze the index update in the loop

   The code increments index by 1 on collision but does not use modulo to wrap around the table size.

2. Step 2: Identify the consequence of missing modulo

   Without modulo, index can go beyond array bounds causing runtime error or incorrect behavior.

3. Final Answer:

   The code does not wrap index back to 0 when it reaches the end of the table. -> Option D

4. Quick Check:

   Linear probing requires modulo to wrap index [OK]

Hint: Always use modulo to wrap index in linear probing [OK]

Common Mistakes:

• Forgetting modulo causes index out of range
• Changing hash function unnecessarily
• Thinking initial values must be zero

5. You have a hash table of size 7 using linear probing. The hash function is h(key) = key % 7. You insert keys: 10, 24, 31, 17, 3. Then you delete key 24 by marking its slot as empty. Now you want to search for key 31. What problem might occur and how to fix it?

hard

A. Search may stop early at the empty slot of deleted key 24, missing key 31; fix by using a special 'deleted' marker instead of empty.

B. Search will always find key 31 without issues; no fix needed.

C. Key 31 will be overwritten by key 24; fix by rehashing all keys after deletion.

D. The hash function is wrong; fix by changing it to key % 5.

Solution

1. Step 1: Understand deletion effect in linear probing

   Deleting by marking slot empty breaks the probe chain, so search may stop early and miss keys inserted after the deleted slot.

2. Step 2: Identify correct deletion method

   Use a special 'deleted' marker to indicate slot is free for insertion but search should continue probing.

3. Final Answer:

   Search may stop early at the empty slot of deleted key 24, missing key 31; fix by using a special 'deleted' marker instead of empty. -> Option A

4. Quick Check:

   Deleted slots need special marker to continue search [OK]

Hint: Use 'deleted' marker, not empty slot, to avoid search errors [OK]

Common Mistakes:

• Marking deleted slots as empty breaks search
• Assuming search always finds keys after deletion
• Changing hash function unnecessarily