Lesson 7 of 12 · 10 min · Collections, streams and generics
How HashMap works inside
What you will learn
- How
putandgetfind a place for a key - Buckets, the hash function and the index calculation
- How collisions are handled, and what a tree bin is
- Capacity, load factor and resizing
- Why keys need good
equalsandhashCode, and howHashMapdiffers fromConcurrentHashMap
In simple words
Imagine a wall of 16 pigeonholes. To store a letter for "Asha", you run her name through a rule that gives a number from 0 to 15 and drop the letter in that hole. To find it later, you run the same rule and go straight to that hole instead of checking every hole. That is a hash map. Sometimes two names land in the same hole, so each hole can hold a small list, and when the wall gets crowded the map builds a bigger wall.
Words to know
- Bucket: one slot of the map's internal array.
- Hash: a number computed from a key by
hashCode. - Collision: two different keys that land in the same bucket.
- Load factor: how full the map may get before it grows (default 0.75).
The structure
A HashMap keeps an array of buckets (the table). The default capacity is 16 (the array is created lazily on the first put), and the capacity is always a power of two. Each bucket holds a chain of nodes: a node stores the key, value, the hash and a pointer to the next node.
index 0: null
index 1: [k1,v1] -> [k9,v9]
index 2: null
index 3: [k4,v4]
...
index 15: [k7,v7]
put(key, value)
- Compute
h = key.hashCode(). - Spread the bits:
hash = h ^ (h >>> 16). XORing the high 16 bits into the low 16 helps because the index only uses the low bits. - Compute the bucket index:
index = (n - 1) & hash, wherenis the table length. Becausenis a power of two this is the same ashash % n, but faster. - If the bucket is empty, put a new node there.
- If not, walk the chain. For each node, check whether
hashequals and then whether the keys are the same (==orequals). If a match is found, replace the value; otherwise append a new node at the end. - Increase
size; ifsizeis greater thanthreshold, resize.
Because the equals check happens only inside one bucket, a good hashCode that spreads keys evenly keeps chains very short, and get is O(1) on average. A key with a bad hashCode pushes everything into a few buckets.
get(key)
The same first steps: compute the spread hash, find the index, then walk that bucket's chain comparing hash and equals until the key is found (return the value) or the chain ends (return null). Note that equals is only used after the bucket is chosen by hashCode, so if equal keys had different hash codes the lookup would look in the wrong bucket and miss. This is why overriding equals requires overriding hashCode (previous lesson).
Collisions and treeification
Two keys with the same bucket index collide. Java 7 and earlier stored a linked list per bucket, which degrades to O(n) if many keys collide (and could be exploited for denial-of-service attacks by crafting colliding keys). Since Java 8:
- When a single bucket's chain reaches 8 nodes and the table has at least 64 buckets, the chain is converted into a balanced red-black tree (a "tree bin"), so lookups in that bucket cost O(log n) instead of O(n).
- If the table is smaller than 64 when a chain hits 8, the map resizes instead of treeifying.
- When a tree bin shrinks to 6 or fewer nodes it turns back into a list.
- If the keys implement
Comparable, the tree can order them by comparison, which makes it more efficient.
So in the worst case get and put are O(log n), and average O(1).
Capacity, load factor and resizing
- Initial capacity: 16 by default.
- Load factor: 0.75 by default. The threshold is
capacity x load factor= 12 for the default. - When
sizeexceeds the threshold, the table is doubled (16, 32, 64, ...), and the nodes are redistributed. Because the capacity doubles, each node either stays at the same index or moves toindex + oldCapacity, which makes resizing cheap per node but still O(n) overall.
If you know roughly how many entries you will store, size the map to avoid repeated resizing: since Java 19 use HashMap.newHashMap(expectedEntries), which calculates the capacity for you; in older code you calculate (int) (expected / 0.75f) + 1.
Map<String, Integer> m = HashMap.newHashMap(1000); // no resizes while adding up to 1000 entries
A lower load factor means fewer collisions and more memory; a higher one saves memory and slows lookups. The default (0.75) is a good trade-off.
Keys, null and order
- One
nullkey is allowed (always stored in bucket 0), andnullvalues are allowed. - No ordering guarantee. Iteration order depends on the hashes and capacity, and can change after a resize. Use
LinkedHashMaporTreeMapif order matters. - Keys should be immutable. If a key's hash changes after insertion, the entry is lost (previous lesson).
StringandIntegerare ideal keys: immutable with well-spread hashes (and a string caches its hash). - Iteration cost is proportional to the capacity plus size, so a huge, mostly empty map is slow to iterate.
HashMap, Hashtable and ConcurrentHashMap
| HashMap | Hashtable | ConcurrentHashMap | |
|---|---|---|---|
| Thread-safe | no | yes (every method synchronized) | yes (fine-grained) |
| Null key and values | allowed | not allowed | not allowed |
| Speed under many threads | unsafe | slow (one lock) | fast |
| Status | standard | legacy, avoid | the choice for concurrent code |
Using a plain HashMap from several threads can lose entries or corrupt it, because resizing and updates are not atomic. ConcurrentHashMap (Java 8 and later) uses CAS operations and locks only the bucket head, so reads rarely block and writers to different buckets do not wait for each other; operations such as computeIfAbsent and merge are atomic. Collections.synchronizedMap wraps a map with one lock and is slower. HashSet is just a HashMap where the elements are the keys and the value is a dummy object.
Fail-fast iterators
HashMap iterators are fail-fast: if the map is structurally modified (an entry added or removed) after the iterator was created, except through the iterator's own remove, the next call throws ConcurrentModificationException. This is a best-effort bug detector, not a thread-safety guarantee.
Interview-ready summary
If asked "how does HashMap work?", a complete answer is: it is an array of buckets; put computes the key's hash (spread by XORing high bits), picks the bucket with (n - 1) & hash, and stores a node there; collisions form a linked list that becomes a red-black tree at 8 nodes (when the table has at least 64 buckets); get repeats the hash and scans the bucket using equals; when the entry count passes capacity x 0.75 the table doubles; keys need consistent equals and hashCode and should be immutable; it is not thread-safe, so use ConcurrentHashMap across threads.
Common mistakes
- Mutable keys or a missing
hashCode. - Sharing a
HashMapbetween threads. - Relying on iteration order.
- Not presizing a large map and causing many resizes.
- Using
Hashtablein new code. - Assuming O(1) always; poor hash functions degrade performance.
Try it yourself
- Write a key class whose
hashCodealways returns 1 and time inserting 50,000 entries compared with a good hash. - Print
HashMapiteration order for the same keys with capacity 16 and after adding many more entries. - Compute
(n - 1) & hashby hand for a few strings withn = 16. - Write a tiny hash map with an array of linked lists to understand
putandget. - Replace a shared
HashMapin a multi-threaded counter withConcurrentHashMap.merge.
Check yourself
How does HashMap decide which bucket a key goes to?
It computes the key's hashCode, spreads the bits with h ^ (h >>> 16), and takes (n - 1) & hash as the index, where n is the table size (a power of two).
What happens when two keys land in the same bucket?
They are stored in a chain; lookups compare keys with equals inside that bucket. From Java 8, a long chain (8 or more, with a table of at least 64) becomes a red-black tree.
When does a HashMap resize?
When the number of entries exceeds capacity times the load factor (12 for the default 16 and 0.75); it doubles the table.
Why does HashMap call hashCode before equals?
hashCode finds the right bucket quickly; equals then identifies the exact key within it. Equal keys must have equal hash codes for lookups to work.
Interview questions
Explain the internal working of HashMap.
Array of buckets, spread hash and index formula, nodes with key, value, hash and next, collision chains converted to trees at 8 nodes, resize at 0.75 load factor by doubling, reliance on hashCode and equals, one null key allowed, not thread-safe.
What changed in HashMap in Java 8?
Long collision chains turn into balanced trees, reducing worst-case lookup from O(n) to O(log n), and the resize redistribution and hash spreading were simplified.
How is ConcurrentHashMap different from Collections.synchronizedMap?
ConcurrentHashMap uses fine-grained locking and compare-and-swap, so reads are mostly lock-free and writes to different buckets run in parallel; the synchronized wrapper uses one lock for the entire map and blocks all other threads.
Summary
- A
HashMapis an array of buckets; the index is(n - 1) & spread(hashCode). - Collisions form chains that become red-black trees at 8 nodes; resizing doubles the table at 0.75 load.
- Good, consistent
hashCode/equalsand immutable keys keep it O(1); iteration order is not guaranteed. - Use
ConcurrentHashMapfor concurrent access; presize big maps withHashMap.newHashMap.
Going deeper
- HashMap API documentation: capacity, load factor and performance notes.
- ConcurrentHashMap API documentation: concurrency behaviour.
- dev.java: The Map interface: maps in the collections guide.
- Java Collections Framework Overview: where HashMap sits.
See how much of this you can explain
A free mock interview asks you new questions on Core Java: OOP, collections and exceptions for Java Full Stack Developer and scores every answer, with what to fix.