Collision Handling Using Open Addressing Linear Probing in DSA Typescript

Mental Model

When two items want the same spot in a table, we look for the next empty spot in a line to put the new item.

Analogy: Imagine parking cars in a row of parking spots. If your favorite spot is taken, you move forward to the next empty spot and park there.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Dry Run Walkthrough

Input: Insert keys 10, 20, 30 into a hash table of size 10 using linear probing. Hash function: key % 10.

Goal: Place all keys in the table without overwriting existing keys by moving to the next empty spot when collision happens.

Step 1: Insert key 10 at index 0 (10 % 10 = 0).

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Index 0 is empty, so key 10 is placed there.

Step 2: Insert key 20 at index 0 (20 % 10 = 0), collision occurs.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Index 0 is taken by 10, so we must find next empty spot.

Step 3: Check index 1, it is empty, insert key 20 there.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [20] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Linear probing moves forward to find empty spot for key 20.

Step 4: Insert key 30 at index 0 (30 % 10 = 0), collision occurs.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [20] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Index 0 is taken by 10, need to find next empty spot.

Step 5: Check index 1, taken by 20, move to index 2.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [20] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Keep moving forward to find empty spot.

Step 6: Index 2 is empty, insert key 30 there.

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [20] -> [30] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Why: Found empty spot for key 30 using linear probing.

Result:

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Table: [10] -> [20] -> [30] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Annotated Code

DSA Typescript

class HashTable {
  table: (number | null)[];
  size: number;

  constructor(size: number) {
    this.size = size;
    this.table = new Array(size).fill(null);
  }

  hash(key: number): number {
    return key % this.size;
  }

  insert(key: number): void {
    let index = this.hash(key);
    // linear probing to find empty slot
    while (this.table[index] !== null) {
      index = (index + 1) % this.size; // move to next index
    }
    this.table[index] = key;
  }

  printTable(): void {
    let result = '';
    for (let i = 0; i < this.size; i++) {
      result += `[${this.table[i] !== null ? this.table[i] : ' '}]`;
      if (i !== this.size - 1) result += ' -> ';
    }
    console.log(result);
  }
}

// Driver code
const ht = new HashTable(10);
ht.insert(10);
ht.insert(20);
ht.insert(30);
ht.printTable();

let index = this.hash(key);

Calculate initial index using hash function

while (this.table[index] !== null) {

Check if current index is occupied to handle collision

index = (index + 1) % this.size;

Move to next index in circular manner for linear probing

this.table[index] = key;

Insert key at found empty index

Output

[10] -> [20] -> [30] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> [ ]

Complexity Analysis

Time: O(n) in worst case because linear probing may check many slots if many collisions happen

Space: O(n) because we store keys in an array of size n

vs Alternative: Compared to chaining which uses linked lists, linear probing keeps all data in one array but may have clustering causing slower lookups

Edge Cases

Inserting into a full table

The insert loop cycles through all slots and finds no empty spot, causing infinite loop or failure

DSA Typescript

while (this.table[index] !== null) {

Inserting duplicate keys

Duplicates are inserted as separate entries in next available slots

DSA Typescript

while (this.table[index] !== null) {

Empty table insertion

Key is inserted directly at hashed index without probing

DSA Typescript

while (this.table[index] !== null) {

When to Use This Pattern

When you see a hash table with collisions and need to store all keys in one array, use linear probing to find next empty slot and avoid overwriting.

Common Mistakes

Mistake: Not wrapping index back to start of table when reaching end
Fix: Use modulo operation to cycle index: index = (index + 1) % size

Mistake: Stopping probing too early without checking all slots
Fix: Continue probing until an empty slot is found or full cycle is detected

Summary

It handles collisions in a hash table by moving forward to the next empty spot in the array.

Use it when you want to store keys in a fixed-size array and handle collisions without extra data structures.

The key insight is to keep checking the next slot in a circle until you find an empty place.

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