Collision Handling Using Open Addressing Linear Probing in DSA Java - Execution Trace

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Start: Insert key

↓

Compute hash index

↓

Check slot at index

↓

Empty?

↓

Insert

↓

Repeat check slot

↓

Done

Start by hashing the key to find an index. If the slot is empty, insert. If occupied, move to the next slot and repeat until an empty slot is found.

Execution Sample

DSA Java

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

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

This code inserts keys into a hash table using linear probing to handle collisions.

Execution Table

Step	Operation	Key	Computed Index	Slot Status	Pointer Changes	Visual State
1	Insert key	10	10 % 7 = 3	Empty	index=3	[null, null, null, 10, null, null, null]
2	Insert key	24	24 % 7 = 3	Occupied (10)	index=4	[null, null, null, 10, 24, null, null]
3	Insert key	31	31 % 7 = 3	Occupied (10)	index=4 occupied (24), move to 5	[null, null, null, 10, 24, 31, null]
4	Insert key	17	17 % 7 = 3	Occupied (10)	index=4 occupied (24), 5 occupied (31), move to 6	[null, null, null, 10, 24, 31, 17]
5	Insert key	3	3 % 7 = 3	Occupied (10)	index=4 occupied (24), 5 occupied (31), 6 occupied (17), move to 0	[3, null, null, 10, 24, 31, 17]
6	Insert key	10	10 % 7 = 3	Occupied (10)	index=4 occupied (24), 5 occupied (31), 6 occupied (17), 0 occupied (3), move to 1	[3, 10, null, 10, 24, 31, 17]
7	Insert key	7	7 % 7 = 0	Occupied (3)	index=1 occupied (10), move to 2	[3, 10, 7, 10, 24, 31, 17]
8	Insert key	14	14 % 7 = 0	Occupied (3)	index=1 occupied (10), 2 occupied (7), move to 3 occupied (10), 4 occupied (24), 5 occupied (31), 6 occupied (17), table full	[3, 10, 7, 10, 24, 31, 17]

💡 Insertion stops when an empty slot is found or the table is full (step 8).

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
index	N/A	3	4	5	6	0	1	2	N/A
table	[null, null, null, null, null, null, null]	[null, null, null, 10, null, null, null]	[null, null, null, 10, 24, null, null]	[null, null, null, 10, 24, 31, null]	[null, null, null, 10, 24, 31, 17]	[3, null, null, 10, 24, 31, 17]	[3, 10, null, 10, 24, 31, 17]	[3, 10, 7, 10, 24, 31, 17]	[3, 10, 7, 10, 24, 31, 17]

Key Moments - 3 Insights

Why do we move to the next index when the computed index slot is occupied?

Because the slot is already taken by another key, linear probing moves sequentially to find the next empty slot, as shown in steps 2 and 3 of the execution_table.

What happens when the table is full and no empty slot is found?

Insertion stops because there is no space left to insert the new key, as seen in step 8 where all slots are occupied and the key cannot be inserted.

Why do we use modulo operation when moving to the next index?

Modulo ensures the index wraps around to the start of the table when reaching the end, preventing out-of-bound errors, demonstrated by index moving from 6 to 0 in step 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the index used to insert key 31?

A 3

B 4

C 5

D 6

💡 Hint

Refer to step 3 in the execution_table where key 31 is inserted.

At which step does the insertion fail due to the table being full?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Check the exit_note and step 8 in the execution_table.

If the table size was increased, how would the insertion of key 14 change?

A It would find an empty slot without wrapping around.

B It would insert at index 0 immediately.

C It would fail earlier due to collisions.

D It would not change the insertion process.

💡 Hint

Consider how more empty slots affect linear probing in the execution_table.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute index = key % table_size
- If slot empty, insert key
- If occupied, move to next index (index+1)%size
- Repeat until empty slot found or table full
- Wrap around using modulo to stay within table bounds

Full Transcript

This visualization shows how keys are inserted into a hash table using linear probing to handle collisions. Each key is hashed to an index. If the slot is empty, the key is placed there. If occupied, the algorithm checks the next slot sequentially, wrapping around the table if needed, until an empty slot is found or the table is full. The execution table tracks each insertion step, showing the key, computed index, slot status, pointer changes, and the table's visual state. Variable tracking shows how the index and table change after each step. Key moments clarify why we move to the next index on collision, what happens when the table is full, and why modulo is used for wrapping. The quiz tests understanding of index calculation, insertion failure, and effects of table size on insertion.

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