Algorithms Lesson 5: Hash Tables

Hash tables (objects/Maps in JS) give O(1) average lookup, insert, and delete. They’re the most commonly used data structure to optimize algorithms from O(n²) to O(n).

How Hash Tables Work

// JavaScript objects ARE hash tables
const phone = {};
phone["Alice"] = "555-0101";  // O(1) insert
phone["Bob"] = "555-0102";    // O(1) insert
console.log(phone["Alice"]);  // O(1) lookup

// Use Map for non-string keys or guaranteed insertion order
const map = new Map();
map.set(42, "number key");     // any type as key!
map.set([1,2,3], "array key"); // even objects!
map.has(42);    // O(1) check
map.get(42);    // O(1) lookup
map.delete(42); // O(1) delete

The “Use a Hash Map” Pattern

// Two Sum problem: O(n²) brute force vs O(n) hash map
// Find indices where arr[i] + arr[j] === target

// Brute force O(n²):
function twoSumBrute(arr, target) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i+1; j < arr.length; j++)
      if (arr[i] + arr[j] === target) return [i, j];
}

// Hash map O(n):
function twoSumFast(arr, target) {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(arr[i], i);
  }
}

Frequency Counter Pattern

// Are two strings anagrams?
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = {};
  for (const c of s) freq[c] = (freq[c] || 0) + 1;
  for (const c of t) {
    if (!freq[c]) return false;
    freq[c]--;
  }
  return true;
}