PHASE 9Intermediate ~39 min· topic 4 of 13

Topic 9.4

HashMap Internals

In one line

A HashMap is an array of buckets. It turns each key's hashCode into a bucket index (after mixing the high bits into the low ones), keeps colliding entries in a linked list that becomes a red-black tree past 8 nodes (Java 8+), and doubles the array when it's 75% full, giving O(1) expected get and put.

Think of it like this

A cloakroom with numbered hooks. When you hand in your coat, the attendant works out a hook number from your ticket and hangs it there. To get it back, they work out the same number and go straight to that hook: no searching the whole room. Sometimes two coats land on the same hook; then the attendant checks the tickets on that hook one by one. When the room gets too full, they move to a room with twice as many hooks and rehang everything. That's a hash table, and HashMap is Java's.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Hash code: An int that an object computes from its contents with hashCode(). Equal objects must give equal hash codes.
Bucket: One slot of the map's internal array. All entries whose keys map to that index live there.
Collision: Two different keys ending up in the same bucket.
Spreading: Mixing the high bits of a hash code into the low bits (h ^ (h >>> 16)) so that the low bits used for the index vary more.
Load factor: How full the table may get before it grows, as a fraction of capacity. The default is 0.75.
Threshold: The size at which the next put triggers a resize: capacity × load factor.
Resize (rehash): Allocating a table twice as big and moving every entry into it.
Treeify: Turning a long bucket list into a red-black tree so lookups in it are O(log n).
Red-black tree: A self-balancing binary search tree. Its height stays about log n, so searching it is fast.

Step by step

01The table and its nodes

A new HashMap has table = null, size = 0 and threshold set from the capacity you asked for. The first put calls resize(), which allocates new Node[16] and sets the threshold to 12.

Each bucket is either null, a single Node, a linked chain of Nodes, or (after treeifying) a TreeNode that is the root of a red-black tree. The node stores the key's spread hash so later comparisons and resizes don't call hashCode() again.

The table and its nodesdiagram

Rendering diagram…

02From key to bucket: hash, spread, mask

Step 1: int h = key.hashCode(); For String this is specified: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1], computed once and cached in the string. For Integer it's the value itself.

Step 2: hash = h ^ (h >>> 16). >>> shifts the bits right, filling with zeros, so the top half lands on the bottom half and ^ (XOR) mixes them. The top half is unchanged.

Step 3: index = (n - 1) & hash. With n = 16, n - 1 = 0b1111, so the index is just the lowest four bits of the spread hash. That's why the capacity must be a power of two: the mask trick only works then, and a bitwise AND is much cheaper than %.

HashMap.java (from the JDK)whole filejava

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// inside putVal / getNode:
Node<K,V> first = tab[(n - 1) & hash];

03put: four cases

1. The bucket is empty: create a node there. 2. The first node matches (p.hash == hash && (p.key == key || key.equals(p.key))): remember it. 3. The bucket is a tree: delegate to putTreeVal. 4. Otherwise walk the list; if a node matches, remember it; if you reach the end, append a new node at the tail, and if the list has grown past 8 nodes, call treeifyBin.

If a matching node was found, its value is replaced and the old value is returned; size doesn't change. If a new node was added, modCount and size go up, and if size > threshold, the table is resized. That's why put returns the previous value or null.

Comparing the cached hash first is a cheap filter: equals (which might compare long strings) only runs on nodes whose hash already matches.

put: four casesdiagram

Rendering diagram…

04Load factor, threshold and resize

With capacity 16 and load factor 0.75, the threshold is 12. Adding the 13th entry triggers a resize to 32 (threshold 24), then 64 at the 25th, 128 at the 49th, and so on. Each resize is O(n), but doubling makes put amortised O(1), exactly as with ArrayList's growth in Topic 9.2.

Why 0.75? It's a time-space trade-off. With a good hash, the expected chain length stays well under 1 at that fill level. A higher load factor saves memory but lengthens chains; a lower one wastes slots. The JDK's own comment notes that at 0.75 the chance of a bucket holding 8 entries is under one in ten million, which is why treeify is a defence, not a normal path.

The power-of-two doubling has a neat consequence: when the table goes from 16 to 32, the index uses one more bit of the hash. A node at index j stays at j if that bit (hash & 16) is 0, or moves to j + 16 if it's 1. Java 8 splits each bucket into a "lo" and a "hi" list this way, keeping their order.

Load factor, threshold and resizediagram

Rendering diagram…

05Pre-sizing: the capacity you pass isn't the size you get

