Speed:

Hash Table

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

🗂️How Hash Tables Work

A Hash Table is a data structure that implements an associative array, mapping keys to values using a hash function. It provides fast insertion, deletion, and lookup operations by computing an index into an array of buckets.

The key components are:

Hash Function: Maps keys to array indices (e.g., key % table_size)
Collision Resolution: Handles when multiple keys hash to the same index
Chaining: Uses linked lists to store multiple elements at same index
Load Factor: Ratio of elements to table size, affects performance

💻Implementation

// Hash Table with Chaining Implementation
class HashTable {
  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;
  }
}

📊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.75
• Hash function: Determines distribution quality
• Dynamic resizing: Maintains performance

🔗 Collision Resolution

• Chaining: Linked lists at each index
• Linear Probing: Check next available slot
• Quadratic Probing: Check slots at quadratic intervals
• Double Hashing: Use second hash function

🎯 Hash Functions

• Division: h(k) = k mod m
• Multiplication: h(k) = ⌊m(kA mod 1)⌋
• Universal hashing: Randomized functions
• Cryptographic: MD5, SHA for security