Hashing, collisions, treeification and load factor

For this lesson, we'll focus on the senior-level internals: why collisions are unavoidable, why HashMap uses load factor 0.75, how resize doubles the table without calling hashCode() again, when a bin treeifies, how TreeNode ordering works, why this changed after hash-flooding attacks, and how to choose initial capacity. We covered the basic put and get path in How HashMap works; here we go deeper.

01Picture it first: sorting mail after a building expansion

Imagine a mailroom with 16 shelves. When the building doubles the shelf wall to 32 shelves, the clerk does not reread every envelope's full address. For each old shelf, one extra address bit decides whether the envelope stays on shelf j or moves to shelf j + 16.

That's the core trick. Doubling adds one mask bit, so every node in an old bucket has only two possible destinations.

Fig. 1

A HashMap resize from 16 to 32 buckets splits old bucket 5 into a lo list that stays at 5 and a hi list that moves to 21 using the bit tested by hash and oldCap

Notice what does not happen. hashCode() is not called again during resize. Each node already stores the spread hash, so the map tests one bit, relinks nodes into two lists, and installs them in the new table.

02Collisions: unavoidable, harmless until they concentrate

Collisions are not a bug by themselves. A 32-bit hash has about 4.29 billion possible values, and the table usually has far fewer buckets than that. The pigeonhole principle says different keys must eventually share a hash value or a bucket.

The real question is distribution. If hashes spread evenly, each bucket stays short and lookup is near O(1). If many keys share low bits, or worse, share the same hash, one bucket gets a long line.

final class BadKey {
    private final int id;

    BadKey(int id) { this.id = id; }

    @Override public boolean equals(Object o) {
        return o instanceof BadKey other && id == other.id;
    }

    @Override public int hashCode() {
        return 1;                      // every key collides
    }
}

Map<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 10; i++) {
    map.put(new BadKey(i), "order-" + i);
}

System.out.println(map.size());         // 10
System.out.println(map.get(new BadKey(7))); // order-7

The map still works because equals separates the keys inside the bucket. But the performance shape is terrible: all ten entries start in one bin. Below 64 buckets, Java prefers to resize; at 64 or more, a bin that grows past 8 nodes can treeify.

String is the common good example. Its hash is specified as:

int h = 0;
for (int i = 0; i < s.length(); i++) {
    h = 31 * h + s.charAt(i);
}

The multiplier 31 is a small odd prime, and the formula is stable across JVMs because String.hashCode() is part of the API contract. Stable does not mean collision-free. Classic pairs such as "Aa" and "BB" collide, which is useful for tests, but normal English-like strings distribute well enough for everyday maps.

03Load factor and threshold: when HashMap resizes

Load factor is the fullness limit of the table. The default 0.75 means resize after the map holds more than 75% as many entries as buckets. With capacity 16, threshold is 16 * 0.75 = 12; the 13th new mapping triggers a resize.

Why 0.75? It is a pragmatic trade-off. Lower values use more memory and fewer collisions. Higher values save table slots but make bins longer and resizes later. Java's default is a good balance for general-purpose server code, and I almost never change it.

int expected = 1_000;
int needed = (int) (expected / 0.75f) + 1; // 1334

Map<String, Integer> oldStyle = new HashMap<>(needed); // rounded up to 2048 buckets
Map<String, Integer> newStyle = HashMap.newHashMap(expected); // Java 19+

The capacity must be a power of two, so 1334 rounds up to 2048. That gives threshold 2048 * 0.75 = 1536, enough room for 1,000 mappings. Passing new HashMap<>(1_000) is the common mistake: 1,000 rounds to 1,024, threshold 768, and the map resizes before you reach 1,000 entries.

04Resize under the hood: lo and hi lists

Resize is where a lot of memorised answers fall apart. Older explanations say HashMap rehashes everything. Java 8+ does not call every key's hashCode() again. It reuses the cached spread hash in each node.

Here is the reason. Old capacity is a power of two, say 16. Old mask is 0b01111; new capacity is 32 and new mask is 0b11111. The new mask adds exactly one bit, the bit whose value is oldCap.

int oldCap = 16;
int oldIndex = hash & (oldCap - 1);
int newIndex = hash & ((oldCap * 2) - 1);

// During resize:
// if ((hash & oldCap) == 0) newIndex == oldIndex
// else newIndex == oldIndex + oldCap

So a bucket at index 5 can only split to index 5 or index 21. The JDK walks the old bin once and builds two chains: loHead/loTail for nodes where (hash & oldCap) == 0, and hiHead/hiTail for nodes where it is non-zero. Then it writes the two heads into the new table.

This matters for performance and correctness. Performance improves because no user code runs during resize. Correctness improves because Java 8 also preserves relative order inside each half and appends nodes, avoiding the old Java 7 head-insertion resize pattern that could form cyclic lists under unsynchronized concurrent mutation.