new HashMap<>(100) rounds the capacity up to the next power of two, 128, giving a threshold of 96. Put 100 entries and it still resizes once, to 256. To hold n entries with no resize you need a capacity of at least n / 0.75, rounded up.

Java 19 added HashMap.newHashMap(int numMappings), which does that arithmetic for you. On older versions, write new HashMap<>((int) (n / 0.75f) + 1), or use Guava's Maps.newHashMapWithExpectedSize.

Main.javawhole filejava

Map<String, User> a = new HashMap<>(100);                   // capacity 128, resizes at the 97th entry
Map<String, User> b = new HashMap<>((int) (100 / 0.75f) + 1); // capacity 256, no resize for 100
Map<String, User> c = HashMap.newHashMap(100);              // Java 19+: same as b

06Treeify: the Java 8 defence against bad hashing

Before Java 8, a bucket was always a linked list, so a map whose keys all collided degraded to O(n) per lookup. Attackers used this ("hash flooding"): sending thousands of request parameters whose String hash codes collide ("Aa" and "BB" both hash to 2112, and so do all their combinations) could freeze a web server.

Since Java 8, when a bucket grows past 8 nodes and the table has at least 64 slots, the bucket becomes a red-black tree ordered by hash, then by compareTo if the keys are Comparable and of the same class, then by a tie-breaker. Lookups in that bucket become O(log n). This is why giving key classes a Comparable implementation helps in the worst case.

Tree nodes are about twice the size of list nodes, so the map only treeifies when it must, and converts back to a list (UNTREEIFY_THRESHOLD = 6) when a resize leaves a bucket small.

07The two deadly key mistakes

**Overriding equals without hashCode**: two equal keys get different identity hash codes, land in different buckets, and the map stores both. get with an equal key usually returns null.

**Mutating a key after put**: the node sits in the bucket chosen by the old hash. Change a field that hashCode uses and every later lookup computes a different bucket. The entry is still there (the map's size counts it, iteration shows it) but get, containsKey and remove can't find it: a memory leak and a correctness bug at once. Use immutable keys: String, Integer, records (Topic 4.9) and enums are ideal.

Try it yourself

1
Predict a bucket
In the first example, add the key "chai". Before running, compute its index: its hashCode is 3052365. Spreading XORs in 3052365 >>> 16 (46), and the bucket is the low four bits of the result (you should get 3). Then run and check.
2
Change the load factor
In the resize simulation, set loadFactor to 1.0f, then to 0.5f. Predict at which entries the resizes happen and the final capacity in each case. Which setting uses more memory for 100 entries?
3
Fix the key bugs
Make Badge immutable (a record: record Badge(String name) {}) and give Ticket a hashCode returning Integer.hashCode(id). Predict the new outputs. The mutation line won't compile any more, which is the point.

Code & diagrams

From key to bucket, step by step New tab

String.hashCode is part of the Java specification, so these numbers are the same on every JVM.

Expected output

apple  hashCode=93029210  spread=93030097  bucket=1
mango  hashCode=103662530 spread=103663087 bucket=15
tea    hashCode=114704    spread=114705    bucket=1
Aa     hashCode=2112      spread=2112      bucket=0
BB     hashCode=2112      spread=2112      bucket=0
Aa and BB collide: true
null key always goes to bucket 0

Why HashMap spreads the hash New tab

The mask only looks at the low bits. Spreading copies information from the high bits down so it isn't thrown away.

Expected output

without spreading: 1 bucket(s) used, biggest holds 16
with spreading:    16 buckets used, one key each

Simulate thresholds, resizes and the lo/hi split New tab

Expected output

entry 13: resize 16 -> 32
entry 25: resize 32 -> 64
entry 49: resize 64 -> 128
entry 97: resize 128 -> 256
final capacity 256, threshold 192
hash 5: old bucket 5 -> new bucket 5 (check: 5)
hash 21: old bucket 5 -> new bucket 21 (check: 21)
hash 37: old bucket 5 -> new bucket 5 (check: 5)
hash 53: old bucket 5 -> new bucket 21 (check: 21)

The two key bugs: mutable keys and equals without hashCode New tab

The badge's entry is still in the map but unreachable by lookup. In theory the Ticket keys could share a bucket by chance; with identity hash codes they practically never do.

Expected output

size: 1
get(same object): null
get(new Badge("asha")): null
tickets stored: 2
equal? true

The Java 8 Map methods that replace get-check-put Java 8+ New tab

Expected output

counts: {cake=2, chai=1, tea=3}
by length: {3=[tea, tea, tea], 4=[cake, chai, cake]}
getOrDefault("milk", 0): 0
putIfAbsent("tea", 99) returned 3
after computeIfPresent: {cake=2, tea=3}
put returns old value: 2

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Change a map while looping over it

Loop with for (String k : counts.keySet()) { if (counts.get(k) == 1) counts.remove(k); }.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.util.ConcurrentModificationException

at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1605)

