Collision Handling Using Open Addressing Linear Probing in DSA C++

Mental Model

When two items want the same spot, try the next spots one by one until you find an empty one.

Analogy: Imagine parking your car in a row of parking spots. If your favorite spot is taken, you check the next spot, then the next, until you find a free spot.

Index: 0  1  2  3  4  5  6  7
Table: _  _  _  _  _  _  _  _
          ↑

Dry Run Walkthrough

Input: Insert keys 10, 22, 31, 15 into a hash table of size 8 using linear probing

Goal: Show how collisions are handled by checking next spots until empty is found

Step 1: Insert 10 at index 10 % 8 = 2

Index: 0  1  2  3  4  5  6  7
Table: _  _ [10] _  _  _  _  _

Why: 10's hash index 2 is empty, so place it there

Step 2: Insert 22 at index 22 % 8 = 6

Index: 0  1  2  3  4  5  6  7
Table: _  _ [10] _  _  _ [22] _

Why: 22's hash index 6 is empty, so place it there

Step 3: Insert 31 at index 31 % 8 = 7

Index: 0  1  2  3  4  5  6  7
Table: _  _ [10] _  _  _ [22] [31]

Why: 31's hash index 7 is empty, so place it there

Step 4: Insert 15 at index 15 % 8 = 7, collision with 31, try next index 0

Index: 0  1  2  3  4  5  6  7
Table: [15] _ [10] _  _  _ [22] [31]

Why: Index 7 is taken, so check next index 0 which is empty, place 15 there

Result:

