If Java 8 treeifies long bins, is a bad hashCode still O(n)?

The Answer

• Hashing is O(1) on the assumption that keys spread across bins. Break the assumption and you get the cost of whatever the bin is made of.
• Since Java 8 a bin with ≥ 8 nodes turns into a red-black tree, once the table has ≥ 64 slots. That is the mitigation everyone quotes.
• It only works if the keys are Comparable. A tree needs an ordering. Equal hash codes supply none, so for non-Comparable keys HashMap cannot order the nodes and the search degenerates to scanning both subtrees.
• Measured on 4,000 keys with a constant hashCode: 8,005,999 comparisons for 4,000 lookups, against 49,585 when the only change is implementing Comparable. 161× at that size, and the gap widens with n.
• So "Java 8 fixed bad hash codes" is half true. It fixed them for String, the boxed primitives, and anything else that happens to be Comparable.
• The real fix is still a hash that spreads. Treeify is a floor, not a plan.

Understand It

What O(1) is actually promising

A hash table's constant-time claim is conditional, and the condition is worth stating out loud: the keys are distributed roughly evenly across the bins. Under that assumption each bin holds about n / capacity entries, the table grows to keep that near 1, and a lookup is one hash, one array index, and one or two comparisons.

None of that is a property of hashing. It is a property of your hashCode. Return a constant and every key lands in one bin, which means a lookup has to examine every entry — and the table resizing does not help, because resizing redistributes by hash and all the hashes are identical.

Treeify, and the condition nobody mentions

System.out.println("       constant hash        constant hash");
System.out.println("   n   not Comparable       + Comparable      ratio");
for (int n : new int[] {1000, 2000, 4000}) {
    long plain = lookupCost(n, Collide::new);
    long ordered = lookupCost(n, CollideOrdered::new);
    System.out.printf("%5d   %,12d   %,15d   %6.0fx%n",
        n, plain, ordered, (double) plain / ordered);
}

       constant hash        constant hash
   n   not Comparable       + Comparable      ratio
 1000        501,499            10,405       48x
 2000      2,002,999            22,799       88x
 4000      8,005,999            49,585      161x

Read the growth, not the absolute numbers. Doubling n quadruples the non-Comparable column — 0.5M, 2M, 8M — which is O(n²) across n lookups, so O(n) each. The Comparable column roughly doubles, which is O(n log n) total and O(log n) each.

Both columns use a hashCode that returns 1. The only difference between the two key classes is four lines implementing compareTo.

The mechanism is in HashMap.TreeNode. When a bin treeifies, the tree is ordered primarily by hash. With identical hashes it needs a tiebreaker, and it looks for one via comparableClassFor — if the key implements Comparable against its own type, compareTo orders the nodes and find can discard half the tree at each step. If it does not, HashMap falls back to an arbitrary but consistent tieBreakOrder for insertion, which keeps the tree balanced but gives a search nothing to navigate by — so find recurses into both subtrees. Balanced shape, linear search.

The comparison that matters for real code

Most keys people actually use are Comparable already — String, Integer, Long, UUID, enums. So in practice treeify does help, and that is why the simplified version of the story survives. It stops being true the moment someone writes a key class:

for (int n : new int[] {4000}) {
    System.out.printf("spread hash        : %,d comparisons for %,d lookups%n",
        lookupCost(n, Spread::new), n);
    System.out.printf("constant hash      : %,d%n", lookupCost(n, Collide::new));
    System.out.printf("constant+Comparable: %,d%n", lookupCost(n, CollideOrdered::new));
}

spread hash        : 4,000 comparisons for 4,000 lookups
constant hash      : 8,005,999
constant+Comparable: 49,585

One comparison per lookup when the hash spreads. Two thousand times that when it does not, even with the tree. Treeify turns a catastrophe into a bad day; it does not make a broken hash acceptable.

The other way a hash table loses an entry

A degraded hash is slow. A changing hash is worse — it loses data, silently:

Map<List<String>, String> map = new HashMap<>();
List<String> key = new ArrayList<>(List.of("a"));
map.put(key, "value");

System.out.println("before mutation, get       : " + map.get(key));
key.add("b");
System.out.println("after  mutation, get       : " + map.get(key));
System.out.println("after  mutation, containsKey: " + map.containsKey(key));
System.out.println("the entry is still in there : size=" + map.size()
    + ", value=" + map.entrySet().iterator().next().getValue());

before mutation, get       : value
after  mutation, get       : null
after  mutation, containsKey: false
the entry is still in there : size=1, value=value

The entry was filed under the old hash. Changing the key changed which bin it should be in, so the lookup goes to the new bin and finds nothing — while the entry sits in the old one, reachable by iteration and by nothing else. It is not garbage, it is not an error, and size() still counts it.

