Hash Tables - O(1) Lookup by Magic Hashing

A Hash Table (also called a hash map) is the data structure that turns any key into an array index in $O(1)$ time. It’s the engine behind JavaScript’s Map, Python’s dict, Java’s HashMap, and the key-value stores that power caches, databases, and compilers. When you look up a value by key in constant time, a hash table is almost certainly responsible.

A Brief History

The concept was invented independently by Hans Peter Luhn at IBM in 1953 and Arnold Dumey in 1956. Luhn’s internal IBM memo proposed using a hash function to rapidly retrieve records — the same core idea used today. Gene Amdahl and colleagues refined the technique while building early IBM computers. Donald Knuth provided the rigorous mathematical analysis in The Art of Computer Programming (1968), establishing the theoretical foundation. The term “hash” likely comes from the idea of chopping and mixing data — a hash function scrambles a key into a seemingly random index. Today, hash tables are so pervasive that most programmers use them daily without thinking about the mechanics underneath.

How It Works

A hash table is an array paired with a hash function:

Hash: Apply a hash function to the key — index = hash(key) % array.length. This maps the key to a bucket index.
Store: Place the key-value pair at array[index].
Retrieve: To look up a key, hash it again to get the same index, then return array[index].value.

The magic: a good hash function distributes keys uniformly across buckets, making the chance of two keys landing in the same slot (a collision) low.

Handling Collisions

Two keys can produce the same hash (collision). The two main strategies:

Chaining: Each bucket holds a linked list of all key-value pairs that hash to that index. Lookup traverses the list. With a good hash and load factor below 0.7, lists stay short — average $O(1)$ , worst case $O(n)$ (all keys in one bucket).

Open Addressing (Linear Probing): When a collision occurs, probe the next slot (or probe with a formula) until an empty slot is found. No linked lists — everything stays in the array. Better cache performance but degrades faster at high load.

Rehashing: When the load factor (elements ÷ buckets) exceeds a threshold (typically 0.7–0.75), the table resizes — usually doubling — and all keys are re-hashed into the new array. This makes insertion amortized $O(1)$ .

Time Complexity

Operation	Average	Worst
Insert	$O(1)$	$O(n)$
Lookup	$O(1)$	$O(n)$
Delete	$O(1)$	$O(n)$

The worst case ( $O(n)$ ) occurs when every key hashes to the same bucket (a degenerate hash function, or a hash-flooding attack). In practice, with a good hash function and reasonable load factor, $O(1)$ is the rule.

Space Complexity

$O(n)$ — one slot per stored element, plus some overhead for empty buckets. A hash table with load factor 0.7 uses roughly $1.43 \times n$ slots.

Advantages and Disadvantages

Advantages:

$O(1)$ average-case insert, lookup, and delete — unmatched for key-value access
Flexible keys — any hashable value (strings, numbers, objects) can be a key
Naturally implements sets (store keys only, no values)
Foundation for counting, grouping, caching, and deduplication

Disadvantages:

No ordering — hash tables don’t maintain insertion order (though JavaScript’s Map does, as an implementation detail)
Worst-case $O(n)$ — pathological inputs can degrade all operations
Higher memory usage than arrays — empty buckets, pointers for chaining
Hash function quality matters — a poor hash function destroys performance
Not cache-friendly for large tables — buckets can be scattered in memory

When to Use a Hash Table

Hash tables are the go-to for:

Frequency counting — count occurrences of each element in $O(n)$ : { 'a': 3, 'b': 1, ... }
Deduplication — store seen items in a set; $O(1)$ membership check
Caching / memoization — store fn(input) → result; skip recomputation on repeated inputs
Two-sum and complement problems — “find two numbers that sum to target” solved in $O(n)$ with a hash set
Grouping / bucketing — group items by a property (group anagrams, group words by length)
Graph adjacency lists — represent a graph as { node: [neighbors] } for $O(1)$ neighbor lookup
LRU Cache — combined with a doubly linked list for $O(1)$ eviction

In JavaScript, Map and Set are the built-in hash table implementations. Plain objects ({}) also act as hash maps for string keys, but Map is preferred: it handles non-string keys, preserves insertion order, exposes .size, and avoids prototype pollution.

In conclusion, the hash table is arguably the single most impactful data structure in practical programming. $O(1)$ lookup by arbitrary key is transformative — it converts many $O(n^2)$ problems into $O(n)$ ones. Understanding how hashing, collision handling, and rehashing work gives you insight into performance that is invisible when you just call map.get(key).