Collision Handling Using Open Addressing Linear Probing in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Probing Insertions

What is the state of the hash table after inserting keys 10, 20, 30, 40 into a hash table of size 5 using linear probing with hash function h(key) = key % 5?

DSA Java

int size = 5;
int[] hashTable = new int[size];
Arrays.fill(hashTable, -1);
int[] keys = {10, 20, 30, 40};
for (int key : keys) {
    int index = key % size;
    while (hashTable[index] != -1) {
        index = (index + 1) % size;
    }
    hashTable[index] = key;
}
System.out.println(Arrays.toString(hashTable));

A [10, 20, -1, 30, 40]

B [10, -1, 20, 30, 40]

C [10, 20, 30, -1, 40]

D [10, 20, 30, 40, -1]

💡 Hint

Remember to check the index and move to the next slot if occupied.

The hash function is key % 5. For keys 10, 20, 30, 40, the initial indices are all 0, 0, 0, and 0 respectively.

Insert 10 at index 0.

Insert 20: index 0 occupied, probe to index 1.

Insert 30: probes to index 2.

Insert 40: probes to index 3.

Final state: [10, 20, 30, 40, -1]

❓ Predict Output

intermediate

Result of Searching in Linear Probing Hash Table

Given a hash table of size 7 with keys inserted using linear probing and hash function h(key) = key % 7, the table is [14, 21, 28, -1, -1, -1, -1]. What is the index returned when searching for key 28?

DSA Java

int size = 7;
int[] hashTable = {14, 21, 28, -1, -1, -1, -1};
int key = 28;
int index = key % size;
int startIndex = index;
while (hashTable[index] != key) {
    index = (index + 1) % size;
    if (index == startIndex || hashTable[index] == -1) {
        index = -1;
        break;
    }
}
System.out.println(index);

A 2

B 0

C -1

D 1

💡 Hint

Check the initial index and probe until key is found or empty slot reached.

Key 28 hashes to 28 % 7 = 0. Index 0 has 14, not 28, so probe next index 1 with 21, still not 28, probe index 2 which has 28. So index 2 is returned.

🔧 Debug

advanced

Identify the Bug in Linear Probing Insert Method

What error will occur when running this linear probing insert method for a full hash table?

DSA Java

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

A ArrayIndexOutOfBoundsException

B Infinite loop

C No error, inserts successfully

D NullPointerException

💡 Hint

What happens if the table is full and no slot is free?

If the hash table is full, the while loop never finds an empty slot (-1), so it keeps cycling through indices endlessly causing an infinite loop.

🧠 Conceptual

advanced

Why Linear Probing Causes Clustering?

Which statement best explains why linear probing causes primary clustering in hash tables?

A Because it places collided keys in the next available slot, causing long runs of occupied slots.

B Because it uses a secondary hash function to resolve collisions.

C Because it stores keys in linked lists at each index.

D Because it rehashes the entire table on every insertion.

💡 Hint

Think about how keys are placed after collisions.

Linear probing places collided keys in the next free slot, which can create clusters of consecutive occupied slots, called primary clustering.

🚀 Application

expert

Final Hash Table State After Mixed Operations

Given a hash table of size 7 using linear probing and hash function h(key) = key % 7, perform these operations in order: insert 10, insert 24, insert 31, delete 24, insert 17. What is the final state of the hash table? Use -1 for empty slots and -2 for deleted slots.

DSA Java

int size = 7;
int[] hashTable = new int[size];
Arrays.fill(hashTable, -1);
// Insert 10
int index = 10 % size;
while (hashTable[index] != -1 && hashTable[index] != -2) {
    index = (index + 1) % size;
}
hashTable[index] = 10;
// Insert 24
index = 24 % size;
while (hashTable[index] != -1 && hashTable[index] != -2) {
    index = (index + 1) % size;
}
hashTable[index] = 24;
// Insert 31
index = 31 % size;
while (hashTable[index] != -1 && hashTable[index] != -2) {
    index = (index + 1) % size;
}
hashTable[index] = 31;
// Delete 24
index = 24 % size;
while (hashTable[index] != 24) {
    index = (index + 1) % size;
}
hashTable[index] = -2;
// Insert 17
index = 17 % size;
while (hashTable[index] != -1 && hashTable[index] != -2) {
    index = (index + 1) % size;
}
hashTable[index] = 17;
System.out.println(Arrays.toString(hashTable));

A [-1, -1, 10, 17, -2, 31, -1]

B [-1, 10, -2, 17, -1, 31, -1]

C [-1, 10, 17, -2, -1, 31, -1]

D [-1, -1, -1, 10, 17, 31, -1]

💡 Hint

Track each insertion and deletion carefully, noting deleted slots can be reused.

Insert 10: 10 % 7 = 3 → index 3: 10

Insert 24: 24 % 7 = 3 occupied → probe 4: 24

Insert 31: 31 % 7 = 3 occ → 4 occ → 5: 31

Delete 24: start at 3 (10 !=24) → 4: set to -2

Insert 17: 17 % 7 = 3 occ → 4 (-2): stop and insert 17

Final: [-1, -1, -1, 10, 17, 31, -1]

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