Hash Table

Definition: A data structure that maps key-value pairs using a hash function to compute index locations for O(1) average lookup, insertion, and deletion.

How It Works

A hash function transforms an arbitrary key into an integer. index = hash(key) % num_buckets then maps that integer onto a bucket in the underlying array. Because the hash function is deterministic, the same key always maps to the same bucket, letting lookup skip straight to the right location instead of scanning.

Collisions happen when two different keys hash to the same bucket, which is inevitable once enough keys are inserted (the pigeonhole principle guarantees it). Two families of strategies handle this:

Separate Chaining: each bucket holds a small linked list (or, in Java 8+ HashMap, a red-black tree once a bucket exceeds 8 entries) of all key-value pairs that hashed there. Lookup scans the short chain within the bucket.
Open Addressing: on collision, probe for the next free slot using a defined sequence (Linear Probing steps by a fixed stride, Quadratic Probing steps by increasing increments, Double Hashing uses a second hash function for the step size). No pointers or extra memory per entry, but deletions need “tombstone” markers so later probing sequences aren’t broken by a slot that looks empty but was actually just vacated.

The table resizes and rehashes all elements when the load factor (items / buckets) exceeds a threshold, typically 0.75. This rehash is O(n), but exactly like a dynamic array’s resize, it’s amortized O(1) per insert across the table’s lifetime, using the same geometric-growth argument.

A good hash function must be deterministic, fast to compute, and distribute keys uniformly across buckets to keep chains and probe sequences short. A poor hash function clusters keys into a few buckets and destroys the O(1) guarantee, degrading toward the chain/probe-sequence length instead.

Insert-and-Resize, Traced

Starting with 4 buckets and a 0.75 load factor threshold, inserting keys "a", "b", "c":

buckets=4, threshold=3 (4*0.75)
insert "a": hash("a")%4=1 -> bucket[1]=["a"]      items=1
insert "b": hash("b")%4=3 -> bucket[3]=["b"]      items=2
insert "c": hash("c")%4=1 -> collision -> bucket[1]=["a","c"]  items=3

items(3) >= threshold(3) -> RESIZE
new buckets=8, threshold=6 (8*0.75)
rehash "a": hash("a")%8=5 -> bucket[5]=["a"]
rehash "c": hash("c")%8=1 -> bucket[1]=["c"]
rehash "b": hash("b")%8=7 -> bucket[7]=["b"]

Every key is rehashed against the new bucket count, since hash(key) % new_size generally differs from hash(key) % old_size; there’s no way to reuse old bucket assignments after a resize, which is exactly why the rehash step costs O(n).

Complexity Analysis

Operation	Average Case	Worst Case
Lookup	O(1)	O(n) (all keys collide into one bucket/chain)
Insert	O(1) amortized	O(n)
Delete	O(1)	O(n)
Space	O(n)	O(n)

Worst case only shows up with a badly designed or adversarially-targeted hash function; a well-distributed hash function makes it vanishingly unlikely in practice.

Why It Matters

Underpins dictionary, map, set, and database indexing primitives across nearly every programming language; arguably the single most-used non-trivial data structure in software engineering.
The O(1) average-case lookup is what makes memoization, caching layers, and compiler symbol tables practical at scale, since repeated lookups on a large keyspace stay cheap regardless of how large the dataset grows.
Consistent hashing, a specialized hash table technique, is what lets distributed caches and databases add or remove nodes while only remapping a small fraction of keys, instead of rehashing the entire dataset on every topology change.

Common Pitfalls

Worst-case O(n) lookup time if hash collisions spike, or if malicious keys are crafted specifically to degrade hash performance (a HashDoS attack), mitigated by seeding hash functions randomly per process, as Python and most modern runtimes now do by default.
Keys must be immutable, or at least never mutated while stored in the table, to keep hash values consistent; mutating a key after insertion makes it unfindable even though it’s still physically present in its original bucket.
Iterating over a hash table and expecting a consistent or insertion order; plain hash tables historically made no ordering guarantee at all, though Python dicts since 3.7 and Java’s LinkedHashMap are notable exceptions that do guarantee order.
Using a poor or default hash function, e.g. hashing only the first few characters of a string, causes clustering that silently degrades performance without ever throwing an error.
Assuming key in hash_table and hash_table[key] cost the same in every language; some naive or custom implementations recompute the hash and re-scan the chain separately for each, doubling the real cost.

