AdvancedData Structures & Algorithms · Lesson 22 of 25 · Updated ·
How Hashing Works — Hash Functions, Collisions and Load Factor
Hash maps (dict in Python, HashMap in Java) are the most useful data structure in interviews: they turn many O(n²) solutions into O(n). Interviewers then ask the natural follow-up — "how does a hash map work inside?" This lesson answers it, and builds a small hash map so you can see every step.
1. The idea: compute where the key lives
An array gives O(1) access if you know the index. A hash table turns any key into an index:
- A hash function turns the key into a number:
hash("asha"). - That number is reduced to a bucket:
index = hash % number_of_buckets. - The value is stored in that bucket. To look it up later, compute the same index again — no searching.
A good hash function is fast, always gives the same number for the same key, and spreads different keys evenly over the buckets.
2. Collisions
Two different keys can land in the same bucket — above, asha (413) and meena (518) both give 3 when divided by 5. That is a collision, and it is unavoidable: there are far more possible keys than buckets. There are two classic ways to handle it.
Chaining
Each bucket holds a small list. A collision just adds to the list; a lookup scans that one short list.
class ChainedMap:
def __init__(self, buckets=5):
self.b = [[] for _ in range(buckets)]
def _index(self, key):
return sum(ord(ch) for ch in key) % len(self.b) # a toy hash, for the demo
def put(self, key, value):
chain = self.b[self._index(key)]
for pair in chain:
if pair[0] == key: # key already there: update it
pair[1] = value
return
chain.append([key, value])
def get(self, key):
for k, v in self.b[self._index(key)]:
if k == key:
return v
return None
m = ChainedMap()
for name, marks in [("ravi", 71), ("asha", 85), ("meena", 90), ("vikram", 62), ("neha", 77)]:
m.put(name, marks)
m.put("asha", 88)
print(m.get("asha"), m.get("meena"), m.get("arjun"))
print([len(chain) for chain in m.b])
88 90 None
[1, 0, 1, 2, 1]
Open addressing (linear probing)
No lists: if the bucket is taken, try the next bucket, then the next, until a free one is found. Lookups follow the same path. Python's dict uses a form of open addressing.
def probe_insert(table, key):
i = sum(ord(ch) for ch in key) % len(table)
while table[i] is not None: # taken: try the next slot
i = (i + 1) % len(table)
table[i] = key
return i
t = [None] * 7
print([probe_insert(t, k) for k in ["ab", "ba", "ca", "ac"]])
print(t)
[6, 0, 1, 2]
['ba', 'ca', 'ac', None, None, None, 'ab']
"ab" and "ba" have the same letter sum, so "ba" collides at slot 6 and moves to slot 0 (wrapping around); "ca" and "ac" are pushed along as well.
3. Load factor and resizing
The load factor is items / buckets. As it grows, chains get longer (or probe sequences get longer) and lookups slow down. So hash tables resize: when the load factor passes a limit — 0.75 in Java's HashMap — they allocate about twice as many buckets and re-insert every key (rehashing).
- A single resize costs O(n), but it happens rarely, so the amortised cost of an insert stays O(1).
- If you know the size in advance, create the map with that capacity to skip the resizes.
4. Complexity, honestly
| Operation | Average | Worst case |
|---|---|---|
| insert / lookup / delete | O(1) | O(n) |
The worst case happens when many keys collide into one bucket — a bad hash function, or deliberately chosen keys. Java 8+ limits the damage: when one bucket's chain grows past 8 entries, it becomes a balanced tree, so even the worst case is O(log n) for that bucket.
5. Java: hashCode() and equals() must agree
HashMap uses hashCode() to pick the bucket and equals() to find the key inside it. If you override one, override both: equal objects must have equal hash codes, or the map will look in the wrong bucket.
import java.util.*;
public class Main {
record Point(int x, int y) {} // a record writes equals() and hashCode() for you
static class BadPoint { // equals() without hashCode(): broken in a HashSet
int x, y;
BadPoint(int x, int y) { this.x = x; this.y = y; }
@Override public boolean equals(Object o) {
return o instanceof BadPoint p && p.x == x && p.y == y;
}
}
public static void main(String[] args) {
Set<Point> good = new HashSet<>();
good.add(new Point(1, 2));
System.out.println(good.contains(new Point(1, 2)));
Set<BadPoint> bad = new HashSet<>();
bad.add(new BadPoint(1, 2));
System.out.println(bad.contains(new BadPoint(1, 2)));
}
}
true
false
BadPoint uses the default hashCode() (based on the object's identity), so two equal points usually land in different buckets and contains says false.
Also: never change a field that the hash code depends on while the object is inside a HashMap or HashSet — it would sit in the wrong bucket and become impossible to find.
6. Which keys can be hashed?
- Python: only immutable values —
str,int,tuple— can be dict keys or set items. Alistcan't (TypeError: unhashable type: 'list'); convert it to atuple. - Use a tuple key for pairs and grid cells:
seen[(r, c)] = True.
seen = {(0, 1): "visited"}
print(seen[(0, 1)])
key = [0, 1]
print(seen.get(tuple(key)))
visited
visited
Common mistakes
- Saying a hash map lookup is "always O(1)" — it is O(1) on average; the worst case is O(n) (or O(log n) per bucket in Java 8+).
- Overriding
equals()in Java withouthashCode(). - Using a mutable object (a list, or an object you later change) as a key.
- Relying on the iteration order of
HashMap— it is not sorted and not insertion order (useLinkedHashMaporTreeMap).
Quick recap
- Hash function → number →
% buckets→ index; the same key always gives the same bucket. - Collisions are normal: chaining keeps a list per bucket; open addressing probes the next slots.
- Load factor = items / buckets; past the limit (0.75 in Java) the table doubles and rehashes.
- Average O(1), worst O(n). In Java,
equals()andhashCode()must agree.