How a Hash Table Works Internally
"O(1) lookup" is an average, not a guarantee, and the difference is where the interesting questions live. This lesson opens the box: how a key becomes a bucket index, what happens when two keys land in the same bucket, and when the average quietly degrades to O(n).
Key to index
- The key is fed to a hash function, producing an integer.
- That integer is reduced into the table's range, usually
hash % capacity. - The entry is stored in the bucket at that index.
- Lookup repeats the same computation and goes straight to the bucket.
Nothing is searched, so the cost does not depend on how many entries the table holds — as long as entries are spread evenly across buckets. A good hash function is exactly the one that achieves that spread.
Collisions
Two different keys can hash to the same bucket. This is unavoidable — there are more possible keys than buckets — so every hash table has a strategy for it.
| Separate chaining | Open addressing | |
|---|---|---|
| Idea | Each bucket holds a list of entries | Probe for the next free bucket |
| Deletion | Straightforward | Needs a tombstone marker |
| Memory | Extra pointers per node | Compact; one flat array |
| Cache behaviour | Weaker — pointer chasing | Stronger — contiguous probing |
| Used by | Java HashMap, C++ unordered_map | Python dict, Go maps |
Java's HashMap adds a refinement: once a single bucket holds more than eight entries and the table is large enough, that chain is converted into a balanced tree, so the worst case per bucket becomes O(log n) instead of O(n). That change landed in Java 8 specifically to blunt hash-collision denial-of-service attacks.
Load factor and resizing
Load factor = entries / buckets. As it rises, collisions become more likely and lookups slow down. When it crosses a threshold — 0.75 in Java, around 0.66 in Python — the table allocates a larger array and rehashes every entry into it.
Pre-size when you know the size
new HashMap<>(expectedSize / 0.75f + 1) avoids repeated rehashing while a map is filled in a loop. Same reasoning as pre-sizing a dynamic array.
Mutating a key after inserting it
The bucket was chosen from the key's hash at insert time. Change a field the hash depends on, and the entry becomes unreachable — get() looks in a different bucket and finds nothing, while the entry still occupies memory. Hash-map keys should be immutable.
| Operation | Average | Worst case |
|---|---|---|
| Insert | O(1) | O(n), or O(log n) with treeified buckets |
| Lookup | O(1) | O(n), or O(log n) with treeified buckets |
| Delete | O(1) | O(n), or O(log n) with treeified buckets |
| Iterate all entries | O(n + capacity) | O(n + capacity) |
The equals / hashCode contract
If you use your own class as a key, you must override both equals() and hashCode(), and they must agree: equal objects must produce equal hash codes. Override only equals, and two equal objects can land in different buckets — the map will happily hold both.
final class Point {
private final int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
@Override public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return x == p.x && y == p.y;
}
@Override public int hashCode() {
return Objects.hash(x, y); // consistent with equals
}
}Key takeaways
- A hash function turns a key into a bucket index, so lookups skip searching entirely.
- Collisions are resolved by chaining or open addressing; both are unavoidable in principle.
- Load factor drives resizing, and resizing rehashes every entry.
- Equal objects must have equal hash codes, and keys must not be mutated after insertion.
Frequently asked questions
Why is hash table lookup O(1) on average but O(n) in the worst case?
On average, entries are spread across buckets so a lookup examines only a few. If every key hashes to the same bucket, the table degenerates into one long chain and a lookup has to scan all n entries.
What is the load factor of a hash table?
The ratio of stored entries to available buckets. When it exceeds a threshold — 0.75 in Java — the table grows and every entry is rehashed into the larger array.
What happens if you override equals but not hashCode?
Two objects that are equal can produce different hash codes and land in different buckets, so a map lookup with an equal key will fail to find the stored entry.
Test yourself on Hashing
Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.
⚡ Start the Hashing quiz