Hash Tables
How a hash function turns keys into array slots, what collisions and load factor mean, and how to build a table with chaining.
beginner45 min#hash-table#hashing#collisions#load-factor#dictionary
Prerequisites: Arrays and Dynamic Arrays, Linked Lists
Why it matters
The hash table is the most useful structure in everyday programming: Python's dict and set, JavaScript's Map, Set and objects, database indexes, caches and symbol tables are all built on it. In interviews it is the standard tool for turning an O(n^2) "compare every pair" idea into O(n) by remembering what you have already seen.
Intuition
Imagine a wall of numbered mailboxes. You do not search for a person's mailbox; you apply a rule to their name that always yields a box number, then walk straight to it. That rule is the hash function. Because the rule is deterministic, the same key always lands in the same box, so lookup does not depend on how many people are registered.
The catch: there are far more possible names than boxes, so two names will sometimes map to the same box. That is a collision, and every hash table needs a plan for it.
How it works
- Hash function: converts a key to an integer. A good one is fast, deterministic, and spreads keys evenly. Equal keys must produce equal hashes.
- Index:
hash(key) % number_of_bucketspicks a slot in an underlying array. - Collision handling:
- Chaining: each slot holds a small list of key-value pairs. A lookup hashes, then scans that one short list.
- Open addressing: every pair lives directly in the array. On a collision you probe other slots (next slot, or by a formula) until you find a free one. Deleting needs tombstone markers so probe sequences do not break.
- Load factor:
items / buckets. As it grows, collisions multiply and chains get longer. When it crosses a threshold (commonly 0.75 for chaining, lower for open addressing), the table allocates about twice as many buckets and rehashes every item, because each index depends on the bucket count. Like a dynamic array, this makes insertion amortized O(1).
The path from a key to its slot is always the same three stages. Here it is for the key banana with the table from the code below, which starts with 4 buckets.
buckets (4) hash("fig") % 4 = 1 and hash("date") % 4 = 1 -> collision
0: []
1: [fig:3] -> [date:4] chaining: both live in bucket 1's list
2: []
3: [apple:5]
Now watch the lesson's table (4 buckets, chaining) receive its first four words, using the same hash as the code. The grid shows one row per bucket, with the chain reading left to right.
Collisions are handled by chaining, and growing the table (rehashing) spreads the chains out again.
The same thing happens later in the lesson's run. Before grape arrives, 8 buckets hold 6 words and date and fig share bucket 3.
Load factor is items divided by buckets. Crossing the threshold triggers a one-time O(n) rehash that keeps chains short.
Keys must be hashable and stable. If a key's contents change after insertion, its hash changes and the table can no longer find it. That is why Python lists cannot be dict keys while tuples can, and why JavaScript objects used as Map keys are compared by reference, not by contents.
Worst case. If all keys collide, one chain holds everything and lookup degrades to O(n). Real libraries defend against that with good hash functions, resizing, randomized seeds (Python randomizes string hashes per process), and in some cases converting long chains into balanced trees. Note that hash iteration order is not sorted; if you need sorted keys, use a tree or sort afterwards.
| Operation | Time | Notes |
|---|---|---|
| Insert / update | O(1) average | Amortized, includes occasional rehash |
| Lookup / membership | O(1) average | Hash, then scan a short chain |
| Delete | O(1) average | Tombstone needed in open addressing |
| Any operation, worst case | O(n) | All keys collide |
| Iterate all items | O(n + buckets) | Order is not sorted |
| Space | O(n) | Extra empty buckets for a low load factor |
Code: a hash table with chaining
Python randomizes its built-in string hash on every run, so this example uses a small deterministic hash (a djb2-style multiply-and-add) to make the output reproducible.
def hash_str(s):
h = 5381
for ch in s:
h = (h * 33 + ord(ch)) % 2**32 # deterministic djb2-style hash
return h
class HashTable:
def __init__(self):
self._buckets = [[] for _ in range(4)]
self._size = 0
def __len__(self):
return self._size
def _bucket(self, key):
return self._buckets[hash_str(key) % len(self._buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for pair in bucket:
if pair[0] == key:
pair[1] = value # update existing key
return
bucket.append([key, value])
self._size += 1
if self._size / len(self._buckets) > 0.75: # load factor limit
self._grow()
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
def delete(self, key):
bucket = self._bucket(key)
for i, pair in enumerate(bucket):
if pair[0] == key:
bucket.pop(i)
self._size -= 1
return True
return False
def _grow(self):
old = self._buckets
self._buckets = [[] for _ in range(len(old) * 2)]
for bucket in old:
for k, v in bucket: # rehash: positions depend on table size
self._buckets[hash_str(k) % len(self._buckets)].append([k, v])
def stats(self):
longest = max(len(b) for b in self._buckets)
return len(self._buckets), longest
t = HashTable()
for word in ["apple", "banana", "cherry", "date", "elder", "fig", "grape"]:
t.put(word, len(word))
t.put("fig", 30)
print(len(t), t.get("fig"), t.get("kiwi", "missing"))
print(t.delete("date"), t.delete("date"), len(t))
print(t.stats())
counts = {}
for w in "to be or not to be".split():
counts[w] = counts.get(w, 0) + 1
print(counts)function hashStr(s) {
let h = 5381;
for (const ch of s) {
h = (h * 33 + ch.charCodeAt(0)) % 2 ** 32; // deterministic djb2-style hash
}
return h;
}
class HashTable {
constructor() {
this.buckets = Array.from({ length: 4 }, () => []);
this.size = 0;
}
#bucket(key) {
return this.buckets[hashStr(key) % this.buckets.length];
}
put(key, value) {
const bucket = this.#bucket(key);
for (const pair of bucket) {
if (pair[0] === key) {
pair[1] = value; // update existing key
return;
}
}
bucket.push([key, value]);
this.size++;
if (this.size / this.buckets.length > 0.75) this.#grow(); // load factor limit
}
get(key, fallback = null) {
for (const [k, v] of this.#bucket(key)) {
if (k === key) return v;
}
return fallback;
}
delete(key) {
const bucket = this.#bucket(key);
const i = bucket.findIndex((pair) => pair[0] === key);
if (i === -1) return false;
bucket.splice(i, 1);
this.size--;
return true;
}
#grow() {
const old = this.buckets;
this.buckets = Array.from({ length: old.length * 2 }, () => []);
for (const bucket of old) {
for (const [k, v] of bucket) {
// rehash: positions depend on table size
this.buckets[hashStr(k) % this.buckets.length].push([k, v]);
}
}
}
stats() {
const longest = Math.max(...this.buckets.map((b) => b.length));
return `(${this.buckets.length}, ${longest})`;
}
}
const py = (b) => (b ? "True" : "False");
const t = new HashTable();
for (const word of ["apple", "banana", "cherry", "date", "elder", "fig", "grape"]) {
t.put(word, word.length);
}
t.put("fig", 30);
console.log(t.size, t.get("fig"), t.get("kiwi", "missing"));
console.log(py(t.delete("date")), py(t.delete("date")), t.size);
console.log(t.stats());
const counts = new Map();
for (const w of "to be or not to be".split(" ")) counts.set(w, (counts.get(w) ?? 0) + 1);
console.log("{" + [...counts].map(([k, v]) => `'${k}': ${v}`).join(", ") + "}");Both versions print:
7 30 missing
True False 6
(16, 1)
{'to': 2, 'be': 2, 'or': 1, 'not': 1}
Reading the output: 7 distinct words were stored and fig was updated to 30 rather than duplicated. After a delete the size is 6. The table started with 4 buckets and doubled twice (4 to 8 to 16) as the load factor crossed 0.75, and the longest chain at the end has length 1. The final line is the classic word-count idiom using the built-in dictionary.
Common pitfalls
- Assuming O(1) is guaranteed: it is an average. Adversarial or badly distributed keys can make it O(n).
- Mutating a key after insertion: the item is stranded in the wrong bucket and can never be found.
- Relying on order: Python dicts keep insertion order and JavaScript Maps do too, but that is a feature of those libraries, not of hashing in general.
- Forgetting that equal keys need equal hashes: if you define your own equality, define a matching hash.
- Floats and objects as keys:
0.1 + 0.2is not equal to0.3, and object keys in JavaScript plain objects are turned into strings, so1and"1"collide. PreferMapwhen key types matter. - Hashing inside a loop of n^2: building a set once outside the loop is usually the whole optimization.
Practice
Two Sum (unsorted) easy
Hint
For each number, what other number would complete the target? Have you seen it already?
Show solution
Keep a map from value to index. For each x at index i, check whether target - x is in the map; if so return that index and i. Otherwise store x. One pass, O(n) time, O(n) space.
Group anagrams medium
Hint
You need a key that is identical for all anagrams of a word.
Show solution
Use the sorted letters of each word (or a tuple of 26 letter counts) as the key and append the word to that key's list. Sorting costs O(k log k) per word of length k; counting costs O(k). Overall O(n * k) with the counting key.
Longest consecutive sequence medium
Hint
Put everything in a set. Which numbers are the start of a run?
Show solution
Add all numbers to a set. For each number x with x - 1 not in the set, count upward while x + 1, x + 2, ... are present. Each run is walked only from its start, so total work is O(n) even though there is a nested loop.
Open addressing with deletion hard
Hint
If you simply empty a slot on delete, what happens to a key that was placed after it in a probe sequence?
Show solution
With linear probing, a lookup stops at the first empty slot. Emptying a deleted slot would cut the probe path and hide later keys. Mark the slot as a tombstone instead: lookups continue past it, inserts may reuse it. Count tombstones toward the load factor and rebuild the table when they pile up.
Interview questions
- How does a hash table achieve O(1) lookup? It converts the key into an array index, so it does not search; collisions are kept short by a good hash and by resizing at a load factor limit.
- What is a collision and how can you handle it? Two keys map to the same bucket. Chaining stores a list per bucket; open addressing probes for another free slot.
- Why does the table resize, and what does it cost? To keep chains short. Rehashing all items is O(n), but it is rare, so insertion is amortized O(1).
- Hash table vs balanced tree? Hash tables are faster on average for exact lookup; trees keep keys sorted and give O(log n) worst case, plus range queries.
Interviewers look for: reaching for a map or set to trade space for time, stating average versus worst case, and knowing why keys must be immutable.
Quick check
A chaining hash table has 8 buckets and 6 items. Its load factor is 0.75 and the resize threshold is 0.75 (resize when above it). You insert one more item. What happens?
Finished this lesson?
Further resources
- Hash table (Wikipedia) (article)
- MDN: Map (docs)
- Python docs: collections (docs)