HashMap stores key-value pairs in an array of buckets. To find a key, it calls hashCode(), mixes the bits, uses the result to pick a bucket, and then compares keys with equals() inside that bucket. That gives O(1) average get and put. Collisions are chained in a linked list, and a long chain in a big enough table is converted to a balanced tree. When the map holds more than 75% of its capacity, the table doubles.
Constant (from HashMap.java) | Value | Meaning |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | 16 | Bucket count of a default map (allocated on the first put) |
| DEFAULT_LOAD_FACTOR | 0.75 | Resize when size exceeds capacity x 0.75 |
| TREEIFY_THRESHOLD | 8 | A bin this long may become a tree |
| UNTREEIFY_THRESHOLD | 6 | A tree this small turns back into a list |
| MIN_TREEIFY_CAPACITY | 64 | Below this table size, resize instead of treeifying |
Tested against. Temurin 25.0.4.1. The constants above were read from theHashMapsource of the JDK; the numbers below come from a program that reads the privatetablefield by reflection. It is not in a repository: download HashMapInternals.java and runjavac -g HashMapInternals.java && java --add-opens java.base/java.util=ALL-UNNAMED HashMapInternals. Internals are implementation details and can change between releases.
Step 1: the hash is spread, then masked into an index
The key’s hashCode() is not used directly. HashMap XORs the top 16 bits into the bottom 16 (h ^ (h >>> 16)) so that keys whose hash codes differ only in the high bits still spread across buckets, because the table length is a power of two and the index is just (n - 1) & hash, which keeps only the low bits. A null key has hash 0 and always lands in bucket 0.
apple hashCode= 93029210 spread= 93030097 index=(16-1)&spread=1
banana hashCode=-1396355227 spread=-1396317280 index=(16-1)&spread=0
cherry hashCode=-1361513063 spread=-1361552575 index=(16-1)&spread=1
null key hash = 0, so it always lands in bucket 0Apple and cherry land in the same bucket, so they will be chained. Because the index uses a bit mask, the capacity is always rounded up to a power of two. Download: HashMapInternals.java.
Step 2: the table is lazy, and it doubles at 75%
new HashMap<>() allocates no table at all. The first put creates 16 buckets. When the size after an insert exceeds capacity x 0.75 (12 for 16), the table doubles to 32 and every entry is redistributed.
after new HashMap() : capacity=0
put #1 changed capacity 0 -> 16
put #13 changed capacity 16 -> 32
new HashMap<>(100) first put -> capacity 128
new HashMap<>(17) first put -> capacity 32The constructor argument is rounded up to the next power of two: 100 becomes 128 and 17 becomes 32. To hold N entries without a resize, ask for N / 0.75 + 1 buckets (or use HashMap.newHashMap(N), added in Java 19, which does that arithmetic).
Going deeper: why the load factor is 0.75
It is a trade-off. A lower factor wastes memory on empty buckets; a higher one lengthens chains and slows lookups. The source comments say 0.75 gives a good balance of time and space. Resizing is also not free: all entries are moved, which is why pre-sizing a map you know will be large is a cheap win. Compare with the synchronised siblings in HashMap vs Hashtable and HashMap vs ConcurrentHashMap.
Step 3: collisions become a list, then a tree
When two keys land in one bucket, the new entry is appended to a linked list of Node objects, and get walks the list comparing hashes and then equals. If a single bin grows to 8 nodes, HashMap normally converts it to a red-black tree of TreeNodes (JEP 180, Java 8), which makes the worst case O(log n) instead of O(n). But there is a guard: if the table is smaller than 64 buckets, it resizes instead, hoping to spread the entries. The experiment uses a key whose hashCode is always 1, so everything collides.
size= 1 capacity=16 bin node = HashMap$Node
size= 8 capacity=16 bin node = HashMap$Node
size= 9 capacity=32 bin node = HashMap$Node
size=10 capacity=64 bin node = HashMap$Node
size=11 capacity=64 bin node = HashMap$TreeNode
get(Colliding(7)) still works: 7Watch the sequence: the 9th insert grows the table from 16 to 32 and the 10th from 32 to 64 (still a list), and only on the 11th does the bin become a TreeNode, because the table has finally reached 64. The key class implements Comparable, which lets the tree order colliding keys; without it the tree must fall back to slower tie-breaking. (The display lines above are a subset of the full program output, shown with the same text.) The tree turns back into a list when it shrinks to 6 nodes.
Step 4: what get() really does
- Compute the spread hash of the key and the index
(n - 1) & hash. - If the table is empty or the bucket is empty, return
null. - Check the first node: same hash and (same reference or
equals) means found. - Otherwise walk the list, or search the tree if the bin is a tree.
The stored hash is compared first, so equals runs only when the hashes match. This is why the contract matters: equal keys must have equal hash codes, or get looks in the wrong bucket. See also how Comparable is used by tree bins.
A key you mutate is a key you lose
The bucket is chosen when the entry is inserted. If the key’s fields (and so its hash) change afterwards, get goes to a different bucket and misses, although the entry is still in the map.
get before mutation : found
get after mutation : null (size still 1)
get after restoring : foundUse immutable keys: String, the wrapper classes, enums or records of immutable fields. See also immutable collections. Download: HashMapInternals.java.
Iteration order is the bucket order
A HashMap iterates bucket by bucket, so the order depends on hashes and capacity and can change after a resize. Never rely on it.
HashMap : [banana, date, apple, cherry]The keys went in as banana, apple, cherry, date. If you need insertion order, use LinkedHashMap; for sorted order, use a TreeMap or see sorting a HashMap by key and value. Since Java 21 a LinkedHashMap also offers first and last entry methods.
Thread safety
HashMap is not thread safe. Concurrent writes can lose entries or corrupt the table, and a reader can see a half-built structure. Use ConcurrentHashMap or wrap access with proper locking; the trade-offs are in the HashMap vs ConcurrentHashMap guide and the concurrency interview questions.
Common mistakes
Overriding equals without hashCode
Two equal objects get different hash codes, land in different buckets, and the map cannot find them. Always override both, using the same fields.
Mutating a key after insertion
The entry becomes unreachable, as the output above shows. Make keys immutable.
Using a constant or poor hashCode
Every key collides and the map degrades to a list or a tree. A tree helps only if keys are Comparable.
Expecting insertion order
Iteration order follows buckets. Use LinkedHashMap when order matters.
Sharing a HashMap between threads
It is not synchronised. Use ConcurrentHashMap.
Common interview questions
How does HashMap work internally?
It keeps an array of buckets. A key’s hash code is spread, masked into an index, and the entry is stored in that bucket as a list node or tree node. Lookup goes to the same bucket and compares keys with equals. The table doubles when the size passes 75% of capacity.
What happens when two keys have the same hash code?
They go to the same bucket and are chained. Lookup compares each key’s equals. At 8 nodes in a bin, and a table of at least 64 buckets, the bin becomes a red-black tree.
Why is the capacity a power of two?
The index is computed as (n - 1) & hash, a single AND instead of a modulo. It works as a modulo only when n is a power of two, and resizing then just splits each bucket in two.
Why does HashMap spread the hash with h ^ (h >>> 16)?
Only the low bits select the bucket in small tables. Mixing the high bits in prevents keys that differ only there from colliding systematically.
Can HashMap hold null keys and values?
Yes: one null key (hash 0, bucket 0) and any number of null values. ConcurrentHashMap and Hashtable reject nulls. More in the collections interview questions.
FAQ
What is the default capacity and load factor of HashMap?
16 buckets and a load factor of 0.75, so the first resize happens when the 13th entry is added.
What is the time complexity of HashMap get and put?
O(1) on average. With heavy collisions it is O(n) for a list bin and O(log n) for a tree bin.
Since which Java version does HashMap use trees?
Java 8, through JEP 180 (Handle Frequent HashMap Collisions with Balanced Trees).
Should you tune HashMap? Rarely. Use immutable keys with good hash codes, pre-size a map you know will be large, and leave the rest alone. Reach for ConcurrentHashMap the moment threads share the map. Related reading in the same series: lambda expressions and the Java 8 features overview.
No Comments yet!