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

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Start: Insert key

↓

Compute hash index

↓

Check slot at index

↓

Slot empty?

Yes→Insert key here

No↓

Move to next index (linear probing)

↓

Back to Check slot

↓

If full circle reached

→Table full, cannot insert

Insert key by hashing to index, if occupied move step-by-step to next slot until empty found or full circle.

Execution Sample

DSA Typescript

const table = new Array(5).fill(null);
function insert(key) {
  let index = key % table.length;
  let startIndex = index;
  while (table[index] !== null) {
    index = (index + 1) % table.length;
    if (index === startIndex) {
      throw new Error('Hash table is full, cannot insert key ' + key);
    }
  }
  table[index] = key;
}

insert(7); insert(12); insert(17);

Insert keys 7, 12, 17 into a hash table of size 5 using linear probing for collisions.

Execution Table

Step	Operation	Key	Index Checked	Slot Empty?	Action	Table State
1	Insert	7	7 % 5 = 2	Yes	Insert 7 at index 2	[null, null, 7, null, null]
2	Insert	12	12 % 5 = 2	No (7 present)	Probe next index 3	[null, null, 7, null, null]
3	Insert	12	3	Yes	Insert 12 at index 3	[null, null, 7, 12, null]
4	Insert	17	17 % 5 = 2	No (7 present)	Probe next index 3	[null, null, 7, 12, null]
5	Insert	17	3	No (12 present)	Probe next index 4	[null, null, 7, 12, null]
6	Insert	17	4	Yes	Insert 17 at index 4	[null, null, 7, 12, 17]
7	End	-	-	-	All keys inserted	[null, null, 7, 12, 17]

💡 All keys inserted successfully; linear probing resolved collisions by checking next slots.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
table	[null, null, null, null, null]	[null, null, 7, null, null]	[null, null, 7, null, null]	[null, null, 7, 12, null]	[null, null, 7, 12, null]	[null, null, 7, 12, null]	[null, null, 7, 12, 17]	[null, null, 7, 12, 17]
index	undefined	2	2 then 3	3	2 then 3 then 4	4	4	4

Key Moments - 3 Insights

Why do we check the next index when the slot is occupied?

Because the hash index is already taken by another key, linear probing moves step-by-step to find the next empty slot, as shown in steps 2, 4, and 5 in the execution_table.

What happens if we reach the end of the table while probing?

We wrap around to the start of the table using modulo operation, ensuring we check all slots. This is implied in the index calculation (index + 1) % table.length.

Can the table become full and prevent insertion?

Yes, if all slots are occupied, the probing will circle back to the start without finding an empty slot, and insertion fails. This is noted in the concept_flow as 'Table full, cannot insert'.

Visual Quiz - 3 Questions

Look at the execution_table, what is the index checked when inserting key 12 at step 3?

A 4

B 2

C 3

D 1

💡 Hint

Check the 'Index Checked' column for step 3 in the execution_table.

At which step does the key 17 get inserted into the table?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the 'Action' and 'Table State' columns to see when 17 is placed.

If the table size was 3 instead of 5, what would happen when inserting key 17 after 7 and 12?

A Inserted at index 0 after probing

B Inserted at index 2 without probing

C Insertion fails due to full table

D Inserted at index 1 after probing

💡 Hint

Consider the table size and how many keys are inserted; check concept_flow for full table scenario.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute hash index for key.
- If slot empty, insert key.
- If occupied, move to next slot (index + 1) % size.
- Repeat until empty slot found or full circle.
- Handles collisions by probing linearly.
- Table full means insertion fails.

Full Transcript

This concept shows how to handle collisions in a hash table using open addressing with linear probing. When inserting a key, we compute its hash index. 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 or determine the table is full. The execution example inserts keys 7, 12, and 17 into a table of size 5. Key 7 goes to index 2 directly. Key 12 collides at index 2, so it moves to index 3. Key 17 collides at indices 2 and 3, then inserts at index 4. The variable tracker shows how the table and index change after each step. Key moments clarify why probing is needed, how wrapping works, and what happens if the table is full. The quiz tests understanding of index checking, insertion steps, and full table scenarios.

Practice

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

easy

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

B. Use a linked list to store multiple values at the same index.

