Collision Handling Using Open Addressing Linear Probing in DSA Typescript - Deep Dive

Overview - Collision Handling Using Open Addressing Linear Probing

What is it?

Collision Handling Using Open Addressing Linear Probing is a method to resolve conflicts when two keys want to occupy the same spot in a hash table. Instead of chaining, it searches for the next free slot in a linear sequence. This way, all elements stay inside the hash table array itself. It helps keep data organized and easy to find even when collisions happen.

Why it matters

Without a way to handle collisions, hash tables would fail to store multiple keys that map to the same position, causing data loss or slow lookups. Linear probing keeps the table efficient and fast by finding nearby empty spots, making hash tables practical for many real-world uses like databases and caches. Without it, many systems would be slower or unreliable.

Where it fits

Before learning this, you should understand basic hash tables and hashing functions. After mastering linear probing, you can explore other collision methods like quadratic probing or double hashing, and then move on to advanced hash table designs and performance tuning.

Mental Model

Core Idea

When a spot in the hash table is taken, linear probing checks the next spots one by one until it finds an empty one to store the new key.

Think of it like...

Imagine parking in a row of parking spots. If your assigned spot is taken, you walk forward to the next spot until you find an empty one to park your car.

Hash Table Array:
┌───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │
├───┼───┼───┼───┼───┼───┤
│ A │ B │   │ C │   │   │
└───┴───┴───┴───┴───┴───┘

Insert key D with hash index 2:
Check index 2: empty -> place D here.

Insert key E with hash index 1:
Index 1 taken by B -> check index 2 (taken by D) -> check index 3 (taken by C) -> check index 4 (empty) -> place E at index 4.

Build-Up - 7 Steps

1

Foundation

Understanding Hash Tables Basics

Concept: Learn what a hash table is and how hashing maps keys to indexes.

A hash table stores data in an array using a hash function that converts keys into array indexes. For example, a key 'apple' might hash to index 3. This lets us find 'apple' quickly by going directly to index 3.

Result

You understand how keys map to positions in a hash table.

Knowing how hashing works is essential before handling collisions because collisions happen when two keys map to the same index.

2

Foundation

What Causes Collisions in Hash Tables

Concept: Understand why collisions happen when different keys hash to the same index.

Since hash functions map many possible keys to a limited array size, sometimes two keys get the same index. For example, 'apple' and 'grape' might both hash to index 3. This is called a collision.

Result

You recognize collisions as a natural problem in hash tables.

Realizing collisions are unavoidable helps you appreciate why collision handling methods like linear probing are necessary.

3

Intermediate

Open Addressing Collision Resolution

Concept: Learn the open addressing approach where all keys stay inside the array and collisions are resolved by searching for free slots.

Instead of using linked lists for collisions, open addressing looks for another empty spot in the array. When a collision occurs, it probes other indexes until it finds an empty one to store the key.

Result

You understand the basic idea of open addressing as a collision handling method.

Knowing open addressing keeps all data in one array, which can improve cache performance and simplify memory management.

4

Intermediate

Linear Probing Step-by-Step

🤔Before reading on: do you think linear probing checks indexes randomly or in a fixed order? Commit to your answer.

Concept: Linear probing checks the next index in order, wrapping around the array if needed, to find an empty slot.

When inserting a key, calculate its hash index. If that spot is taken, check the next index (index + 1). If that is taken, check the next one, and so on, until an empty spot is found. This is called linear probing.

Result

You can insert keys using linear probing and understand how it searches for free slots.

Understanding the fixed step of +1 in linear probing helps predict where keys will be stored and how clustering can happen.

5

Intermediate

Searching and Deleting with Linear Probing

🤔Before reading on: when searching for a key, do you stop at the first empty slot or keep searching? Commit to your answer.

Concept: Searching follows the same linear probing sequence until the key is found or an empty slot is reached. Deletion requires special handling to avoid breaking the search chain.

To search, start at the hash index and check each slot in order. If the key is found, return it. If an empty slot is found before the key, it means the key is not in the table. For deletion, mark the slot as deleted (a special marker) instead of empty to keep the search chain intact.

Result

You can search and delete keys correctly using linear probing.

Knowing why deleted slots need special markers prevents search failures and data loss.

6

Advanced

Handling Clustering and Performance Issues

🤔Before reading on: do you think linear probing causes keys to spread evenly or cluster together? Commit to your answer.

Concept: Linear probing can cause clustering where groups of keys build up, slowing down insertions and searches.

When many keys cluster, linear probing must check many slots, reducing performance. This is called primary clustering. Techniques like resizing the table or using other probing methods can reduce clustering.

Result

You understand the performance tradeoffs of linear probing and when it slows down.

Recognizing clustering helps you decide when to switch to better collision methods or resize the table.

7

Expert

Implementing Linear Probing in TypeScript

🤔Before reading on: do you think the insert function should stop immediately after finding an empty slot or continue searching? Commit to your answer.

Concept: Learn a complete TypeScript implementation of linear probing with insert, search, and delete operations.