at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1628)

at Main.main(Main.java:9)

Break #2

Unbox a missing value

With Map<String, Integer> stock, write int left = stock.get("milk"); when there is no milk entry.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

at Main.main(Main.java:7)

Myth vs fact

Myth

HashMap get is always O(1).

Fact

It's O(1) expected with a reasonable hashCode. With heavy collisions it's O(n) for list buckets, or O(log n) once a bucket is treeified (Java 8+), and for non-Comparable keys with identical hashes a tree bucket can still need a full search.

Myth

HashMap keeps insertion order.

Fact

It iterates in bucket order, which depends on hash codes and capacity and can change after a resize. Use LinkedHashMap for insertion order or TreeMap for sorted order.

Myth

new HashMap<>(100) can hold 100 entries without resizing.

Fact

It gets capacity 128 and threshold 96, so the 97th entry resizes it. Use HashMap.newHashMap(100) (Java 19) or a capacity of n / 0.75 + 1.

Myth

Buckets turn into trees whenever they have 8 entries.

Fact

Only when a bucket grows past 8 nodes and the table already has at least 64 buckets. In a smaller table the map resizes instead.

Interview problem

The problem

"Explain how HashMap works" (the classic interview question)

An interviewer asks: "How does HashMap work internally? What happens when two keys have the same hash code? What changed in Java 8? Is it thread-safe?" Give a complete, structured answer.

You're given

Cover storage, hashing, collisions, resizing and Java 8 changes.
Mention complexity and the key contract.
Finish with concurrency.

The interviewer follows up

Why does ConcurrentHashMap forbid null keys and values when HashMap allows them?

What happens if hashCode always returns 42?

Can two unequal objects have the same hashCode?

When it breaks

A shared HashMap written by several threads

What you see

Entries vanish, size() is wrong, iteration sees stale or missing data, and on Java 7 a concurrent resize could create a cycle that pins a CPU core at 100% inside HashMap.get forever (visible in a thread dump as a thread stuck in HashMap.getEntry).

Fix & prevent

Use ConcurrentHashMap for shared maps, or confine the map to one thread, or publish an immutable Map.copyOf snapshot. Take thread dumps (jcmd <pid> Thread.print) when a CPU is pinned.

A cache keyed by a mutable object

What you see

Lookups miss even though size() keeps growing; the cache's hit rate drops to near zero, memory climbs, and eventually OutOfMemoryError. The leaked entries show up in a heap dump as nodes in the "wrong" bucket.

Fix & prevent

Use immutable keys (records, String, IDs). If a key object must change, remove the entry first, change it, then put it back.

A key class with a terrible hashCode (constant, or using only one rarely varying field)

What you see

CPU usage rises sharply as the map grows, and profiling shows time in HashMap.getNode, putVal or TreeNode.find instead of business code.

Fix & prevent

