Collision Handling Using Open Addressing Linear Probing in DSA Java - Build from Scratch

Collision Handling Using Open Addressing Linear Probing

📖 Scenario: Imagine you are creating a simple phone book application that stores phone numbers using a hash table. Sometimes, two phone numbers might want to be stored in the same spot. To handle this, you will use a method called linear probing to find the next free spot.

🎯 Goal: Build a hash table using an array and implement collision handling using open addressing with linear probing. You will insert phone numbers and then display the final state of the hash table.

📋 What You'll Learn

Create an integer array called hashTable of size 7 initialized with -1 to represent empty slots.

Create an integer variable called size and set it to 7.

Write a method called linearProbingInsert that takes an integer key and inserts it into hashTable using linear probing.

Insert the keys 10, 20, 15, 7, and 32 into the hash table using linearProbingInsert.

Print the final state of hashTable showing all elements separated by spaces.

💡 Why This Matters

🌍 Real World

Hash tables are used in many applications like databases, caches, and phone books to store and quickly find data.

💼 Career

Understanding collision handling in hash tables is important for software developers working on efficient data storage and retrieval systems.

1

Create the hash table array

Create an integer array called hashTable of size 7 and initialize all elements to -1.

DSA Java

// Create the hashTable array of size 7 and initialize all elements to -1
// Your code here

Hint

Use a for loop to set each element of hashTable to -1.

2

Create the size variable

Create an integer variable called size and set it to 7.

DSA Java

public class LinearProbing {
    static int[] hashTable = new int[7];
    // Create size variable
    // Your code here

    public static void main(String[] args) {
        for (int i = 0; i < hashTable.length; i++) {
            hashTable[i] = -1;
        }
    }
}

Hint

Declare size as a static integer variable and assign 7.

3

Implement linear probing insert method and insert keys

Write a static method called linearProbingInsert that takes an integer key and inserts it into hashTable using linear probing. Then, insert the keys 10, 20, 15, 7, and 32 by calling linearProbingInsert for each key inside main.

DSA Java

public class LinearProbing {
    static int[] hashTable = new int[7];
    static int size = 7;

    public static void linearProbingInsert(int key) {
        // Your code here
    }

    public static void main(String[] args) {
        for (int i = 0; i < hashTable.length; i++) {
            hashTable[i] = -1;
        }
        // Insert keys 10, 20, 15, 7, 32 using linearProbingInsert
        // Your code here
    }
}

Hint

Use key % size to find the initial index. If occupied, move to the next index until an empty slot (-1) is found.

4

Print the final hash table

Print the elements of hashTable separated by spaces in one line inside main after inserting the keys.

DSA Java

public class LinearProbing {
    static int[] hashTable = new int[7];
    static int size = 7;

    public static void linearProbingInsert(int key) {
        int index = key % size;
        int startIndex = index;
        while (hashTable[index] != -1) {
            index = (index + 1) % size;
            if (index == startIndex) {
                return; // Table full, do nothing
            }
        }
        hashTable[index] = key;
    }

    public static void main(String[] args) {
        for (int i = 0; i < hashTable.length; i++) {
            hashTable[i] = -1;
        }
        linearProbingInsert(10);
        linearProbingInsert(20);
        linearProbingInsert(15);
        linearProbingInsert(7);
        linearProbingInsert(32);
        // Print the hashTable
        // Your code here
    }
}

Hint

Use a for loop to print each element of hashTable followed by a space.

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