HashMap internals

HashMap is the most used data structure in Java and the one interviewers most want you to open up. It is also the one where a bad hashCode turns O(1) into O(n) without any error, and where "iteration order" is a property people rely on that was never promised. This is how it works, in enough detail to predict its behaviour, its memory, and what a resize actually moves.

#Buckets

A HashMap holds an array of buckets — Node<K,V>[] table — whose length is always a power of two. To store a key:

1. Compute h = key.hashCode().
2. Spread it: h ^ (h >>> 16). The high bits are folded into the low bits, because step 3 only uses the low bits and many hashCode implementations vary mostly in the high ones.
3. Pick the bucket: index = h & (table.length - 1). With a power-of-two length, this is the low bits of the hash — a mask, not a modulo.
4. Walk the bucket. If a node has an equal hash and an equals key, replace its value. Otherwise append a node.

get does the same walk and returns the value or null. A null key is allowed (bucket 0); null values are allowed too, which is why get returning null does not mean "absent" — use containsKey or getOrDefault.

#Under the hood: what an entry costs, and what a resize moves

Each entry is a Node: 12-byte header, int hash, K key, V value, Node next: 32 bytes with compressed references. The table slot that points at it is another 4 bytes, and at the default load factor there are 1.33 slots per entry, so the map's own overhead is about 37 bytes per entry before the key and value objects. A HashMap<Long, Long> with ten million entries is 370 MB of map, plus 480 MB of boxed Longs: about 850 MB to store 160 MB of numbers. Measured on a real JVM at 2 million entries, a pre-sized HashMap<Long,Long> costs 88.4 bytes per entry. The stored hash field is what lets a lookup skip equals on most chain nodes, and what lets a resize avoid calling hashCode() again.

A resize doubles the table and re-buckets every node, but it does not rehash. Because the new length has one more bit, a node's new index is either its old index or old index + old length, decided by one bit of its stored hash. Each bucket is split into a "low" and a "high" list in one pass, preserving relative order. It is still O(n) and still happens at 12, 24, 48, 96 entries for the default 16-slot table, which is why a map you know will hold 10,000 entries should be created with HashMap.newHashMap(10_000) (Java 19+; it sizes the table as n / 0.75 + 1) and skip ten resizes.

#Load factor and resize

size / table.length is the load. When it exceeds the load factor (default 0.75), the table doubles and every entry is re-bucketed as above. Lower the factor and chains get shorter at the cost of a sparser table; raise it and the reverse. 0.75 is the measured sweet spot between memory and probe length for a well-distributed hash, and almost nobody should change it.

#Collisions and treeification

Two keys in one bucket is a collision; the bucket becomes a linked chain and lookup walks it. With a good hash and load ≤ 0.75, chains are short — the average is under one. With a bad hash — every key returning the same value — every entry lands in one bucket and every operation is O(n).

Since Java 8, a chain longer than 8 entries in a table of at least 64 buckets is converted to a red-black tree of TreeNodes (56 bytes each, with parent, left, right, prev and a colour), making the worst case O(log n) instead of O(n). The tree orders by hash first, then by compareTo if the keys are Comparable, then by class name and System.identityHashCode as a last resort, so it works for any key but is only useful against collisions when keys can be compared. It exists as protection against hash-collision denial of service — the 2011 attacks that sent thousands of colliding form-field names to web servers — not as an excuse for a bad hashCode. A bucket shrinks back to a list at 6.

#What a bad hashCode does

class Point {
    int x, y;
    @Override public boolean equals(Object o) { ... }
    @Override public int hashCode() { return 1; }     // legal, catastrophic
}

Legal — equal objects have equal hashes — and every point goes in bucket 1. A map of 100,000 points takes 100,000 comparisons per lookup, or, since Point is not Comparable, a tree ordered by identity hash that helps insertion and not lookup. Objects.hash(x, y) or 31 * x + y distributes them. The 31 is a small odd prime: multiplying by it mixes bits cheaply and the JIT turns it into a shift and a subtract.

String.hashCode with the spread distributes these keys across the table; return 42 — the Point above — puts every one of them in a single bucket, so every lookup walks all of them. That is the lesson's claim about O(1) and O(n), and it is a difference you can count.