Hash all the fields equals uses (Objects.hash, or a record's generated hashCode). If the key is under your control, implementing Comparable also makes treeified buckets O(log n).

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Before Java 8, HashMap inserted new nodes at the head of a bucket and the resize transfer reversed list order. Two threads resizing at once could link nodes into a cycle, and a later get would spin forever at 100% CPU. Java 8's tail insertion and lo/hi split removed that particular failure, but concurrent writes still lose entries or corrupt tree bins. HashMap is simply not for shared mutable use.
▸
Memory per entry: a HashMap.Node is 32 bytes with compressed references (12-byte header + int hash + key, value and next references), plus the table slot (4 bytes, with up to 25% to 50% of slots empty). A TreeNode is roughly twice that. For millions of small entries, consider primitive-specialised maps or sorted arrays.
▸
Object.hashCode without an override is an identity hash stored in the object header (on HotSpot, generated lazily and often thread-local random). Two new Ticket(7) objects therefore almost never share a bucket, which is why the missing-hashCode bug shows up as duplicate keys rather than an occasional miss.
▸
The iteration cost of a HashMap is O(capacity + size), not O(size): a map that once held a million entries and now holds ten still walks the big table. HashMap never shrinks; build a new map if that matters. LinkedHashMap iterates in O(size) because it follows its own linked list.

Remember this

1
Inside, a HashMap has an array Node<K,V>[] table, whose slots are called buckets. Each Node holds the key, the value, the key's cached hash, and next (a link to another node in the same bucket). The table length is always a power of two, 16 by default, and is allocated lazily on the first put.
2
To find a bucket, HashMap first calls key.hashCode(), then spreads it: h ^ (h >>> 16), which mixes the top 16 bits into the bottom 16. Then it computes the index as (n - 1) & hash, where n is the table length. Because n is a power of two, n - 1 is a mask of low bits (15 is 1111 in binary), so the & is a cheap replacement for hash % n. Without spreading, keys whose hash codes differ only in their high bits would all land in the same bucket.
3
Two different keys landing in the same bucket is a collision. put walks the bucket's nodes: if one has the same hash and an equal key (== or equals), its value is replaced; otherwise a new node is appended at the tail. get does the same walk and returns the value or null. This is why both hashCode and equals must be right (Topic 4.8): hashCode picks the bucket, equals picks the node.
4
Load factor (0.75 by default) controls when the table grows. The threshold is capacity × loadFactor: 12 for a 16-slot table. When size exceeds it, resize() doubles the table and moves every node. Because the length doubles, each node either stays at index j or moves to j + oldCapacity, decided by one bit (hash & oldCapacity), so Java 8 doesn't recompute any hash codes.
5
Since Java 8, a bucket whose list grows past 8 nodes (TREEIFY_THRESHOLD = 8) is converted into a red-black tree of TreeNodes, so a badly colliding bucket costs O(log n) instead of O(n). If the whole table is still smaller than 64 (MIN_TREEIFY_CAPACITY), it resizes instead, since a small table is the likelier cause. A tree shrinks back to a list at 6 nodes or fewer during a resize. With a decent hashCode, buckets almost never get that long.
6
The rules that follow: get, put, remove and containsKey are O(1) expected, containsValue is O(n). Iteration order is the bucket order, not insertion order, and it can change after a resize, so never rely on it (use LinkedHashMap or TreeMap, Topic 9.6). One null key is allowed (it hashes to 0) and null values too. Never mutate a key after putting it in a map. And HashMap isn't thread-safe: use ConcurrentHashMap (Topic 13.8). The DSA course's Hashing module (/dsa/hashing) shows the problems this O(1) lookup unlocks.

Explain it without notes

Walk through exactly what happens in map.put(key, value) on a Java 8+ HashMap.

Why is the table length always a power of two, and what does h ^ (h >>> 16) achieve?

What are load factor and threshold, and what does a resize do in Java 8?

What is treeification, when does it happen, and why was it added?

Why must keys implement hashCode consistently with equals, and why should they be immutable?

Practice

Implement a tiny IntMap (keys and values are int) using separate chaining: an array of 8 bucket lists, index Math.floorMod(key, buckets.length), and put/get that replace or append. Put keys 1, 9 and 17 (which collide) and 2, then print get(9), get(17), get(3) and the length of bucket 1.

Count how many times each character appears in "mississippi" using a HashMap<Character, Integer> and merge, then print it as a TreeMap.

Two-sum with a map: given int[] nums = {2, 7, 11, 15} and target 9, return the indexes of two numbers that add up to the target in one pass. Print them.

Trade-offs

↔
HashMap gives O(1) expected lookups but no order and no range queries. TreeMap gives sorted keys and range queries at O(log n) (Topic 9.6).
↔
A lower load factor means shorter chains and faster lookups but more empty slots; a higher one saves memory but lengthens chains. The default 0.75 is right for almost all code.
↔
Pre-sizing avoids repeated resizes for big maps, but over-sizing wastes memory and slows iteration (which walks every slot). Size for what you'll really store.

Done when you can

Done when you can explain hash, spread and (n - 1) & hash, and why the capacity is a power of two.
Done when you can walk through put and get, including collisions and replacement.
Done when you can compute when a map resizes from its capacity and load factor.
Done when you can explain the Java 8 lo/hi split and treeify rules (8, 6, 64).
Done when you never use mutable keys and always pair equals with hashCode.
Done when you use merge, computeIfAbsent and getOrDefault instead of get-check-put.

Command Palette

Words you'll meet

Step by step

01The table and its nodes

02From key to bucket: hash, spread, mask

03put: four cases

04Load factor, threshold and resize

05Pre-sizing: the capacity you pass isn't the size you get

06Treeify: the Java 8 defence against bad hashing

07The two deadly key mistakes

Try it yourself

Predict a bucket

Change the load factor

Fix the key bugs

Code & diagrams

Break it on purpose

Change a map while looping over it

Unbox a missing value

Myth vs fact

Interview problem

"Explain how HashMap works" (the classic interview question)

When it breaks

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can