HashMap, line by line

the picture

the HashMap chapter has the friendly version: buckets, collisions, a load factor. this one reads the source. if you've ever been asked "why is the capacity a power of two?" in an interview, everything you need is in about 40 lines of it.

think of a coat check with numbered hooks (the table). your ticket number decides the hook (the hash picks the bin). two coats on one hook get stacked (a chain). when the room gets busy, the staff build a second row of hooks and move each coat at most once, to a hook they can work out from the ticket alone (resize).

table

Node<K,V>[]. null until the first put (it's allocated lazily, inside resize()). length is always a power of two, default 16.

Node

four fields: final int hash, final K key, V value, Node next. 32 bytes each on jdk 25 with default flags (we measured it with a class histogram).

threshold

capacity × loadFactor. default 16 × 0.75 = 12. the put that makes size exceed it triggers a resize.

modCount

bumped on every structural change. iterators compare it to fail fast (see fail-fast).

notice the node keeps its hash. it's computed once, on the way in, and never again. that detail pays off twice later: lookups compare the cached int before ever calling equals, and resizing never calls hashCode().

hash(): folding the top half down

the whole method is one line:

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

why bother? because of how the bin is picked. a 16-bin table looks at the low 4 bits of the hash and nothing else. if your keys only differ above bit 4 (and plenty do: whole-number Float keys, ids that are multiples of 65,536, a lazy hashCode()), they all land in the same bin. h >>> 16 slides the top half down, and XOR mixes it into the bits the mask will actually read.

same thing, in code you can run:

void main() {
    for (int i = 0; i < 4; i++) {
        int h = Integer.valueOf(i << 16).hashCode();
        int spread = h ^ (h >>> 16);
        IO.println(h + ": bin " + (h & 15) + " without spreading, bin " + (spread & 15) + " with");
    }
}

0: bin 0 without spreading, bin 0 with
65536: bin 0 without spreading, bin 1 with
131072: bin 0 without spreading, bin 2 with
196608: bin 0 without spreading, bin 3 with

the comment above hash() is honest about the tradeoff: it's the cheapest mix that fixes the common systematic cases, and anything nastier is left for the trees (below) to absorb. one shift, one XOR. it runs on every get and put, so cheap wins.

(n - 1) & hash, and why the length is a power of two

when n is a power of two, n - 1 is a run of ones: 16 → 1111, 64 → 111111. so hash & (n - 1) keeps exactly the low bits, which is the same as hash % n for a non-negative hash, without a division. and unlike %, it never goes negative (-7 % 16 is -7; -7 & 15 is 9), so there's no Math.abs bug waiting to happen.

that's the deal: a power-of-two length makes indexing a single AND, and (we'll see in a second) it makes resizing almost free. the price is that only the low bits matter, which is why hash() exists.

so what if you ask for a capacity that isn't a power of two? tableSizeFor rounds up, with a bit trick instead of a loop:

var map = new HashMap<Integer, Integer>(100);
for (int i = 0; i < 100; i++) map.put(i, i);
// how long is map's table now?

put, one branch at a time

putVal is about 40 lines and every one of them shows up in an interview somewhere. here's the path a key takes:

null keys are allowed, and they really do go to bin 0 (unlike ConcurrentHashMap, which bans them):

void main() {
    var m = new HashMap<String, Integer>();
    m.put(null, 1);
    m.put(null, 2);
    IO.println(m + " " + m.get(null) + " " + m.size());
    IO.println("Aa".hashCode() + " " + "BB".hashCode());
}

{null=2} 2 1
2112 2112

resize: every chain splits by one bit

here's the payoff of power-of-two lengths. going from 16 to 32 bins, the mask grows by exactly one bit, bit 4 (value 16, the old capacity). a node's new index is its old index plus either 0 or 16, depending on that one bit. so resize() doesn't rehash anything. it walks each old chain once and deals the nodes into two lists: (e.hash & oldCap) == 0 stays at j (lo), the rest go to j + oldCap (hi).

this is also why HashMap iteration order is "whatever the bins say", and why it changes when the map grows:

var m = new HashMap<Integer, String>();
m.put(17, "a");
m.put(1, "b");
IO.println(m.keySet());
for (int i = 100; i < 111; i++) m.put(i, "x"); // 13 entries: resize to 32
m.keySet().removeIf(k -> k >= 100);
IO.println(m.keySet());

treeification: when a chain turns into a tree

three constants control it, all in the source:

the middle one is the bit people miss. a crowded bin in a small table is more likely a "the table is too small" problem than a "these keys really collide" problem, so HashMap tries growing first. drag through it with keys that all return the same hashCode():

we didn't make those numbers up. reflection into a live map (this needs --add-opens, so it's a terminal run rather than a run button):

import java.lang.reflect.Field;
import java.util.HashMap;
 
public class Treeify {
    record Key(int id) implements Comparable<Key> {
        public int hashCode() { return 42; } // every key collides
        public int compareTo(Key o) { return Integer.compare(id, o.id); }
    }
 
    public static void main(String[] args) throws Exception {
        Field table = HashMap.class.getDeclaredField("table");
        table.setAccessible(true);
        var map = new HashMap<Key, Integer>();
        for (int i = 1; i <= 11; i++) {
            map.put(new Key(i), i);
            Object[] t = (Object[]) table.get(map);
            Object bin = t[42 & (t.length - 1)];
            System.out.println(i + " keys: Node[" + t.length + "], bin is a " + bin.getClass().getSimpleName());
        }
    }
}

$ java --add-opens java.base/java.util=ALL-UNNAMED Treeify.java
1 keys: Node[16], bin is a Node
...
8 keys: Node[16], bin is a Node
9 keys: Node[32], bin is a Node
10 keys: Node[64], bin is a Node
11 keys: Node[64], bin is a TreeNode

a TreeNode is 56 bytes against a Node's 32 (it extends LinkedHashMap.Entry and adds parent, left, right, prev and a red flag). that's why trees are the fallback, not the default. the comment in HashMap.java works out the odds: with random hashes and the default load factor, bin sizes follow a Poisson distribution with a mean of about 0.5, and the chance of a bin reaching 8 is about 6 in 100 million. if you see tree bins in a heap dump, some hashCode() is broken or someone is attacking you on purpose (hash flooding, where an attacker sends keys chosen to collide). the trees arrived in java 8 (JEP 180) so that a pile of colliding keys degrades to O(log n) instead of a list walk.

why 8 to treeify but 6 to untreeify? hysteresis. if both were 8, a bin hovering around 8 entries would flip between list and tree on every other operation. the gap of 2 means it has to shrink for real before converting back. (removing from a tree bin uses a shape check instead of a count: when the root has no left or right child, or the left child has no left child, the bin goes back to a list. that's somewhere between 2 and 6 nodes.)