Speed:

Chaining Hash Table

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

🔗How Chaining Works

Chaining is a collision resolution technique for hash tables that handles collisions by storing multiple elements at the same index using linked lists. Each table slot contains a pointer to a linked list of all elements that hash to that particular index.

The key advantages of chaining:

Simple implementation: Easy to understand and implement
No clustering: Collisions don't affect neighboring slots
Dynamic size: Chains can grow as needed
Load factor flexibility: Can exceed 1.0 without major issues
Easy deletion: No tombstone mechanism needed

💻Implementation

// Hash Table with Chaining Implementation
class ChainingHashTable {
  constructor(size = 11) {
    this.size = size;
    this.table = new Array(size).fill(null).map(() => []);
    this.count = 0;
  }
  
  hash(key) {
    return key % this.size;
  }
  
  insert(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    
    // Check if key already exists
    if (!bucket.includes(key)) {
      bucket.push(key);
      this.count++;
      
      // Resize if load factor > 0.75
      if (this.count > this.size * 0.75) {
        this.resize();
      }
    }
  }
  
  search(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    return bucket.includes(key) ? index : -1;
  }
  
  delete(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    const keyIndex = bucket.indexOf(key);
    
    if (keyIndex !== -1) {
      bucket.splice(keyIndex, 1);
      this.count--;
      return true;
    }
    return false;
  }
  
  resize() {
    const oldTable = this.table;
    this.size = this.nextPrime(this.size * 2);
    this.table = new Array(this.size).fill(null).map(() => []);
    this.count = 0;
    
    for (let bucket of oldTable) {
      for (let key of bucket) {
        this.insert(key);
      }
    }
  }
  
  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;
  }
  
  display() {
    for (let i = 0; i < this.size; i++) {
      console.log(`[${i}]: ${this.table[i].join(' -> ')}`);
    }
  }
}

📊Performance Analysis

Time Complexity

• Average Insert: O(1)
• Average Search: O(1 + α)
• Average Delete: O(1 + α)
• Worst case: O(n) when all keys hash to same slot

Load Factor Impact

• α = n/m: average chain length
• α = 0.75: good performance
• α = 1.0: still acceptable
• α > 2.0: consider resizing

✅ Advantages

• Simple to implement: Straightforward collision handling
• No clustering: Each slot is independent
• Flexible load factor: Can exceed 1.0
• Easy deletion: No special handling needed
• Memory efficient: Only allocates what's needed

❌ Disadvantages

• Memory overhead: Extra space for pointers
• Cache performance: Poor memory locality
• Dynamic allocation: Runtime memory management
• Poor worst case: All elements in one chain
• Pointer dereferencing: Extra indirection overhead