Speed:

Linear Probing Hash Table

Average: O(1)Worst: O(n)Space: O(n)

↗️How Linear Probing Works

Linear Probing is a collision resolution technique for hash tables that uses consecutive slots to resolve collisions. When a collision occurs at index i, the algorithm checks slots i+1, i+2, i+3, ... until an empty slot is found.

The probing sequence follows the formula:

h(k, i) = (h(k) + i) mod m

where k = key, i = probe number (0, 1, 2, ...), m = table size

Simple implementation: Easy to understand and code
Cache-friendly: Sequential memory access improves performance
Primary clustering: Keys tend to cluster together
Tombstone deletion: Mark deleted slots to maintain probe chains

💻Implementation

// Linear Probing Hash Table Implementation
class LinearProbingHashTable {
  constructor(size = 11) {
    this.size = size;
    this.table = new Array(size).fill(null);
    this.deleted = new Array(size).fill(false); // Track deleted slots
    this.count = 0;
  }
  
  hash(key) {
    return key % this.size;
  }
  
  insert(key) {
    if (this.count >= this.size * 0.7) {
      this.resize();
    }
    
    let index = this.hash(key);
    
    // Linear probing: check consecutive slots
    while (this.table[index] !== null && this.table[index] !== key) {
      if (this.deleted[index]) break; // Can use deleted slot
      index = (index + 1) % this.size;
    }
    
    if (this.table[index] !== key) {
      this.table[index] = key;
      this.deleted[index] = false;
      this.count++;
    }
    return true;
  }
  
  search(key) {
    let index = this.hash(key);
    let probes = 0;
    
    while (this.table[index] !== null || this.deleted[index]) {
      if (this.table[index] === key && !this.deleted[index]) {
        return index; // Found
      }
      index = (index + 1) % this.size;
      probes++;
      
      if (probes >= this.size) break; // Avoid infinite loop
    }
    return -1; // Not found
  }
  
  delete(key) {
    let index = this.search(key);
    if (index !== -1) {
      this.table[index] = null;
      this.deleted[index] = true;
      this.count--;
      return true;
    }
    return false;
  }
  
  resize() {
    let oldTable = this.table;
    let oldDeleted = this.deleted;
    this.size = this.nextPrime(this.size * 2);
    this.table = new Array(this.size).fill(null);
    this.deleted = new Array(this.size).fill(false);
    this.count = 0;
    
    for (let i = 0; i < oldTable.length; i++) {
      if (oldTable[i] !== null && !oldDeleted[i]) {
        this.insert(oldTable[i]);
      }
    }
  }
  
  nextPrime(n) {
    while (!this.isPrime(n)) n++;
    return n;
  }
  
  isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i === 0) return false;
    }
    return true;
  }
}

📊Performance Analysis

Time Complexity

• Average Insert: O(1)
• Average Search: O(1)
• Average Delete: O(1)
• Worst case: O(n) for all operations

Load Factor Impact

• α = 0.5: ~1.5 probes average
• α = 0.7: ~2.2 probes average
• α = 0.9: ~5.5 probes average
• α > 0.7: Performance degrades rapidly

✅ Advantages

• Simple implementation: Easy to understand and code
• Cache-friendly: Sequential memory access pattern
• Memory efficient: No extra pointers or structures
• Good locality: Related data stored close together
• Fast when sparse: Excellent performance at low load factors

❌ Disadvantages

• Primary clustering: Consecutive occupied slots form clusters
• Load factor sensitive: Performance degrades quickly after 70%
• Deletion complexity: Requires tombstone mechanism
• Poor worst-case: Can degrade to O(n) in bad scenarios
• Table size matters: Should use prime numbers for better distribution