| Situation | What happens | Planning use |
|---|---|---|
| Typical lookup or insert | Expected O(1) time; worst case O(n) when all elements land in one bucket | Budget for constant time on average, but do not rely on it if the hash function clusters keys. |
| Separate chaining cost | Equality tests proportional to N/M (N keys, M lists) | Add lists as keys grow so each chain stays short. |
| Open addressing as the table fills | Performance becomes very bad as the load factor approaches 1; resize when it exceeds about 2/3 | Resize well before the table is full. |
| Modular hashing with a power-of-two table size | The index uses only the lowest-order bits of the key | Prefer a prime size that is not close to a power of two. |
These figures come from Princeton’s Algorithms hashing chapter and Cornell’s data structures lecture notes on hashing.
How do hash tables work? A hash function turns each key into an array index, so a lookup jumps straight to one slot instead of scanning; the speed holds only while collisions stay rare and the table is not too full.
This guide is one of the programming essays on this site. It starts with what the design costs and buys you, then explains the mechanism and builds two working versions in Python.
The speed you can plan on
A hash table makes search, insert and delete cheap on average, and the cost does not climb with the number of stored items as long as keys spread out. Cornell’s notes describe hashing as expected-case O(1) time, but O(n) in the worst case. A tutorial summary from GeeksforGeeks gives the same average figure for all three operations: search, insert and delete.
The speed comes from arrays. A hash function maps any key to an integer in the range 0 to M-1 for an array of M slots, as the Princeton algorithms text puts it. Reading a slot by index is direct, so Cornell notes that set and map operations can run in O(1) time when hash tables are implemented on arrays. There is no scan through the other entries, which is why a lookup finds its value so quickly.
The worst case is a practical warning, not a curiosity. It occurs when all elements hash to the same bucket, and then the table behaves like one long list. The average-case analysis assumes the hash function distributes keys uniformly among the integers from 0 to M-1. If your keys cluster or your function ignores most of the key, expect the slow case rather than the fast one.
What a collision costs
Two different keys can hash to the same array index, so every hash table needs a collision resolution strategy. Princeton’s text states plainly that we must face the possibility that two or more different keys may hash to the same index. Sharing a slot does not make keys equal: two keys can share a home bucket without being equal.
That has a direct coding consequence. After the hash function picks a slot, the table must still compare the stored key with the key you asked for. An implementation that trusts the index alone returns wrong values as soon as a collision occurs. How much the comparison costs depends on the strategy you choose next.
Choosing between chaining and open addressing

Separate chaining keeps a list of the key-value pairs whose keys hash to each index, one list per array slot. Open addressing stores every pair in the table itself, so the table must be larger than the number of pairs (M > N in Princeton’s notation). Its simplest form is linear probing: on a collision, check the next table entry.

- Pick chaining when you cannot predict the data size. Cornell notes that the bucket approach suffers gradually declining performance as the load factor grows, so there is no hard resize point. Princeton shows search and insert costs proportional to N/M, which tells you directly how many buckets to add to keep chains short.
- Pick open addressing when you can resize early. Its performance becomes very bad as the load factor approaches full capacity, so it suits cases where you control growth and keep the table comfortably under full. A LibreTexts data structures course notes it has better cache behaviour because everything lives in the same table, while chaining’s linked lists have poorer cache performance.
- Measure before trusting either claim. Cornell’s notes say open addressing is slower in practice than an array of buckets, which pulls against the cache argument. Benchmark with your own keys before choosing on theory alone.

Load factor and resizing
A hash table resizes when it holds too many elements for its buckets, because lookups slow down as each bucket fills. Cornell defines the load factor as a = n/m, the number of elements per bucket, for n elements and m buckets. Resizing keeps that ratio bounded, which is how the notes keep each bucket list small, O(1) in size.

