Hash tables back Python's dict and set, database hash joins, caches, and symbol tables. This page explains the lookup path, the two main ways to handle collisions, why load factor and resizing keep operations O(1) on average, and the failure modes that push them to O(n).
A hash table maps keys to values via a hash function that converts each key to an array index. Average O(1) for insert, lookup, and delete; worst case O(n) when too many keys collide. Python's dict and set are hash tables.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
Allocate an array of m buckets. To insert (key, value): compute i = hash(key) % m, place the entry in bucket i. Resolve collisions by chaining (each bucket holds a linked list) or open addressing (probe to the next free slot). When the load factor exceeds a threshold (~0.75), grow the array and rehash everything.
# Python dict — already a hash table.
d = {}
d["alice"] = 30
d["bob"] = 25
print(d["alice"]) # 30 — O(1) average
print("alice" in d) # True — O(1) average
del d["bob"]
# Hand-rolled hash table with separate chaining.
class HashTable:
def __init__(self, capacity=16):
self._buckets = [[] for _ in range(capacity)]
self._size = 0
def _bucket(self, key):
return self._buckets[hash(key) % len(self._buckets)]
def put(self, key, val): # O(1) average
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
self._size += 1
if self._size > 0.75 * len(self._buckets):
self._resize(len(self._buckets) * 2)
def get(self, key): # O(1) average
for k, v in self._bucket(key):
if k == key:
return v
raise KeyError(key)
def _resize(self, new_cap):
old = self._buckets
self._buckets = [[] for _ in range(new_cap)]
self._size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
h = HashTable()
h.put("alice", 30); h.put("bob", 25)
print(h.get("alice")) # 30A lookup hashes the key to an integer, reduces it to a slot index (with modulo, or a bit mask when the table size is a power of two), and then inspects that slot. Because different keys can map to the same slot, the table stores enough information to confirm a match: usually the full hash and the key itself. Implementations compare the cached hash first since it is a cheap integer check, then call the key's equality method only when the hashes match.
For this to work, keys must be hashable: their hash must not change while they are in the table, and equal keys must have equal hashes. That is why Python lists cannot be dict keys while tuples of immutable values can.
Separate chaining stores a linked list (or small array, or in Java 8+ a tree once a bucket gets large) at each slot. It degrades gracefully as the table fills and deletion is simple. Open addressing stores entries directly in the slot array and, on collision, probes other slots in a deterministic sequence: linear probing (next slot), quadratic probing, or double hashing. It is more cache-friendly because there are no pointers to follow, but it needs tombstones for deletion and its performance collapses as the table approaches full. CPython uses open addressing with a perturbed probe sequence and keeps a separate compact array of entries so iteration follows insertion order.
The load factor is the number of stored entries divided by the number of slots. Expected probe length grows as the load factor rises, so tables resize, typically doubling, once a threshold is crossed (around 0.75 for Java's HashMap, about 2/3 for CPython's dict). Resizing rehashes every entry, an O(n) operation, but because it happens after a geometric number of inserts the amortized cost per insert stays O(1).
class HashMap:
"""Separate-chaining hash map with doubling resize."""
def __init__(self, cap=8):
self.buckets = [[] for _ in range(cap)]
self.size = 0
def _slot(self, key):
return hash(key) % len(self.buckets)
def put(self, key, value):
b = self.buckets[self._slot(key)]
for i, (k, _) in enumerate(b):
if k == key:
b[i] = (key, value)
return
b.append((key, value))
self.size += 1
if self.size / len(self.buckets) > 0.75:
self._resize()
def get(self, key):
for k, v in self.buckets[self._slot(key)]:
if k == key:
return v
raise KeyError(key)
def _resize(self):
old = [kv for b in self.buckets for kv in b]
self.buckets = [[] for _ in range(2 * len(self.buckets))]
self.size = 0
for k, v in old:
self.put(k, v)
m = HashMap()
for i in range(20):
m.put(f"k{i}", i)
print(m.get("k7"), len(m.buckets)) # 7 32| Need | Hash table | Alternative |
|---|---|---|
| Exact-match lookup by key | O(1) average | - |
| Ordered iteration or range queries | Not supported | Balanced BST, B-tree, sorted array |
| Min/max or k-th smallest | O(n) | Heap or BST |
| Membership with tiny memory, false positives OK | Large | Bloom filter |
| Guaranteed worst-case latency | O(n) worst case | Balanced tree, O(log n) |
__eq__ and __hash__. If two equal objects hash differently, lookups silently fail.str hashing per process (PYTHONHASHSEED) for this reason.