skip to content

What changed in Java 8's HashMap internals, and how did HashMap behave before that release?

level: middleimportance: should knowfreq 68%

answer

  1. collisions, resizing and hashing all moved
  2. worst case of one crowded bucket
  3. head versus tail of a chain
  4. low and high lists, the oldCap bit
  5. why one XOR became enough

basics

~20 s

Java 8 added tree bins: a crowded bucket becomes a red-black tree. put appends at a plain bin's tail, resize splits bins in order, and hash mixing is one XOR. Before, buckets stayed linked lists, O(n) under heavy collisions.

solid answer

~50 s

The headline, from JEP 180, is **tree bins**: a crowded bin converts from a linked list to a red-black tree, once the table has at least 64 slots, taking the worst case from O(n) to O(log n) when keys have distinct hashes or their class itself declares `Comparable` of itself. `put` now appends at a plain bin's tail, and `resize()` splits each bin on the `oldCap` bit into low and high lists that keep their order; JDK 7's update line linked new entries at a bin's head and, on resize, re-linked entries one by one at a head. `hash()` shrank from a multi-shift mix to `h ^ (h >>> 16)`, partly because trees now handle heavy collisions, and the alternative `String` hash from Java 7u6 went away. The guarantees did not move: iteration order stays unspecified, and concurrent access with a structural writer still needs external synchronization.

code

java · 22 lines
java
import java.util.HashMap;
import java.util.Map;

public class BinOrder {
    // Every key lands in one bin, so iteration shows that bin's chain.
    record Key(String name) {
        @Override
        public int hashCode() {
            return 1;
        }
    }

    public static void main(String[] args) {
        Map<Key, Integer> map = new HashMap<>();
        for (String name : new String[] {"a", "b", "c"}) {
            map.put(new Key(name), 0);
        }
        System.out.println(map.keySet());
        map.computeIfAbsent(new Key("d"), k -> 0);
        System.out.println(map.keySet());
    }
}

go deeper

for a junior

Recall the headline: since Java 8 a crowded HashMap bucket can become a red-black tree instead of staying a linked list. Iteration order and thread safety did not improve.

for a middle

Explain each mechanism: what makes a bin treeify, how put appends to a plain bin, how resize splits a bin on the oldCap bit, and why a single XOR became enough for hash spreading.

for a senior

Show the production reading: tree bins soften a poor hashCode without curing it. Keys with equal hashes and no usable Comparable ordering still search about half a bin on a hit and all of it on a miss, so fix the hash and consider ordering.

for a principal

Weigh the trade the JDK made: a change planned as implementation-only, yet iteration order shifted and code relying on it had to be fixed. Use it to argue how firmly a team should ban reliance on unspecified behaviour.