The threshold depends on the strategy. For open addressing, Cornell advises resizing the array when the load factor exceeds 2/3 or so. That is guidance from one set of course notes, not a universal constant, and chaining has no equivalent hard limit because its decline is gradual. Choose a chaining threshold by measuring how long your chains get.
Resizing means rebuilding. The index is the remainder after dividing by the table size, so a new size gives every key a new position. The simplest approach is to allocate a larger array and insert every existing pair again, which the Python code below does.
From key to index
A hash function must give the same output for the same key, run quickly and spread keys evenly, according to Princeton’s requirements for good hash functions. The standard way to reduce an integer key k to a valid slot is modular hashing: choose the array size M to be prime and compute k mod M.
The size matters. If m is a power of two, Cornell points out that h(k) is just the p lowest-order bits of k, so every key sharing those bits collides regardless of its other bits. Cornell adds that in practice primes not too close to powers of 2 work well. Any custom hash function you pass into a table should be judged by the same test: does every part of the key influence the index?
Building it in Python
Both tables below use Python’s built-in hash and the remainder operator to pick a slot. They take a capacity and a maximum load factor as arguments, so the resize threshold is yours to set. A hash function that carries its own settings, such as a seed, is a natural fit for the pattern that answers what is a closure in programming.
Separate chaining
Each bucket here is a Python list of key-value pairs. Real chains are often linked nodes, as in this linked list explained guide, but a list keeps the sketch short and the logic identical.
class ChainedTable:
def __init__(self, capacity, max_load):
self.buckets = [[] for _ in range(capacity)]
self.count = 0
self.max_load = max_load
def _index(self, key):
return hash(key) % len(self.buckets)
def put(self, key, value):
if self.count / len(self.buckets) > self.max_load:
self._grow()
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))
self.count += 1
def get(self, key):
for k, v in self.buckets[self._index(key)]:
if k == key:
return v
raise KeyError(key)
def _grow(self):
old = self.buckets
self.buckets = [[] for _ in range(len(old) + len(old))]
self.count = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
The equality test inside put and get is the check for keys that share a bucket without being equal. A production version would round the new capacity up to a prime that is not near a power of two, following the sizing advice above.
Open addressing with linear probing
This version keeps pairs directly in one array and walks forward on a collision. The max_load value must stay below 1 so an empty slot always exists, which matches the requirement that the table be larger than the number of pairs. A value near 2/3 follows Cornell’s guidance. Deletion is left out to keep the sketch short.
class ProbingTable:
def __init__(self, capacity, max_load):
self.slots = [None] * capacity
self.count = 0
self.max_load = max_load
def _find(self, key):
i = hash(key) % len(self.slots)
while self.slots[i] is not None and self.slots[i][0] != key:
i = (i + 1) % len(self.slots)
return i
def put(self, key, value):
if (self.count + 1) / len(self.slots) > self.max_load:
self._grow()
i = self._find(key)
if self.slots[i] is None:
self.count += 1
self.slots[i] = (key, value)
def get(self, key):
slot = self.slots[self._find(key)]
if slot is None:
raise KeyError(key)
return slot[1]
def _grow(self):
old = self.slots
self.slots = [None] * (len(old) + len(old))
self.count = 0
for slot in old:
if slot is not None:
self.put(*slot)
Compare the two classes and the trade-off becomes visible. Chaining never runs out of room in a bucket and only slows gradually, while probing needs the resize check to run early because its search loop lengthens sharply as empty slots disappear.
Frequently asked questions
Are collisions rare enough to ignore?
No. A LibreTexts course uses the birthday paradox to make the point: with only 23 people, the chance that two share a birthday is 50%. Collisions appear sooner than intuition suggests, even in a large table.
Must equal keys always produce equal hashes?
Yes. Princeton’s text states the Java rule that if two objects are equal, their hashCode values must be the same. Otherwise equal keys would land in different slots and a lookup would miss a value that is present.
How are string keys turned into numbers?
Princeton’s approach treats the characters as digits of a large integer using a small prime R, and Java uses 31. Java code then masks off the sign bit with 0x7fffffff before taking the remainder by the table size M, so the index is never negative.
Is the load factor the same as how full the table is?
For open addressing, yes, since each slot holds at most one pair. In a chained table the load factor is the average number of elements per bucket, defined as n/m, so it can exceed 1 without any slot overflowing.