```typescript class LinearProbingHashTable { private table: (string | null | string)[]; private size: number; private deletedMarker = '__deleted__'; constructor(size: number) { this.size = size; this.table = new Array(size).fill(null); } private hash(key: string): number { let hash = 0; for (const char of key) { hash = (hash * 31 + char.charCodeAt(0)) % this.size; } return hash; } insert(key: string): void { let index = this.hash(key); const startIndex = index; while (this.table[index] !== null && this.table[index] !== this.deletedMarker) { if (this.table[index] === key) return; // Key already exists index = (index + 1) % this.size; if (index === startIndex) throw new Error('Hash table is full'); } this.table[index] = key; } search(key: string): boolean { let index = this.hash(key); const startIndex = index; while (this.table[index] !== null) { if (this.table[index] === key) return true; index = (index + 1) % this.size; if (index === startIndex) return false; } return false; } delete(key: string): void { let index = this.hash(key); const startIndex = index; while (this.table[index] !== null) { if (this.table[index] === key) { this.table[index] = this.deletedMarker; return; } index = (index + 1) % this.size; if (index === startIndex) return; } } printTable(): void { console.log(this.table.map((v, i) => `${i}: ${v}`).join(' | ')); } } // Example usage: const ht = new LinearProbingHashTable(7); ht.insert('apple'); ht.insert('grape'); ht.insert('banana'); ht.printTable(); console.log('Search grape:', ht.search('grape')); ht.delete('grape'); ht.printTable(); console.log('Search grape:', ht.search('grape')); ```

Result

The hash table stores keys with collisions resolved by linear probing. Insertions, searches, and deletions work correctly, and the table state prints showing keys and empty or deleted slots.

Seeing a full implementation clarifies how linear probing works in practice and highlights the importance of handling deleted slots carefully.

Under the Hood

Linear probing uses a simple arithmetic sequence to find the next slot: (current_index + 1) modulo table_size. This ensures the search wraps around the array. The table stores keys directly, and deleted slots are marked specially to keep search chains intact. The hash function distributes keys, but collisions cause clusters that slow down operations.

Why designed this way?

Linear probing was designed for simplicity and speed, using only the array without extra pointers or memory. It trades off some clustering risk for cache-friendly access and easy implementation. Alternatives like chaining require extra memory and pointers, which were costly in early computing.

┌───────────────┐
│ Hash Function │
└──────┬────────┘
       │ key
       ▼
┌───────────────┐
│ Initial Index │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Check slot at index          │
│ If empty -> insert key       │
│ Else -> index = (index + 1) % size
│ Repeat until empty slot      │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does linear probing always find an empty slot if the table is not full? Commit yes or no.

Common Belief: Linear probing will always find an empty slot if the table has space.

Reality: If the table is full or nearly full, linear probing can loop endlessly or fail to find a slot due to clustering and deleted markers.

Why it matters: Assuming infinite success can cause infinite loops or crashes in real systems when the table is full.

Quick: When deleting a key, can you just set its slot to null? Commit yes or no.

Common Belief: You can delete a key by setting its slot to null (empty).

Reality: Setting a slot to null breaks the search chain, causing searches for keys inserted after that slot to fail.

Why it matters: Incorrect deletion leads to missing keys during search, causing data loss or incorrect results.

Quick: Does linear probing spread keys evenly across the table? Commit yes or no.

Common Belief: Linear probing spreads keys evenly, preventing clustering.

Reality: Linear probing causes primary clustering where groups of keys build up, slowing down operations.

Why it matters: Ignoring clustering leads to poor performance and slow lookups in large tables.

Expert Zone

1

Deleted slots must be marked specially to maintain search chains, but too many deleted slots degrade performance and require table rehashing.

2

The choice of table size (preferably prime) affects clustering and probing efficiency significantly.

3

Linear probing's cache friendliness can outperform other methods despite clustering, especially in small to medium tables.

When NOT to use

Avoid linear probing when the load factor is high (above 0.7) or when deletions are frequent, as clustering and deleted slots degrade performance. Use alternatives like quadratic probing, double hashing, or chaining in these cases.

Production Patterns

Linear probing is used in performance-critical systems like in-memory caches and databases where memory locality matters. It is often combined with dynamic resizing and careful hash function choice to balance speed and collision handling.

Connections

Quadratic Probing

Alternative collision resolution method that uses a quadratic function to find next slots instead of linear steps.

Understanding linear probing helps grasp quadratic probing as a way to reduce clustering by spreading probes more widely.

Cache Memory Optimization

Linear probing benefits from accessing contiguous memory locations, improving cache hits.

Knowing how linear probing accesses memory sequentially explains why it can be faster than chaining despite clustering.

Parking Lot Management

Both involve finding the next available spot in a sequence when the preferred spot is taken.

Recognizing this pattern in real life helps understand the probing sequence and its challenges like clustering.

Common Pitfalls

#1 Deleting a key by setting its slot to null breaks search chains.

Wrong approach:

hashTable[index] = null; // delete key

Correct approach:

hashTable[index] = deletedMarker; // mark as deleted

Root cause:

Misunderstanding that empty slots stop searches, so marking deleted slots differently preserves search continuity.

#2 Not handling full table leads to infinite loops during insertion.

Wrong approach:

while (table[index] !== null) { index = (index + 1) % size; } // no full check

Correct approach:

let start = index;
do { if (table[index] === null) break; index = (index + 1) % size; } while (index !== start);
if (index === start) throw new Error('Table full');

Root cause:

Ignoring the possibility that all slots are taken causes endless probing.

#3 Choosing a table size that is a power of two increases collisions.

Wrong approach:

const size = 16; // power of two

Correct approach:

const size = 17; // prime number

Root cause:

Poor table size choice causes hash function to produce many collisions, worsening clustering.

Key Takeaways

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

Deleted slots must be specially marked to avoid breaking search chains and losing keys.

Clustering is a key drawback of linear probing that slows down operations as the table fills.

Choosing a good table size and hash function helps reduce collisions and improve performance.

Linear probing is simple, cache-friendly, and effective for moderate load factors but has limits in heavy use cases.

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