Speed:

Quadratic Probing Hash Table

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

🔍How Quadratic Probing Works

Quadratic Probing is a collision resolution technique for hash tables that uses a quadratic function to find the next available slot when a collision occurs. Instead of checking consecutive slots (linear probing), it checks slots at quadratic intervals.

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

Collision occurs: Use quadratic sequence: +0, +1, +4, +9, +16, ...
Better clustering: Avoids primary clustering of linear probing
Load factor: Keep below 0.7 for optimal performance
Table size: Should be prime to ensure good distribution

💻Implementation

// Quadratic Probing Hash Table Implementation
class QuadraticProbingHashTable {
  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);
    let i = 0;
    
    while (this.table[index] !== null && this.table[index] !== key) {
      if (this.deleted[index]) break; // Can use deleted slot
      i++;
      index = (this.hash(key) + i * i) % this.size;
      
      if (i >= this.size) return false; // Table full
    }
    
    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 i = 0;
    
    while (this.table[index] !== null || this.deleted[index]) {
      if (this.table[index] === key && !this.deleted[index]) {
        return index; // Found
      }
      i++;
      index = (this.hash(key) + i * i) % this.size;
      
      if (i >= this.size) break;
    }
    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

Key Properties

• Space: O(n) for table storage
• Load factor: α = n/m should be < 0.7
• Clustering: Reduces primary clustering
• Cache performance: Better than chaining

✅ Advantages

• Better than linear probing: Reduces primary clustering
• Cache-friendly: Better memory locality than chaining
• Simple implementation: No extra data structures needed
• Memory efficient: No pointer overhead
• Good performance: When load factor is controlled

❌ Disadvantages

• Secondary clustering: Keys with same hash value cluster
• Limited load factor: Performance degrades after 70% full
• Deletion complexity: Requires tombstone mechanism
• Table size constraints: Must be prime for optimal performance
• Probing may fail: Cannot guarantee finding slot in full table