Index: 0  1  2  3  4  5  6  7
Table: [15] _ [10] _  _  _ [22] [31]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class HashTable {
    vector<int> table;
    int size;
public:
    HashTable(int s) : size(s) {
        table.resize(size, -1); // -1 means empty
    }

    void insert(int key) {
        int index = key % size; // hash function
        int start_index = index;
        while (table[index] != -1) { // collision
            index = (index + 1) % size; // linear probing
            if (index == start_index) {
                cout << "Hash table full, cannot insert " << key << endl;
                return;
            }
        }
        table[index] = key;
    }

    void print() {
        for (int i = 0; i < size; i++) {
            if (table[i] == -1) cout << "_ ";
            else cout << table[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    HashTable ht(8);
    ht.insert(10);
    ht.insert(22);
    ht.insert(31);
    ht.insert(15);
    ht.print();
    return 0;
}

int index = key % size; // hash function

Calculate initial index using hash function

while (table[index] != -1) { // collision

Check if spot is taken, if yes, move to next index

index = (index + 1) % size; // linear probing

Advance index by one, wrap around if needed

if (index == start_index) { cout << "Hash table full, cannot insert " << key << endl; return; }

Stop if we circled back to start, table is full

table[index] = key;

Place key in found empty spot

Output

15 _ 10 _ _ _ 22 31 

Complexity Analysis

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

Space: O(n) because we store n elements in the table array

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

Edge Cases

Inserting into a full table

The code detects full table and stops insertion with a message

DSA C++

if (index == start_index) { cout << "Hash table full, cannot insert " << key << endl; return; }

Inserting duplicate keys

Duplicates are inserted as separate entries if spots are free; no duplicate check

DSA C++

while (table[index] != -1) { ... }

Empty table insertion

Keys are inserted directly at their hash index if empty

DSA C++

if (table[index] == -1) table[index] = key;

When to Use This Pattern

When you see a hash table with collisions and no extra lists, and the problem says to find next free spot, use linear probing to handle collisions by checking next indices.

Common Mistakes

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

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

Summary

It handles collisions by checking the next spots in the table until an empty one is found.

Use it when you want to store items in a fixed-size array and handle collisions without extra memory.

The key insight is to move step-by-step through the table to find a free spot, like looking for a parking space.

Practice

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

easy

A. Rehash all elements to a new table when a collision occurs.

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. If a collision occurs, check the next slot sequentially until an empty slot is found.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in order if the original slot is occupied.

2. Step 2: Compare with other methods

   Other options describe chaining or resizing, not linear probing.

3. Final Answer:

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

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking collision means resizing immediately
• Assuming random slot probing

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 * 2) % m

B. (i + 1) % m

C. (i - 1) % m

D. (i + 3) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index, wrapping around using modulo.

2. Step 2: Verify modulo usage

   Modulo with table size m ensures index stays within bounds.

3. Final Answer:

   (i + 1) % m -> Option B

4. Quick Check:

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

Hint: Next slot in linear probing is (i+1) mod table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo to wrap index
• Subtracting instead of adding

3. Consider a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. Insert keys 10, 20, 15 in order. What is the final state of the table (index: value)?

medium

A. 0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20

B. 0: null, 1: null, 2: 15, 3: 10, 4: 20, 5: null, 6: null

C. 0: null, 1: null, 2: 10, 3: 20, 4: 15, 5: null, 6: null

D. 0: null, 1: null, 2: 10, 3: 15, 4: 20, 5: null, 6: null

Solution

1. Step 1: Compute hashes and insert 10

   h(10) = 10 % 7 = 3, index 3 empty, insert 10 at 3.

2. Step 2: Insert 20

   h(20) = 20 % 7 = 6, index 6 empty, insert 20 at 6.

3. Step 3: Insert 15

   h(15) = 15 % 7 = 1, index 1 empty, insert 15 at 1.

4. Final Answer:

   0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20 -> Option A

5. Quick Check:

   Positions 1:15, 3:10, 6:20 [OK]

Hint: Calculate hash, insert keys, probe next if occupied [OK]

Common Mistakes:

• Miscomputing hash values
• Not applying modulo correctly
• Placing keys at wrong indices

4. The following code snippet attempts to insert keys into a hash table using linear probing. Identify the bug:

int hash(int key, int size) { return key % size; }

void insert(int table[], int size, int key) {
  int index = hash(key, size);
  while (table[index] != -1) {
    index = (index + 1) % size;
  }
  table[index] = key;
}

int main() {
  int size = 5;
  int table[5] = {-1, -1, -1, -1, -1};
  insert(table, size, 5);
  insert(table, size, 10);
  insert(table, size, 15);
  insert(table, size, 20);
  insert(table, size, 25);
  insert(table, size, 30);
  return 0;
}

medium

A. Infinite loop possible when table is full because no stop condition in while loop.

B. Hash function is incorrect; should use (key + 1) % size.

C. No bug, code works correctly for all insertions.

D. Array initialization with -1 is invalid in C++.

Solution

1. Step 1: Analyze insertion loop

   The while loop probes next index until an empty slot (-1) is found.

2. Step 2: Check for full table scenario

   If the table is full, the loop will cycle endlessly without a stop condition.

3. Step 3: Confirm other options

   Hash function is correct modulo. Array initialization with -1 is valid. So only infinite loop is the bug.

4. Final Answer:

   Infinite loop possible when table is full because no stop condition in while loop. -> Option A

5. Quick Check:

   Full table causes infinite loop in linear probing [OK]

Hint: Check if loop stops when table is full [OK]

Common Mistakes:

• Ignoring full table infinite loop
• Thinking hash function is wrong
• Assuming array init with -1 is invalid

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5, 6. You want to insert key 12 where h(k) = k % 10. If index 2 is occupied, what sequence of indices will be checked before insertion? What index will key 12 be inserted at if indices 2 to 6 are occupied but index 7 is free?

hard

A. Check indices 2, 4, 6, 8; insert at 8

B. Check indices 2, 3, 4; insert at 4

C. Check indices 2, 3, 4, 5, 6, 7; insert at 7

D. Check indices 2, 3, 4, 5, 6; insert at 2

Solution

1. Step 1: Calculate initial index for key 12

   h(12) = 12 % 10 = 2, so start checking at index 2.

2. Step 2: Apply linear probing sequence

   Since indices 2, 3, 4, 5, 6 are occupied, check next indices sequentially: 2, 3, 4, 5, 6, then 7.

3. Step 3: Find first free slot

   Index 7 is free, so insert key 12 at index 7.

4. Final Answer:

   Check indices 2, 3, 4, 5, 6, 7; insert at 7 -> Option C

5. Quick Check:

   Linear probe checks sequential slots until free [OK]

Hint: Probe sequentially until free slot found [OK]

Common Mistakes:

• Skipping indices in probing
• Inserting at first occupied slot
• Not wrapping index with modulo