Comparison

	Hash Table	Binary Search Tree	Trie	Sorted Array
Lookup	O(1) average	O(log n) average	O(k), k = key length	O(log n)
Maintains sorted order	No	Yes	Prefix order only	Yes
Range queries	Not supported	O(log n + results)	Prefix queries only	O(log n + results)
Worst-case lookup	O(n)	O(n) unbalanced, O(log n) balanced	O(k)	O(log n)

Example

Python dict, JavaScript Object/Map, and Java HashMap all use hash tables as their core implementation.

hash("apple") % 8 buckets = 3   -> bucket[3] = [("apple", 1.20)]
hash("banana") % 8 buckets = 3  -> collision! bucket[3] = [("apple",1.20), ("banana",0.50)]
lookup("banana") -> hash to bucket 3 -> scan short chain -> found in O(1) average

With 8 buckets and a load factor threshold of 0.75, inserting the 7th key (7/8 = 0.875 > 0.75) triggers a resize to 16 buckets and rehashes all existing keys into their new positions, a single O(n) pause amortized across all the O(1) inserts that led up to it.

Chaining vs. Open Addressing, In Practice

Chaining (bucket 3 holds a small list):
bucket[3] -> ("apple", 1.20) -> ("banana", 0.50) -> null

Open Addressing, linear probing (banana collides with apple's slot):
slot[3] = ("apple", 1.20)
slot[4] = ("banana", 0.50)   # probed forward by 1 after collision

Chaining degrades gracefully: even at a load factor above 1 (more items than buckets), it just means longer average chains, still functionally correct. Open addressing degrades sharply as the load factor approaches 1, since probe sequences get dramatically longer, which is why open-addressing implementations typically resize at a lower threshold (often 0.5-0.7) than chaining implementations.

Variants

Cuckoo Hashing: uses two (or more) hash functions and two tables; a key always lives in one of two possible slots, giving worst-case O(1) lookup at the cost of occasionally evicting and re-placing existing keys on insert, which can cascade into a full rehash if a cycle of evictions forms.
Robin Hood Hashing: an open-addressing variant that, on collision, “steals” a slot from a key that’s closer to its own ideal bucket than the new key is to its own, evening out the variance in probe-sequence length across the whole table and keeping worst-case lookups closer to the average case.
Perfect Hashing: for a known, static set of keys, constructs a collision-free hash function ahead of time, giving guaranteed O(1) worst-case lookup; impractical for a table that needs to support arbitrary future inserts.

Real-World Systems

Python’s dict is a hash table using open addressing (not chaining), with a pseudo-random probing sequence, and has guaranteed insertion-order iteration since Python 3.7 as an explicit language guarantee, not just an implementation detail.
Java’s HashMap uses separate chaining, with each bucket promoted from a linked list to a red-black tree once it holds more than 8 entries, specifically to bound worst-case lookup at O(log n) instead of O(n) under adversarial collisions.
Redis’s core key-value store is fundamentally a hash table, and Redis’s own HASH data type (nested field-value maps within a single key) is a hash table built on top of a hash table.
Git’s object store is content-addressed: every blob, tree, and commit is stored and looked up by the SHA-1/SHA-256 hash of its content, functioning as a giant hash table where the “key” is derived directly from the data itself.

FAQ

Why do languages seed hash functions randomly at process startup? To prevent HashDoS: an attacker who knows the exact hash function and seed can craft input keys that all collide into the same bucket, degrading every lookup from O(1) to O(n) and creating a denial-of-service vector. A random per-process seed makes that attack infeasible to precompute.

What’s the difference between a Hash Table, a Hash Map, and a Hash Set? They’re the same underlying structure. A “map” associates keys with values; a “set” stores keys only, using the hash table purely for O(1) membership testing.

Common Interview Questions

Why is the average case O(1) but the worst case O(n)? — average case assumes a well-distributed hash function spreading keys evenly across buckets; worst case is every key colliding into a single bucket, degrading to a linear scan of one long chain.
How would you design a hash function for a custom object? — combine the hashes of the object’s immutable fields (commonly via a running multiply-and-XOR or a proper hash-combining function), ensuring equal objects always produce equal hashes, since violating that breaks lookup correctness.
What happens if you use a mutable object as a dictionary key and then mutate it? — its hash value changes, so the table can no longer find it in the bucket it was originally placed in; this is exactly why most languages either disallow mutable keys or require hashing based on immutable state only.

Referenced by

Dig deeper

Spot an error in this note?