## What changed, at a glance A `HashMap` keeps its entries in an array of **bins**, also called buckets. A key's hash picks the bin, and keys that land in the same bin are a **collision**. Java 8 reworked how a bin stores collisions and how bins move when the table grows. Nearly all of it sits below the contract: JEP 180 planned that "no interfaces or specifications will be modified" for the tree-bin part, and the class comment gained a note that comparison order may help break ties. The code quoted here is JDK 27, and these paths read the same at JDK 25. | Aspect | JDK 7's update line | Since Java 8 | |---|---|---| | Crowded bin | Linked list, O(n) to search | Red-black tree past a threshold | | New key through `put` | Linked at the bin's head | Appended at a plain bin's tail | | Resize | Each entry re-indexed, then linked at a bin's head | Bin split into two lists, order kept | | Hash mixing | Several shifts and XORs | One shift, one XOR | | `String` collisions | Optional alternative hash, from 7u6 | Alternative hash removed | ## Tree bins: the change JEP 180 is about Before Java 8 a bin was always a linked list, so many colliding keys turned a lookup into a walk along a chain, which is O(n). JEP 180 switches a bin to a balanced tree once it grows past a threshold, improving the worst case to O(log n). In the source, the nodes are `TreeNode`, a package-private class holding red-black links, and the package-private `treeifyBin` does the conversion. It runs when `put` adds to a bin already holding `TREEIFY_THRESHOLD` (8) nodes, and on a table smaller than `MIN_TREEIFY_CAPACITY` (64) it resizes instead. - **The O(log n) has a condition.** A tree bin orders by hash first and, on a tie, by `compareTo` when the key's class itself declares `Comparable` of itself; a subclass that only inherits it does not qualify. The source promises worst-case O(log n) "when keys either have distinct hashes or are orderable". With equal hashes and no ordering, `TreeNode.find` searches both subtrees: on JDK 27, 4,096 keys sharing one hash average about 2,049 `equals` calls per `get`, against 12 when the class declares `Comparable` of itself. - **Trees are the exception.** A `TreeNode` is about twice the size of a plain node, and the source's Poisson estimate for random hash codes gives a list of length 8 a frequency of 0.00000006. The tree is insurance against poor or malicious hashing. - **Scope.** The same work covers `LinkedHashMap`, whose iteration order JEP 180 keeps, and reuses code from the JDK 8 version of `ConcurrentHashMap`. The JEP leaves out `Hashtable`, whose iteration order legacy code depends on, and `WeakHashMap`, where weak keys cost too much in microbenchmarks. ## Insertion and resize `putVal`, the package-private method behind `put`, walks a plain chain looking for an existing key and, at the end, runs `p.next = newNode(hash, key, value, null)`. JDK 7's update line linked a new entry at the head. Tail insertion is not universal: for a plain bin, `computeIfAbsent`, `compute` and `merge` still prepend, through `tab[i] = newNode(hash, key, v, first)` or the same line with `value`, at JDK 27 and 25 alike. `resize()` doubles the table. Because capacity is a power of two, doubling adds one bit to the index mask, so for a plain bin one test splits it: - `(e.hash & oldCap) == 0`: the entry joins the **low** list and stays at index `j`. - Otherwise it joins the **high** list and moves to `j + oldCap`. - Each list is built at its tail, so relative order holds; the source marks this branch `// preserve order`. - Only the stored `Node.hash` is read, so no key's `hashCode()` runs. Going from 16 to 32, hashes 1, 17, 33 and 49 all start in bin 1. Bin 1 keeps 1 and 33, and bin 17 receives 17 and 49. Tree bins get the same split through `TreeNode.split`, turning back into a plain list when a side has `UNTREEIFY_THRESHOLD` (6) or fewer nodes. JDK 7's update line computed each entry's new index in turn and linked it at the head of its target bin, which reversed entries that stayed together. `WeakHashMap`, which JEP 180 reverted to its prior state, works that way at JDK 27: its private `transfer` runs `e.next = dest[i]; dest[i] = e;`. ## Hash mixing The package-private `hash()` is now `(h = key.hashCode()) ^ (h >>> 16)`. Its comment gives the reason for the brevity: many sets of hashes are already well distributed, and "we use trees to handle large sets of collisions in bins", so it XORs in the "cheapest possible way". The XOR still matters, because the table index uses only low bits. JDK 7's update line mixed harder, with several shifts; `WeakHashMap`'s `hash` shows that style today, `h ^= (h >>> 20) ^ (h >>> 12)` followed by `h ^ (h >>> 7) ^ (h >>> 4)`. Java SE 7u6 had also added an alternative hash function for `String` keys, off by default and enabled through the `jdk.map.althashing.threshold` system property. Java 8 removed the function and the property in favour of tree bins. ## What did not change - **Iteration order stays unspecified.** JEP 180 warned the work would likely alter it, and the Java 8 notes say code depending on it "should be fixed". - **Thread safety did not arrive.** The class comment still says that if several threads access a map concurrently and at least one modifies it structurally, it "must be synchronized externally". An order-preserving resize is not a concurrency fix; those hazards and the alternatives are covered with `ConcurrentHashMap`.

  • Why can the test (e.hash & oldCap) decide an entry's new HashMap bin without computing a full index?
    Capacity is a power of two, so doubling adds exactly one bit, oldCap, to the index mask. If that bit of the stored hash is 0, the index is unchanged. If it is 1, the index grows by oldCap. That lets one pass split a bin into two lists that keep their relative order.
  • If tree bins handle heavy collisions, why does HashMap's hash() still XOR the high bits down at all?
    The index uses only the low bits, so hashes differing only above the mask would always collide. The source's example is Float keys holding consecutive whole numbers in small tables. One XOR is the cheapest way to reduce that and to let the highest bits influence the index.
  • With well-distributed hash codes, how often does a HashMap actually use tree bins?
    Rarely. The source's Poisson estimate under random hash codes and the default load factor gives a list of length 8 a frequency of 0.00000006. Tree nodes are about twice the size of plain ones, so they appear only when a bin warrants them. They mainly protect against poorly distributed or malicious hash codes.

  • Tree bins guarantee O(log n) lookups for any keys, even equal hashes with no Comparable ordering.
  • Java 8's order-preserving resize made HashMap safe for concurrent writers.
  • Every insertion path now appends at the tail, including computeIfAbsent, compute and merge.
  • Since Java 8 a HashMap's iteration order is stable enough to rely on.
  • A resize calls hashCode() again on every key to find its new bin.
  • JEP 180 put tree bins into every hash map, including Hashtable and WeakHashMap.

HashMap balanced-tree bins
Java 1.8
HashMap alternative String hash
Java 1.7removed 1.8

Assumes JDK 27 for the quoted code; tree bins shipped in Java 8 per JEP 180, and these HashMap paths read the same at JDK 25.

context