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

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Insert key

↓

Compute hash index

↓

Check slot at index

↓

Slot empty?

Yes→Insert key here

No↓

Move to next index (linear probing)

↓

Repeat check until empty slot found or table full

Start by hashing the key to find an index. If the slot is empty, insert the key. If not, move step-by-step to the next slot until an empty one is found.

Execution Sample

DSA Javascript

let hashTable = new Array(5).fill(null);
let keys = [12, 22, 32];
for (let key of keys) {
  let index = key % 5;
  while (hashTable[index] !== null) {
    index = (index + 1) % 5;
  }
  hashTable[index] = key;
}

Insert keys 12, 22, and 32 into a hash table of size 5 using linear probing to handle collisions.

Execution Table

Step	Operation	Key	Computed Index	Slot Check	Pointer Moves	Hash Table State
1	Insert	12	12 % 5 = 2	Slot 2 empty	No moves	[null, null, 12, null, null]
2	Insert	22	22 % 5 = 2	Slot 2 occupied (12)	Move to 3	[null, null, 12, null, null]
2	Insert	22	Index 3	Slot 3 empty	No more moves	[null, null, 12, 22, null]
3	Insert	32	32 % 5 = 2	Slot 2 occupied (12)	Move to 3	[null, null, 12, 22, null]
3	Insert	32	Index 3	Slot 3 occupied (22)	Move to 4	[null, null, 12, 22, null]
3	Insert	32	Index 4	Slot 4 empty	No more moves	[null, null, 12, 22, 32]
4	End	-	-	-	-	[null, null, 12, 22, 32]

💡 All keys inserted; no empty slots found beyond index 4 for last key; insertion complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
hashTable	[null, null, null, null, null]	[null, null, 12, null, null]	[null, null, 12, 22, null]	[null, null, 12, 22, 32]	[null, null, 12, 22, 32]
index (for 12)	undefined	2	2	2	2
index (for 22)	undefined	undefined	3	3	3
index (for 32)	undefined	undefined	undefined	4	4

Key Moments - 3 Insights

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

Because the slot is already taken by another key, we use linear probing to check the next slot (see execution_table steps 2 and 3 where index moves from 2 to 3 and then 4).

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

Insertion stops because there is no space left. In this example, the table has empty slots, so insertion completes successfully (see exit_note).

Why do we use modulo (%) with the table size when moving to the next index?

Modulo ensures the index wraps around to the start of the table if it reaches the end, preventing out-of-bounds errors (see pointer moves in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the hashTable state after inserting key 22?

A [null, null, 12, null, 22]

B [null, null, 12, 22, null]

C [null, null, 22, null, null]

D [null, 22, 12, null, null]

💡 Hint

Check the hashTable State column at Step 2 in the execution_table.

At which step does the index move from 3 to 4 during insertion?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the Pointer Moves and Computed Index columns in execution_table rows for Step 3.

If the table size was 3 instead of 5, what would happen when inserting key 32?

A It would insert at index 2 without collision

B It would cause an infinite loop trying to find an empty slot

C It would insert at index 0 after probing

D It would overwrite existing keys

💡 Hint

Consider the modulo operation and table size in variable_tracker and how linear probing works.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute hash index: index = key % table_size
- If slot empty, insert key
- If occupied, move to next slot (index + 1) % table_size
- Repeat until empty slot found or table full
- Ensures all keys stored without chaining
- Simple, but can cause clustering

Full Transcript

This visualization shows how linear probing handles collisions in a hash table. When inserting a key, we compute its hash index using modulo operation. If the slot is empty, we insert the key there. If the slot is occupied, we move step-by-step to the next slot, wrapping around the table if needed, until we find an empty slot. The execution table traces inserting keys 12, 22, and 32 into a table of size 5. Key 12 goes to index 2 directly. Key 22 collides at index 2, so it moves to index 3. Key 32 collides at indexes 2 and 3, then moves to index 4. The variable tracker shows how the hash table and index variables change after each insertion. Key moments clarify why we move to next slots, what happens if the table is full, and why modulo is used for wrapping. The quiz tests understanding of the hash table state after insertions, pointer moves, and behavior with smaller table sizes.

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 at each slot to store multiple values.

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

D. Replace the existing value in the slot with the new value.

Solution

1. Step 1: Understand collision handling methods

   Linear probing handles collisions by searching the next available slot in a sequence.

2. Step 2: Identify linear probing behavior

   When a collision happens, linear probing checks the next slot one by one until it finds an empty slot.

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 collision means resizing immediately
• Replacing existing values instead of probing

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 + 3) % m

D. (i + 1) % m

Solution

1. Step 1: Recall linear probing index update

   Linear probing moves to the next slot by adding 1 to the current index.

2. Step 2: Apply modulo to wrap around

   To stay within table size, use modulo operation with table size m.

3. Final Answer:

   (i + 1) % m -> Option D

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:

• Using multiplication instead of addition
• Not using modulo to wrap index
• Subtracting instead of adding

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 (index: value)?

medium

A. 0: null, 1: null, 2: 7, 3: 12, 4: 17

B. 0: null, 1: 7, 2: null, 3: 12, 4: 17

C. 0: 7, 1: 12, 2: 17, 3: null, 4: null

D. 0: null, 1: 7, 2: 12, 3: 17, 4: null

Solution

1. Step 1: Calculate initial positions using hash function

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys initially map to index 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2 (empty). Insert 12: index 2 occupied, try 3 (empty), insert at 3. Insert 17: index 2 occupied, 3 occupied, try 4 (empty), insert at 4.

3. Final Answer:

   0: null, 1: null, 2: 7, 3: 12, 4: 17 -> Option A

4. Quick Check:

   Keys placed at 2, 3, 4 with probing [OK]

Hint: All keys hash to 2, probe next slots for empty [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Skipping slots incorrectly during probing
• Miscomputing hash values

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

const size = 7;
const table = new Array(size).fill(null);
function hash(key) {
  return key % size;
}
function insert(key) {
  let index = hash(key);
  while (table[index] !== null) {
    index = (index + 1) % size;
  }
  table[index] = key;
}
insert(10);
insert(17);
insert(24);
console.log(table);

medium

A. The hash function should use key % (size - 1) instead of key % size.

B. The table array should be initialized with zeros instead of null.

C. The insert function does not handle the case when the table is full, causing an infinite loop.

D. The index update in the while loop should subtract 1 instead of adding 1.

Solution

1. Step 1: Analyze insert function loop

   The while loop probes next slots until it finds an empty slot (null).

2. Step 2: Identify missing full table check

   If the table is full, the loop cycles endlessly without exit condition, causing infinite loop.

3. Final Answer:

   The insert function does not handle the case when the table is full, causing an infinite loop. -> Option C

4. Quick Check:

   Missing full table check causes infinite loop [OK]

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

Common Mistakes:

• Thinking modulo should be size-1
• Ignoring infinite loop possibility
• Confusing null with zero initialization

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5. You want to insert key 22. The hash function is h(k) = k % 10. Which index will key 22 be inserted into?

hard

A. 2

B. 6

C. 7

D. 5

Solution

1. Step 1: Calculate initial index for key 22

   22 % 10 = 2, so initial index is 2.

2. Step 2: Apply linear probing to find empty slot

   Indices 2, 3, 4, 5 are occupied. Next index is 6, which is free.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Start at 2, probe until free slot at 6 [OK]

Hint: Probe forward from hash index until empty slot found [OK]

Common Mistakes:

• Inserting at first hashed index ignoring occupancy
• Stopping probing too early
• Choosing wrong next index