Hash Table

Explanation

A hash function takes a key (any value: string, number, object) and returns an integer (the hash code). That integer, modulo the array size, gives an index where the value is stored. When you look up a key, you run the same hash function to compute the same index and retrieve the value in O(1) time — no searching required. This is the magic that makes JavaScript objects and Python dicts so fast. Collisions happen when two different keys hash to the same index. The two main collision resolution strategies are: chaining (each bucket holds a linked list of entries that share that hash) and open addressing (when a collision occurs, probe to the next available slot). JavaScript's Map and Python's dict both use variations of open addressing. Most real hash table implementations resize (rehash) when the load factor (entries/capacity) exceeds ~0.75, copying everything to a larger array. The worst case for hash tables is O(n) — when all keys collide into the same bucket (this is an actual attack vector called a hash collision DoS attack). Well-designed hash functions minimize this. For keys with known structure, a perfect hash function (no collisions at all) can be constructed. In JavaScript, plain objects ({}) are hash tables with string/symbol keys. The Map object is a proper hash table that allows any type as key, preserves insertion order, and has O(1) size. Sets are hash tables that only store keys (no values), providing O(1) membership testing — the single most common use case for a hash table.

Code Example

// JavaScript Map (proper hash table) vs plain object

// Map: any key type, preserves order, has .size
const cache = new Map();
cache.set('user:42', { name: 'Alice', age: 30 });
cache.set('user:43', { name: 'Bob', age: 25 });

console.log(cache.get('user:42')); // { name: 'Alice', age: 30 }
console.log(cache.has('user:99')); // false
console.log(cache.size);           // 2

// O(1) frequency count — classic hash table use case
function charFrequency(str) {
  const freq = new Map();
  for (const ch of str) {
    freq.set(ch, (freq.get(ch) ?? 0) + 1);
  }
  return freq;
}

// O(1) set membership test
const visited = new Set();
visited.add('page-1');
if (!visited.has('page-2')) {
  // first visit to page-2
  visited.add('page-2');
}

Why It Matters for Engineers

Hash tables are behind almost every O(1) operation you've ever taken for granted: looking up a variable in a scope, checking if a key exists in an object, caching results, de-duplicating a list. When you see an O(n²) algorithm, the fix is often "use a hash table" — trade memory for time by storing previously computed values. Understanding hash tables also means understanding their failure modes: key collisions, worst-case performance degradation, non-deterministic iteration order (in objects), and why floating-point numbers are bad hash keys. These are the kinds of bugs that are nearly impossible to diagnose if you don't know what's happening underneath.