And the same map being filled, one key at a time, with that same return 42:

Press Play. Every key lands in the same bucket, and the chain grows by one each time — which is what "O(n) lookup" looks like while it is happening rather than after.

#Walkthrough: the map that ate the heap

A service kept Map<Long, Long> lastSeen from user id to timestamp, ten million users, and ran out of a 2 GB heap. The heap dump said 61% HashMap$Node, 29% java.lang.Long. The arithmetic, which the team could have done before the dump:

1. Ten million Nodes at 32 bytes: 320 MB. The table, at 16 million slots after the last doubling (10M / 0.75 rounds up to a power of two): 64 MB.
2. Ten million boxed Long keys and ten million boxed Long values at 24 bytes each — a Long is a 12-byte header plus an 8-byte value, padded — 480 MB, none of them in the Long cache.
3. Total about 850 MB for 160 MB of actual data, and the resize from 8 million to 16 million slots needed both tables alive at once, which is the moment the OOM fired.
4. Options, in order: a primitive-keyed map (fastutil's Long2LongOpenHashMap, about 24 bytes per entry, open addressing, no nodes); two sorted long[] arrays with binary search if the set is loaded once; or, if the data is really a per-user column, the database. The HashMap was the right structure for the access pattern and the wrong one for the volume.

The general rule: a HashMap costs roughly 40 bytes per entry plus its boxed keys and values. Below a million entries nobody notices. Above ten million, count before you allocate.

#Iteration order is not a contract

HashMap iterates bucket by bucket. The order depends on hash values and table size, so it changes when the map resizes and differs between JVM versions (the spread function changed in Java 8). Code that depends on it is code that breaks on a deploy. If order matters:

• Insertion order: LinkedHashMap, which threads a doubly linked list through the entries (two more references per node, 40 bytes).
• Sorted by key: TreeMap.
• Most recently used first: new LinkedHashMap<>(16, 0.75f, true) and override removeEldestEntry — a fifteen-line LRU cache.

#Mutable keys

A key's bucket is chosen from its hash at insertion. Mutate the key so its hash changes, and get looks in the new hash's bucket, finds nothing, and the entry is unreachable — still counted in size(), still iterated, never found by key. Keys must be immutable, or at least their hashed fields must be. Strings, records, boxed primitives, java.time types: fine. Entities with a mutable id: not fine.

#Compound operations are not atomic

if (!map.containsKey(k)) map.put(k, v);        // two operations; a race in a shared map
map.putIfAbsent(k, v);                          // one operation
map.computeIfAbsent(k, key -> expensive(key)); // one operation, lazy

Even single-threaded, computeIfAbsent, merge and compute are the clearer API. Multi-threaded, a plain HashMap is unsafe in every way — concurrent puts during a resize could, before Java 8, link a bucket into a cycle and spin a thread at 100% CPU forever, and today they lose entries silently. Use ConcurrentHashMap, whose computeIfAbsent is atomic per key.

#Try it yourself

#Misconceptions

• "A resize rehashes every key." It re-buckets by one bit of the stored hash; hashCode() is not called. That is why the hash is stored in the node.
• "Treeification fixes a bad hashCode." It caps the worst case at O(log n) for Comparable keys and costs 24 bytes more per node. A good hash is O(1) and 32 bytes.
• "HashMap is a few bytes per entry." About 37 of its own, plus the boxed keys and values. Ten million entries is hundreds of megabytes.
• "Iteration order is stable if I never resize." It is unspecified, differs between Java versions, and is the wrong thing to rely on even when it happens to hold.
• "Concurrent access just loses a few updates." Before Java 8 it could form a cycle and hang a thread; today it loses entries and can throw during a resize. It is not "mostly fine".

#Going deeper

• java.util.HashMap source, the class comment ("Implementation notes") and resize(), which the diagram above draws.
• HashMap.TreeNode and treeifyBin, for the tie-break order when keys are not Comparable.
• The 2011 "Effective DoS attacks against web application platforms" talk (Klink and Wälde), the origin of hash-flooding defences.
• jol on a HashMap with a few entries, and HashMap.newHashMap Javadoc for the sizing formula.
• fastutil's Long2LongOpenHashMap documentation, for what a primitive open-addressing map costs instead.