Notes
Requirements
Agree the contract first. Put adds a key or replaces its value. Get returns the value or null. Remove deletes and returns the old value. All three should take constant time on average. Keys can be any type with sensible equals and hash code, and one null key is allowed. The map grows on its own. The usual follow-up is to make it safe for many threads, so leave room for that. Iteration order is out of scope.
- put(key, value): add or replace
- get(key): value or null
- remove(key): value or null
- size()
- average O(1) for all three
- any key type with equals and
- hashCode, null key allowed
- grow automatically
- then: make it thread-safe
- out of scope: iteration order
Structure
The structure is an array of buckets. A key's hash picks a bucket, and each bucket holds a short linked list of nodes, called a chain, because different keys can land in the same bucket. Each node stores the hash, the key, the value and a pointer to the next node. To find a key, compute its bucket and walk that short chain comparing keys. If chains stay short, every operation is constant time on average.
- table: Node[16]
- [0] -> null
- [1] -> (user-7,7) -> (user-9,9)
- [2] -> null
- [3] -> (user-1,1)
- ...
- key -> hash -> index -> walk
- the short chain, compare keys
Hashing
How does a key become a bucket index? Take its hash code and reduce it to the table size. Keep the capacity a power of two, and hash modulo n becomes hash and n minus one, a single fast bit mask. The catch is that the mask only looks at the lowest bits, and many hash codes differ only in their high bits. So first spread the hash by mixing the top sixteen bits into the bottom sixteen with an exclusive or.
static int spread(Object key) {
int h = key == null
? 0 : key.hashCode();
return h ^ (h >>> 16);
}
static int indexFor(int h, int n) {
return h & (n - 1); // n = 2^k
}
n = 16: index = last 4 bits put
Put works like this. Spread the hash, find the bucket and walk its chain. If a node has the same hash and an equal key, replace its value and return the old one; the size does not change. Otherwise push a new node at the head of the chain, increase the size, and if the map is now more than three quarters full, resize. Comparing the stored hash first is a cheap filter before calling equals.
int h = spread(key);
int i = indexFor(h, table.length);
for (e = table[i]; e != null; e = e.next)
if (e.hash == h &&
Objects.equals(e.key, key)) {
V old = e.value; e.value = value;
return old;
}
table[i] = new Node(h, key, value,
table[i]);
if (++size > cap * 0.75) resize(); get and remove
Get is the same walk, returning the value or null. Remove walks while remembering the previous node. When it finds the key, it links the previous node straight to the next one, or moves the bucket head if the match was first, then decreases the size. Using Objects equals instead of key dot equals means the one null key works without a special case.
Node prev = null;
for (e = table[i]; e != null;
prev = e, e = e.next)
if (e.hash == h &&
Objects.equals(e.key, key)) {
if (prev == null) table[i] = e.next;
else prev.next = e.next;
size--; return e.value;
}
return null; The contract
The map is only correct if keys keep Java's contract. Rule one: if two keys are equal, their hash codes must be equal, otherwise get searches the wrong bucket and misses a key that is there. Rule two: never change a key after putting it. Its hash changes, but the node stays in the old bucket, so the entry becomes unreachable. The demo shows exactly this: get returns null while the size is still one. That is why good keys are immutable.
- rule 1: a.equals(b) means
- a.hashCode() == b.hashCode()
- else get() looks in the
- wrong bucket
- rule 2: never mutate a key
- after put(): its hash moves,
- the node does not
- demo: put(k), k.name = "beta"
- get(k) = null, size still 1
Resizing
As the map fills, chains get longer, so at a load factor of three quarters we double the table and move every node. Because the size is a power of two, doubling adds exactly one bit to the mask, so each node either stays at the same index or moves up by the old size. A single resize costs time proportional to the size, but it happens so rarely that the average cost of a put stays constant. A thousand keys need only seven resizes.
new table = 2 x old length for each node in each old bucket: j = hash & (newN - 1) push node onto new[j] one more hash bit decides: j == i or j == i + oldN 1000 keys: capacity 2048, 7 resizes, longest chain 4
Bad hash codes
Now the worst case. If a key class returns the same hash code for everything, every key lands in one bucket, the chain grows to the full size of the map, and constant time quietly becomes linear. The real Java map defends against this by turning any chain longer than eight into a balanced tree, giving logarithmic time even in the worst case. Mention it: attackers can choose keys that collide on purpose to slow a server down.
- hashCode() { return 42; }
- 200 keys, longest chain 200
- every get is a list scan: O(n)
- Java 8+ fix: a chain longer
- than 8 turns into a red-black
- tree, so O(log n) worst case
- attackers can force collisions
- with chosen keys: hash flooding
Concurrency
Our map is not safe for many threads. If two threads put different keys into the same empty bucket, both read the head as empty and both write their own node as the new head, so one key silently disappears. A put during a resize can lose nodes, and size plus plus is a read, add and write that can drop updates. Just saying synchronized on every method fixes it, but then only one thread can use the map at a time.
- thread A and B: put into the
- same empty bucket
- both read head = null
- both write their node as head
- one key silently vanishes
- resize during put: nodes moved
- twice or lost
- size++ is read-modify-write:
- counts drift
Lock striping
A better design is lock striping. Keep sixteen independent maps, each with its own lock, and send each key to one stripe by its hash. Two threads only wait for each other when their keys share a stripe, so up to sixteen can work at once. A merge method does the read and the write under one lock, which is what a counter needs. In the demo, eight threads add five thousand each and the total is exactly forty thousand.
List<MyHashMap> stripes (16)
List<ReentrantLock> locks (16)
int s = stripe(key);
locks.get(s).lock();
try { return fn.apply(stripes.get(s)); }
finally { locks.get(s).unlock(); }
merge(): read + write in one lock
8 x 5000 increments = 40000 Real world
Interviewers like to hear what the real libraries do. Java's hash map uses chaining, a power-of-two table, a load factor of three quarters, and turns long chains into trees. The concurrent hash map goes further than our stripes: it fills an empty bucket with a single compare-and-set, locks only the head node of a busy bucket, lets several threads help with a resize, and keeps the size in striped counters. The old Hashtable uses one lock for everything.
- HashMap: chaining, treeify at 8,
- power-of-two table, 0.75
- ConcurrentHashMap (Java 8+):
- CAS to fill an empty bucket
- lock only the bucket head
- when it is not empty
- resize helped by many threads
- size kept in striped counters
- Hashtable: one lock, avoid
Extensibility
Follow-ups build on the same core. Open addressing stores entries directly in the array and probes the next slot on a collision, which is friendlier to the CPU cache. A map can shrink when mostly empty. Thread a doubly linked list through the nodes and you get insertion order; move a node to the front on every get and you have an LRU cache. Add an expiry to each node and it becomes a cache with time to live.
- open addressing: no nodes,
- probe the next free slot
- (linear, Robin Hood hashing)
- shrink when mostly empty
- iteration in insert order:
- a doubly linked list of nodes
- LRU cache: that list + move
- to front on get
- TTL: an expiry on each node
Testing
The full code is below the player. The demo inserts a thousand keys and prints the capacity, the number of resizes and the longest chain; replaces a value and checks the size did not change; removes a key and stores a null key; shows the two hundred long chain from a bad hash code; shows a mutated key going missing; and runs eight threads of counter updates on the striped map without losing a single one.
1000 keys: capacity 2048, resizes 7, longest chain 4 put same key: old 777, size 1000 remove(user-1) = 1, then null null key: put then get = -1 bad hashCode: longest chain 200 mutated key: get(k) = null, size 1 striped: 8 x 5000 = 40000
Say it like this
Here is the short version to say out loud. An array of buckets whose size is a power of two, each a chain of nodes. Spread the hash, mask it to an index, compare the stored hash and then equals. Double the table at three quarters full, so put is constant time amortised. Keys must keep the equals and hash code contract and never change. For many threads, use lock striping or compare-and-set per bucket.
- "An array of buckets, size 2^k,
- each a chain of nodes. Spread
- the hash, mask to an index,
- compare hash then equals.
- Double at 0.75 full, so put is
- O(1) amortised. Keys must keep
- the equals and hashCode contract
- and never change. For threads,
- lock striping or CAS per bucket."