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 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 one.

Index: 0  1  2  3  4  5  6
Table: [ ] [ ] [ ] [ ] [ ] [ ] [ ]
          ↑
       hash(key) points here

Dry Run Walkthrough

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

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

Step 1: Insert 10: compute hash 10 % 7 = 3, slot 3 is empty, place 10 there

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

Why: First insertion, slot is free so we put 10 there

Step 2: Insert 20: compute hash 20 % 7 = 6, slot 6 is empty, place 20 there

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

Why: Slot 6 is free, so 20 goes there without collision

Step 3: Insert 30: compute hash 30 % 7 = 2, slot 2 is empty, place 30 there

Index: 0  1  2  3  4  5  6
Table: [ ] [ ] [30] [10] [ ] [ ] [20]

Why: Slot 2 is free, so 30 goes there without collision

Step 4: Insert 17: compute hash 17 % 7 = 3, slot 3 is occupied by 10, move to next slot 4 which is empty, place 17 there

Index: 0  1  2  3  4  5  6
Table: [ ] [ ] [30] [10] [17] [ ] [20]

Why: Collision at slot 3, so linear probing moves to next free slot 4

Result:

Index: 0  1  2  3  4  5  6
Table: [ ] [ ] [30] [10] [17] [ ] [20]

Annotated Code

DSA C

#include <stdio.h>
#define TABLE_SIZE 7

int hash(int key) {
    return key % TABLE_SIZE;
}

void insert(int table[], int key) {
    int index = hash(key);
    int start_index = index;
    while (table[index] != -1) {
        index = (index + 1) % TABLE_SIZE; // move to next slot
        if (index == start_index) {
            printf("Hash table is full, cannot insert %d\n", key);
            return;
        }
    }
    table[index] = key;
}

void print_table(int table[]) {
    printf("Hash Table:\n");
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table[i] == -1) {
            printf("[%d]: empty\n", i);
        } else {
            printf("[%d]: %d\n", i, table[i]);
        }
    }
}

int main() {
    int table[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; i++) {
        table[i] = -1; // initialize all slots as empty
    }

    insert(table, 10);
    insert(table, 20);
    insert(table, 30);
    insert(table, 17);

    print_table(table);
    return 0;
}

int index = hash(key);

compute initial slot using hash function

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

check if slot is occupied to handle collision

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

move to next slot in linear probing

if (index == start_index) {

detect full table to stop infinite loop

table[index] = key;

insert key into found empty slot

Output

Hash Table:

[0]: empty

[1]: empty

[2]: 30

[3]: 10

[4]: 17

[5]: empty

[6]: 20

Complexity Analysis

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

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

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

Edge Cases

Inserting into a full table

The code detects full table and prints an error message without infinite loop

DSA C

if (index == start_index) {

Inserting first element

Inserted directly at hashed slot since it is empty

DSA C

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

When to Use This Pattern

When you see a hash table with collisions and no extra lists, think of linear probing to find next free slot by moving forward.

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) % TABLE_SIZE

Mistake: Not checking for full table causing infinite loop
Fix: Add a check to stop when index returns to start_index

Summary

It handles collisions by moving forward to find the next empty slot in the hash table.

Use it when you want a simple way to resolve collisions without extra memory for linked lists.

The key insight is to keep trying the next slot until you find an empty one or confirm the table is full.

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 to store multiple elements at the same index.

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

D. Rehash all elements using a new hash function when a collision occurs.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in the array sequentially when the desired slot is occupied.

2. Step 2: Compare options with definition

   If a collision occurs, check the next slot sequentially until an empty slot is found. correctly describes this sequential checking. Other options describe different collision handling methods.

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 means try next slot one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking rehashing happens on every collision
• Assuming table size doubles automatically

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. next_index = (i + 3) % m

B. next_index = (i * 2) % m

C. next_index = (i - 1) % m

D. next_index = (i + 1) % m

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.

2. Step 2: Match formula with options

   next_index = (i + 1) % m matches this formula: (i + 1) % m. Other options use incorrect increments.

3. Final Answer:

   next_index = (i + 1) % m -> Option D

4. Quick Check:

   Linear probing next index = (i + 1) mod m [OK]

Hint: Linear probing adds 1 to index modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• 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(k) = k % 5. Insert keys 7, 12, 17 in order. What is the final state of the table?

medium

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

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

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

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

Solution

1. Step 1: Calculate initial positions using hash function

   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 occupied, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are occupied, so insert at index 4.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not wrapping around table size
• Misplacing keys at wrong indices

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

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;
}

medium

A. The index update should subtract 1 instead of adding 1.

B. The table is not initialized with -1 for empty slots.

C. The while loop condition should check for table[index] == -1.

D. The hash function should use multiplication instead of modulo.

Solution

1. Step 1: Analyze the insert function logic

   The function checks for empty slots by comparing with -1, so the table must be initialized with -1 to mark empty slots.

2. Step 2: Identify missing initialization

   If the table is not initialized with -1, the condition table[index] != -1 may fail incorrectly, causing wrong insertions or infinite loops.

3. Final Answer:

   The table is not initialized with -1 for empty slots. -> Option B

4. Quick Check:

   Empty slots must be marked -1 [OK]

Hint: Initialize table slots with -1 before insertion [OK]

Common Mistakes:

• Ignoring table initialization
• Wrong loop condition in while
• Incorrect hash function usage

5. You have a hash table of size 7 using linear probing. Insert keys 10, 20, 15, 7, 32 in order using hash function h(k) = k % 7. After all insertions, what is the content of the table?

hard

A. [7, 15, null, 10, 32, null, 20]

B. [null, 15, 32, 10, null, 20, 7]

C. [null, 15, 32, 10, 20, 7, null]

D. [null, 15, 32, 10, 20, null, 7]

Solution

1. Step 1: Calculate initial indices for each key

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

2. Step 2: Insert keys using linear probing

   Insert 10 at index 3. Insert 20 at index 6. Insert 15 at index 1. Insert 7 at index 0. Insert 32 at index 4 (empty). Final table: [7, 15, null, 10, 32, null, 20].

3. Step 3: Match with options

   [7, 15, null, 10, 32, null, 20] matches the correct order. Nulls at indices 2 and 5.

4. Final Answer:

   [7, 15, null, 10, 32, null, 20] -> Option A

5. Quick Check:

   Keys placed at their hash or next free slot [OK]

Hint: Calculate hash, insert or probe next free slot [OK]

Common Mistakes:

• Not probing when slot is occupied
• Misplacing keys at wrong indices
• Ignoring table size wrap-around