C. If a collision occurs, check the next slot sequentially until an empty slot is found.

D. Replace the existing value at the collided slot with the new value.

Solution

1. Step 1: Understand collision handling

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain linear probing method

   Linear probing resolves collisions by checking the next slot in order until an empty slot is found.

3. Final Answer:

   If a collision occurs, check the next slot sequentially until an empty slot is found. -> Option C

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 on collision

2. Which of the following TypeScript code snippets correctly implements the linear probing step to find the next index after a collision in a hash table of size size?

easy

A. let nextIndex = currentIndex % size;

B. let nextIndex = (currentIndex * 2) % size;

C. let nextIndex = (currentIndex - 1) % size;

D. let nextIndex = (currentIndex + 1) % size;

Solution

1. Step 1: Understand linear probing index calculation

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

2. Step 2: Check code correctness

   let nextIndex = (currentIndex + 1) % size; correctly calculates nextIndex as (currentIndex + 1) % size, ensuring wrap-around.

3. Final Answer:

   let nextIndex = (currentIndex + 1) % size; -> Option D

4. Quick Check:

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

Hint: Add 1 and mod by size for next slot [OK]

Common Mistakes:

• Multiplying index instead of adding
• Subtracting index causing negative values
• Not using modulo for wrap-around

3. Consider a hash table of size 5 using linear probing. The hash function is h(key) = key % 5. Insert keys in this order: 7, 12, 17. What is the final state of the hash table (index: value)?

medium

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

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

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

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

Solution

1. Step 1: Calculate initial hash indices

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

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is occupied, try 3 (empty), insert 12. For 17, indices 2 and 3 occupied, try 4 (empty), insert 17.

3. Final Answer:

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

4. Quick Check:

   All keys start at 2, linear probe fills next slots [OK]

Hint: All keys hash same, fill next slots sequentially [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Not wrapping around the table
• Misplacing keys at wrong indices

4. The following TypeScript code tries to insert keys into a hash table using linear probing. What is the bug that causes an infinite loop?

const size = 5;
const table = new Array(size).fill(null);
function hash(key: number) { return key % size; }
function insert(key: number) {
  let index = hash(key);
  while (table[index] !== null) {
    index = (index + 1) % size;
  }
  table[index] = key;
}
insert(5);
insert(10);
insert(15);
insert(20);
insert(25);
insert(30);

medium

A. No check for full table causing infinite loop when table is full.

B. Hash function is incorrect and returns negative indices.

C. Array initialization with null is wrong; should use undefined.

D. Insert function does not update index inside the loop.

Solution

1. Step 1: Analyze insert loop behavior

   The while loop keeps moving index until an empty slot is found.

2. Step 2: Identify missing full table check

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

3. Final Answer:

   No check for full table causing infinite loop when table is full. -> Option A

4. Quick Check:

   Full table without exit causes infinite loop [OK]

Hint: Add full table check to avoid infinite loop [OK]

Common Mistakes:

• Assuming hash function returns negative
• Thinking null vs undefined causes loop
• Forgetting to update index inside loop

5. You have a hash table of size 7 using linear probing. The hash function is h(key) = key % 7. You insert keys: 14, 21, 28, 35, 42. Then you delete key 21. What is the correct way to handle deletion to avoid search errors in linear probing?

hard

A. Set the slot to null immediately to free it for new insertions.

B. Mark the slot as a special 'deleted' marker instead of null to continue probing.

C. Rehash the entire table after deletion to fix collisions.

D. Do nothing; deletion is not needed in linear probing.

Solution

1. Step 1: Understand deletion problem in linear probing

   Setting slot to null breaks the probe chain, causing search failures for keys after deleted slot.

2. Step 2: Use special 'deleted' marker

   Marking slot as 'deleted' allows probing to continue while allowing new insertions.

3. Final Answer:

   Mark the slot as a special 'deleted' marker instead of null to continue probing. -> Option B

4. Quick Check:

   Deleted marker keeps probe chain intact [OK]

Hint: Use 'deleted' marker slot, not null, after deletion [OK]

Common Mistakes:

• Setting slot to null breaks search chain
• Rehashing entire table unnecessarily
• Ignoring deletion impact on probing