Collision Handling Using Open Addressing Linear Probing in DSA Java

Mental Model

When two items want the same spot in a table, we look for the next empty spot in a line to put the new item.

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 -> 7 -> 8 -> 9
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 0 (10 % 10 = 0)

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

Why: 10 fits directly at index 0 with no collision

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

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

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

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

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

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

Result:

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

Annotated Code

DSA Java

public class LinearProbingHashTable {
    private final int SIZE = 10;
    private Integer[] table;

    public LinearProbingHashTable() {
        table = new Integer[SIZE];
    }

    private int hash(int key) {
        return key % SIZE;
    }

    public void insert(int key) {
        int index = hash(key);
        int startIndex = index;
        while (table[index] != null) { // collision handling
            index = (index + 1) % SIZE; // move to next slot
            if (index == startIndex) { // table full
                System.out.println("Hash table is full, cannot insert " + key);
                return;
            }
        }
        table[index] = key; // place key
    }

    public void printTable() {
        for (int i = 0; i < SIZE; i++) {
            if (table[i] != null) {
                System.out.print(table[i] + " ");
            } else {
                System.out.print("- ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinearProbingHashTable hashTable = new LinearProbingHashTable();
        hashTable.insert(10);
        hashTable.insert(20);
        hashTable.insert(30);
        hashTable.printTable();
    }
}

int index = hash(key);

compute initial index using hash function

while (table[index] != null) {

detect collision if slot is occupied

index = (index + 1) % SIZE;

move to next slot in linear probing

if (index == startIndex) {

check if table is full to avoid infinite loop

table[index] = key;

insert key at found empty slot

Output

10 20 30 - - - - - - - 

Complexity Analysis

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

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

vs Alternative: Compared to chaining which uses linked lists, linear probing keeps all keys in one array but may have clustering causing slower searches

Edge Cases

Inserting into a full table

Insertion fails with a message that the table is full

DSA Java

if (index == startIndex) { // table full

Inserting keys with same hash repeatedly

Linear probing moves forward until an empty slot is found

DSA Java

while (table[index] != null) {

Inserting into an empty table

Key is inserted directly at hashed index

DSA Java

table[index] = key;

When to Use This Pattern

When you see a hash table with collisions and the problem asks to resolve them without extra data structures, reach for linear probing because it finds the next free spot in the array.

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 checking for full table and causing infinite loop
Fix: Keep track of start index and stop probing if we return to it

Summary

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

Use it when you want a simple way to resolve collisions in a fixed-size hash table without extra memory.

The key insight is to keep looking forward one slot at a time until you find an empty place.

Practice

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

easy

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

D. Rehash all elements using a new hash function.

Solution

1. Step 1: Understand linear probing concept

   Linear probing means when a collision happens, we look at the next slot in order, moving forward one by one.

2. Step 2: Compare options

   If a slot is occupied, check the next slot sequentially until an empty one is found. describes this exact process. Options B, C, and D describe other collision methods or resizing, not linear probing.

3. Final Answer:

   If a slot is occupied, check the next slot sequentially until an empty one 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 resizes the table
• Assuming linear probing uses a new hash function

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

D. (i - 1) % m

Solution

1. Step 1: Recall linear probing index calculation

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

2. Step 2: Check options

   Only (i + 1) % m uses (i + 1) % m, which correctly moves to the next slot circularly.

3. Final Answer:

   (i + 1) % m -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Adding 2 instead of 1
• Multiplying index instead of adding
• Subtracting index causing negative values

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

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Placing all keys at initial hash index
• Not wrapping around the table
• Confusing index positions

4. Given the following code snippet for linear probing insertion, what is the bug?

int insert(int[] table, int key) {
  int m = table.length;
  int i = key % m;
  while (table[i] != 0) {
    i = (i + 1) % m;
  }
  table[i] = key;
  return i;
}

medium

A. It does not handle the case when the table is full, causing an infinite loop.

B. The hash function should be key / m instead of key % m.

C. It inserts the key at the wrong index without probing.

D. It uses 0 to check empty slots, which is invalid for all keys.

Solution

1. Step 1: Analyze the while loop condition

   The loop continues while the slot is occupied (not zero). If the table is full, it loops forever because no empty slot is found.

2. Step 2: Check other options

   The hash function should be key / m instead of key % m. is wrong because modulo is correct for hashing. It inserts the key at the wrong index without probing. is wrong because probing is done. It uses 0 to check empty slots, which is invalid for all keys. assumes 0 is invalid, but 0 can be used as empty marker if keys are positive.

3. Final Answer:

   It does not handle the case when the table is full, causing an infinite loop. -> Option A

4. Quick Check:

   Full table causes infinite loop [OK]

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

Common Mistakes:

• Ignoring full table condition
• Misunderstanding hash function usage
• Assuming 0 cannot be empty slot marker

5. You have a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. Insert keys 10, 24, 31, 17, 3, 7 in order. After all insertions, which index will key 7 be stored at?

hard

A. 3

B. 4

C. 1

D. 6

Solution

1. Step 1: Calculate initial hashes and insert keys

   h(10)=3, insert at 3.
   h(24)=3, slot 3 occupied, try 4.
   h(31)=3, slots 3 and 4 occupied, try 5.
   h(17)=3, slots 3,4,5 occupied, try 6.
   h(3)=3, slots 3,4,5,6 occupied, try 0.
   h(7)=0, slot 0 occupied, try 1.

2. Step 2: Check slot 1 for key 7

   Slot 1 is empty, so key 7 is stored at index 1.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Linear probing finds next free slot [OK]

Hint: Probe next slots until empty to find key position [OK]

Common Mistakes:

• Stopping at initial hash index
• Not checking all occupied slots
• Miscounting index after wrap-around