Foundation · Module 5 · Lesson 1
Hash-table internals
Buckets, hash functions, collisions, load factor, and resizing.
15–25 min readLesson 27 of 123 Interactive Lab
Lesson 27 of 123
1d streakInteractive Visualization
See how hash-table internals works
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive data structure
Change the structure and watch the operation
Try an operation and connect the visible movement to its runtime cost.
0
empty
1
empty
2
empty
3
empty
4
cat: 4
5
empty
6
tea: 9
sun: 2
readyThe demo hash adds character codes, then takes the remainder after dividing by seven.
How Hash Tables Work: Buckets, Collisions & Rehashing
A Hash Table maps arbitrary keys (strings, objects, numbers) to array indices using a Hash Function. It provides average O(1) time complexity for insertions, lookups, and deletions by transforming a key into an integer bucket index.
Hash Table with Separate Chaining (Java HashMap Architecture)text
Key -> hash(key) -> index = hash & (capacity - 1)
Bucket Array (Array of Node pointers):
[ 0 ] -> null
[ 1 ] -> [ Key: "apple" | Val: $1.20 ] -> [ Key: "melon" | Val: $3.50 ] -> null (Collision Chain)
[ 2 ] -> [ Key: "orange" | Val: $0.80 ] -> null
[ 3 ] -> null
[ 4 ] -> [ Key: "banana" | Val: $0.50 ] -> null
Collision Resolution Strategies:
1. Separate Chaining: Each bucket holds a linked list (or balanced Red-Black tree when length >= 8 in Java).
2. Open Addressing (Linear Probing): On collision at slot i, probe i+1, i+2, etc., until an empty slot is found.| Metric / Property | HashMap (Separate Chaining) | Open Addressing (Linear Probing) |
|---|---|---|
| Collision Handling | Appends node to linked list or tree at bucket | Searches forward for the next empty array slot |
| Deletion Cost | Trivial: unlink node from chain | Requires tombstone marker to avoid breaking search chains |
| Max Load Factor | Can exceed 1.0 (typical threshold 0.75) | Must stay well below 1.0 (typically 0.5 - 0.7) |
| Cache Performance | Pointer chasing across heap nodes | Excellent cache locality (contiguous array probing) |
Load Factor and Dynamic Rehashing Cost
The Load Factor (α) equals
size / capacity. When size > capacity * 0.75, the hash table allocates an array of double the capacity and re-hashes every element. Like dynamic arrays, while one rehash costs $O(n)$, amortized lookup and insertion remain strictly O(1).Interview Trap: Mutable Object Keys
Never mutate an object that is being used as a key in a HashMap or HashSet! If you mutate a field that affects
hashCode(), the object’s bucket index changes. When you subsequently call map.get(key), the map searches the wrong bucket and fails to find the entry, causing a severe memory leak.Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Lookup / insert
Expected O(1), worst O(n)
O(n) table
The bound follows from the number of states visited and the work performed per transition.When to use it
- Presence, uniqueness, frequency, complement, and previously seen state queries.
- Replacing repeated scans with indexed history.
- Grouping values by a canonical key.
Common mistakes
- Assuming hash lookup has a deterministic O(1) worst case.
- Updating the map before a query that requires a distinct earlier item.
- Using mutable or inconsistent keys.
Practice prompts
- Reproduce the worked Hash-table internals example without looking at the trace.
- Change one input condition and explain whether the Hash-table internals invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.