Hash tables are the most-used data structure in everyday programming and the least understood. Every Python dict, JavaScript object, Java HashMap, and Go map is a hash table. When a developer writes cache[key] = value and later retrieves it in nanoseconds regardless of cache size, a hash table is doing that work. Understanding the internals prevents the surprises.
What changed in 2026
- Python 3.12+ dict is more compact. CPython's dict implementation now splits the key/value storage from the index table, reducing memory by up to 40 % for large dicts with string keys.
- Rust's HashMap defaulted to AHash. The faster, DoS-resistant AHash replaced SipHash as the default hasher in Rust's
std::collections::HashMap, improving throughput ~30 % for non-adversarial inputs.
- Robin Hood hashing is mainstream. Many languages and databases now use Robin Hood open addressing (or a variant), which reduces worst-case probe lengths by redistributing "rich" entries.
- Hash flooding attacks remain real. Untrusted keys (HTTP headers, user form fields) must still use randomised hashers. Go, Java, and Python all do this by default; rolling your own hash table is risky.
How a hash table works
- Allocate an array of
n buckets (often a power of 2).
- Hash the key to an integer using a hash function.
- Map to a bucket with
index = hash(key) % n.
- Store or retrieve the value at that index.
# Conceptual — not what CPython actually does
class SimpleHashTable:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)] # chaining
def _index(self, key):
return hash(key) % self.capacity
def set(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
for k, v in self.buckets[self._index(key)]:
if k == key:
return v
raise KeyError(key)
Collision resolution
Two keys can hash to the same bucket. That is a collision, and every hash table must handle it.
| Strategy |
How it works |
Pros |
Cons |
| Chaining |
Each bucket holds a linked list |
Simple, graceful under high load |
Pointer overhead, cache-unfriendly |
| Open addressing |
Probe neighboring slots |
Cache-friendly, no allocations |
Clustering; needs low load factor |
| Robin Hood |
Open addressing, swap if probe > current occupant |
Low variance, good cache |
Slightly complex deletion |
| Cuckoo hashing |
Two hash functions; evict and re-insert |
Worst-case O(1) lookup |
Complex resize |
Python uses a variant of open addressing with pseudo-random probing. Java's HashMap uses chaining, converting chains to red-black trees when a bucket exceeds 8 entries.
Load factor and resize
Load factor = (number of entries) / (number of buckets).
When load factor exceeds a threshold (~0.7 for most implementations), the table doubles its bucket count and rehashes every key. This keeps collision probability low.
Entries: 700, Buckets: 1 000 → Load factor: 0.70 → rehash triggered
After resize: Entries: 700, Buckets: 2 000 → Load factor: 0.35
Rehash cost is O(n) — a single insert can cause a spike. For latency-sensitive code, pre-size the table:
# Pre-allocate to avoid mid-stream resize
from collections import defaultdict
# Java: new HashMap<>(initialCapacity, loadFactor)
# Go: make(map[K]V, hintSize)
d = dict.fromkeys(range(100_000)) # pre-sizes in CPython
Time complexity
| Operation |
Average |
Worst case |
| Get |
O(1) |
O(n) — all keys collide |
| Set |
O(1) amortised |
O(n) — rehash |
| Delete |
O(1) |
O(n) |
| Iteration |
O(n) |
O(n) |
Worst case only happens with adversarial keys or a broken hash function. With a randomised hasher (Python, Go, Java), collisions are random and rare.
Hash sets vs hash maps
A hash set stores only keys; a hash map stores key-value pairs. The underlying mechanism is identical — sets are maps where the value is a sentinel.
// Hash set: fast membership test
const seen = new Set<string>();
seen.add("alice");
console.log(seen.has("alice")); // true — O(1)
// Hash map: fast key-value lookup
const scores = new Map<string, number>();
scores.set("alice", 42);
console.log(scores.get("alice")); // 42 — O(1)
How to pick
- Need O(1) lookup by key? → Hash map.
- Need fast membership test? → Hash set.
- Need sorted order or range queries? → Sorted map (B-tree, red-black tree) or sorted array + binary search.
- Keys are sequential integers starting at 0? → Plain array; it is already O(1) by index.
- Input is untrusted/from the network? → Ensure the hasher is randomised (it is in all major runtimes by default).
Common mistakes
Using mutable keys. Hash tables require keys to be hashable (immutable). Using a list as a dict key in Python raises TypeError. Use a tuple.
Iterating while mutating. Adding or removing keys during iteration is undefined behaviour in most languages. Copy keys first or use a different iteration pattern.
Comparing hash tables by content incorrectly. map1 == map2 does deep-value comparison in Python and JS, but Object.is(obj1, obj2) in JS only checks reference equality. Be explicit.
Ignoring memory. A hash table with 10 M entries and 64-byte values uses ~640 MB just for values, plus ~30–50 % overhead for the index structure. Model memory, not just time.
What to skip
- Custom hash tables in application code — every standard library implementation is battle-tested and DoS-hardened. Rolling your own reintroduces hash flooding vulnerabilities.
- Hash tables for ordered traversal — if you need to iterate in sorted order frequently, use a sorted structure. See Binary search explained in 2026 for sorted-data trade-offs.
- Deeply nested hash maps as a schema substitute — add a struct or dataclass when keys become a de-facto schema; it is easier to reason about and refactor.
FAQ
Why is Python dict insertion-ordered but hash tables generally are not?
CPython 3.7+ maintains a separate insertion-order array alongside the hash index. It is an implementation guarantee, not a hash-table property. JavaScript V8 does the same for string keys.
What makes a good hash function?
Uniform distribution (every bucket equally likely), avalanche effect (one-bit key change flips ~half the hash bits), and speed. MurmurHash3, xxHash, and AHash are popular choices for non-cryptographic uses.
Can two different keys have the same hash?
Yes — that is a collision. Collision does not mean equality; the table always compares keys with == after matching hashes.
When does a hash table outperform a database index?
In-memory hash tables beat disk-based B-tree indexes for hot data that fits in RAM. Redis is essentially a hash table server. For data larger than RAM or requiring persistence, use a database.
Where to go next