Lesson 7 of 12 · 10 min · Collections, streams and generics

How HashMap works inside

Covers: Java 25 LTS (also valid on 21). Updated 13 Nov 2026. Part of the Java Full Stack Developer roadmap.

What you will learn

  • How put and get find 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 equals and hashCode, and how HashMap differs from ConcurrentHashMap

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)

  1. Compute h = key.hashCode().
  2. 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.
  3. Compute the bucket index: index = (n - 1) & hash, where n is the table length. Because n is a power of two this is the same as hash % n, but faster.
  4. If the bucket is empty, put a new node there.
  5. If not, walk the chain. For each node, check whether hash equals and then whether the keys are the same (== or equals). If a match is found, replace the value; otherwise append a new node at the end.
  6. Increase size; if size is greater than threshold, 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 size exceeds 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 to index + 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 null key is allowed (always stored in bucket 0), and null values are allowed.
  • No ordering guarantee. Iteration order depends on the hashes and capacity, and can change after a resize. Use LinkedHashMap or TreeMap if order matters.
  • Keys should be immutable. If a key's hash changes after insertion, the entry is lost (previous lesson). String and Integer are 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 HashMap between threads.
  • Relying on iteration order.
  • Not presizing a large map and causing many resizes.
  • Using Hashtable in new code.
  • Assuming O(1) always; poor hash functions degrade performance.

Try it yourself

  1. Write a key class whose hashCode always returns 1 and time inserting 50,000 entries compared with a good hash.
  2. Print HashMap iteration order for the same keys with capacity 16 and after adding many more entries.
  3. Compute (n - 1) & hash by hand for a few strings with n = 16.
  4. Write a tiny hash map with an array of linked lists to understand put and get.
  5. Replace a shared HashMap in a multi-threaded counter with ConcurrentHashMap.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 HashMap is 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/equals and immutable keys keep it O(1); iteration order is not guaranteed.
  • Use ConcurrentHashMap for concurrent access; presize big maps with HashMap.newHashMap.

Going deeper

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.