This is why a hash key must be effectively immutable for as long as the map holds it, and why a mutable collection is a bad key even though List implements hashCode correctly.

Reference

Writing a key that behaves:

// Best: a record. equals and hashCode are generated from the components,
// the fields are final, and the two can never drift apart.
record OrderKey(String customerId, int lineNumber) {}

// By hand, if you must: every field in equals must be in hashCode.
final class OrderKey {
    private final String customerId;
    private final int lineNumber;

    @Override public boolean equals(Object o) {
        if (this == o) return true;
        return o instanceof OrderKey k
            && lineNumber == k.lineNumber
            && customerId.equals(k.customerId);
    }
    @Override public int hashCode() {
        return Objects.hash(customerId, lineNumber);   // same fields, same order
    }
}

What each choice costs:

Rules that follow from the measurements:

• Never return a constant, and do not hand-roll a hash by adding fields: a + b collides for every pair with the same sum. Objects.hash(a, b) uses 31 * h + field, which does not.
• If a key class is yours and might collide, implement Comparable. It costs four lines and is the difference between O(log n) and O(n) in the worst case.
• Keys must be effectively immutable while the map holds them. Prefer records or final fields; never a List, Set or mutable DTO.
• hashCode must use a subset of the fields equals uses — ideally exactly the same ones.

Scenarios

A cache keyed by a mutable entity. Someone uses the JPA entity as a map key. It has a generated equals/hashCode over all fields, including ones a setter changes. The first time anything mutates the entity while it is in the cache, that cache entry becomes unreachable and the memory is never reclaimed because the map still references it. A slow leak whose cause is three layers away from the symptom.

HashDoS. If keys come from user input and the hash is predictable, an attacker sends thousands of colliding keys and turns every lookup into a scan. This is why String.hashCode's weakness was a real CVE class across many languages, and part of why treeify was added at all — it caps the damage at O(log n). For String, which is Comparable, the cap actually applies.

A key that is a record of two ints, and a suspiciously slow report. Records generate a good hash, so suspect the map, not the key: a TreeMap where a HashMap was intended is O(log n) by design, and at a few million lookups that difference is visible without anything being wrong.

Deliberately colliding for a test. A constant hashCode is the standard way to force collisions and test bin behaviour. Worth knowing that such a test exercises the non-Comparable path unless the test key implements Comparable — so a test written this way is testing the slow path, which is usually what you wanted.

Interviewer's Next Move

1. "Java 8 treeifies bins, so is a bad hashCode fixed?" Only for Comparable keys. The tree is ordered by hash first, and identical hashes leave it with no ordering unless compareTo supplies one — so a non-Comparable key's treeified bin is balanced but searched linearly. Measured, that is 8 million comparisons against 50 thousand on 4,000 keys.

2. "What are the two thresholds, and why are there two?" Eight nodes in a bin, and a table of at least 64 slots. Below 64 slots a long bin more likely means the table is too small than that the hash is bad, so HashMap resizes instead — redistributing is cheaper and fixes the real cause. Treeifying a tiny table would pay for a tree structure that a resize would have emptied.

3. "Why is a mutated key worse than a slow one?" Because it is silent. The entry stays in the bin chosen by its old hash, so get and containsKey both miss while size() still counts it and iteration still yields it. No exception, no log line, and a map that disagrees with itself.

4. "Is Objects.hash(a, b) better than a.hashCode() + b.hashCode()?" Yes, because addition is commutative and collides on every pair with the same sum — (1,2) and (2,1) hash identically. Objects.hash folds with 31 * h + field, so order matters and the spread is far better. It does allocate a varargs array, which matters only on a genuinely hot path.

5. "Where does ConcurrentHashMap differ here?" Same treeify strategy and the same Comparable dependency, but it locks per bin. A degraded hash therefore costs more than time: every writer to the giant bin contends on one lock, so a bad hash turns a concurrent map into a serial one.

Check Yourself

Your key returns a constant hashCode and lookups are slow. You add Comparable. What changes, and what does not? Lookups go from O(n) to O(log n), because the treeified bin can now order its nodes and discard half at each step. What does not change: every key is still in one bin, and it is still thousands of times slower than a hash that spreads.

Why is 64 slots part of the treeify condition? Because a long bin in a small table usually means the table needs resizing, not that the hash is bad. Resizing redistributes entries and is cheaper than building a tree that the resize would have made unnecessary.

A map contains an entry that containsKey says is absent. What happened? A field used by hashCode changed after the put. The entry is filed under the old hash, so the lookup examines the wrong bin. Iteration still finds it, which is how you confirm the diagnosis.