A bucket that becomes a tree

There is a comment in java.util.HashMap that does something unusual for a comment in a standard library: it shows its working.

It explains that tree nodes are about twice the size of plain ones, so they are used only where a bin holds enough entries to warrant them; that with well-distributed hash codes tree bins are rarely used at all; and that under random hash codes the number of entries in a bin follows a Poisson distribution with a parameter of about 0.5, given the resize threshold of 0.75. Then it lists the probabilities: a bin of one occurs with probability 0.30, of two 0.076, of three 0.013, and of eight — 0.00000006.

Six in a hundred million. The threshold at which a bucket becomes a red-black tree is eight, and the source comment’s own arithmetic says a bucket essentially never gets there.

What the Poisson argument says, measured #

Throw $n$ keys uniformly into $m$ buckets and the number landing in any given bucket is Binomial $(n, 1/m)$, which for large $m$ is Poisson with parameter $\lambda = n/m$. Java resizes at a load factor of 0.75, so $\lambda \le 0.75$, and the comment uses 0.5 as a working average across the resize cycle.

Measured, with 192 random keys in 256 buckets — $\lambda = 0.75$ — the longest bucket holds four. Not eight; four, and that is the maximum over 256 buckets, not the average. The mean successful lookup costs 1.42 comparisons.

Treeifying changes nothing at all, because nothing crosses the threshold. bucketCost with the mechanism enabled and disabled returns identical numbers, and assertTreeifyOnlyMattersWhenTheHashFails requires them to be identical — a check that the mechanism has not fired, which is an unusual thing to assert and is the right thing to assert here.

And what happens when the hash fails #

The third row is the one the mechanism exists for. With every key in one bucket, a chained lookup is a linear scan: 96.5 comparisons on average and 192 in the worst case, for a table holding 192 keys, which is worse than not having a hash table at all. With the bucket treeified it is 8 in the worst case.

The second row is the more realistic failure and it is the more interesting one. A hash that uses only the low three bits spreads 192 keys across 8 buckets of about 24 each; eight buckets pass the threshold and are converted; the mean lookup falls from 12.98 to 5.00 and the worst from 31 to 5.

A factor of twenty-four on the worst case, from a mechanism that has never once run on correctly-hashed data.

Why 8, specifically #

Two forces set the threshold and they pull in opposite directions.

Downward: a tree bin is faster to search once the bucket is long. Crossing over as early as possible minimises the worst case.

Upward: a tree node is about twice the size of a plain one — it carries parent, left, right, previous and a colour bit where a list node carries a next pointer. Converting a bucket doubles its memory, and converting eagerly would double the memory of a table that never needed it.

Eight is where the second consideration wins decisively. At $\lambda = 0.5$ the probability of reaching it is $6 \times 10^{-8}$, so the expected number of tree bins in a table of a million buckets is well under one. The threshold is set so that the memory cost is zero in practice, and the search cost is whatever it has to be in the case where the memory cost is already lost.

That is a different shape of trade from the ones in the threshold somebody chose. minrun and the insertion cutoff sit at the knee between two costs that are both paid on every run. This one sits where one of the costs is paid with probability $6\times10^{-8}$, so it is chosen to make the common case exactly free rather than to balance anything.

Pushing further makes the point sharply, and the figure refuses to draw it. At λ = 3 — four times Java’s resize threshold — a well-spread hash produces a longest bucket of exactly eight and four buckets are treeified on entirely ordinary data. bucket-occupancy asserts that a good hash never reaches the threshold, so at that load the assertion fails and no figure is emitted.

That refusal is the measurement. The treeify threshold is only dead code because the resize threshold keeps it that way, and the two constants — 8 and 0.75 — are not independent choices in two different parts of the class. Change either and the other stops meaning what it meant, which is the same entanglement the threshold somebody chose found among Timsort’s four.

At the threshold itself, the tree is worth twelve per cent #

Every number in the two failure rows comes from two expressions, and putting them side by side says something about where eight sits that the table does not.

A chained lookup into a bucket of $k$ entries costs $(k+1)/2$ on a successful search; a treed one costs $\lceil\log_2(k+1)\rceil$. At $k = 192$ that is 96.5 and 8 — the colliding row, exactly. At $k = 24$, which is what 192 keys in eight buckets gives, it is 12.5 and 5 against the measured 12.98 and 5.00, the excess being that the buckets are uneven and a lookup is size-biased towards the long ones.

So the mechanism’s worth is the ratio

$$\frac{k+1}{2\lceil\log_2(k+1)\rceil},$$

and evaluating it along the way up is the interesting part. At $k = 8$, the threshold itself: 4.5 against 4, a gain of twelve per cent. At 16: 8.5 against 5, a factor of 1.7. At 24: 2.5. At 192: 12.1.

The conversion is nearly worthless at the moment it fires, and its value grows without bound afterwards.

That is the right shape for a trigger nobody intends to pull, and it is worth stating as a design principle rather than as an observation about Java. A threshold placed where the remedy is already valuable would mean the mechanism was leaving value unclaimed below it — every bucket of six or seven would be paying a list’s cost while a cheaper structure sat one branch away. A threshold placed where the remedy is worth twelve per cent has nothing behind it worth claiming: the whole benefit is ahead, in the region a good hash never reaches.

It also resolves an objection the memory argument invites. A tree node is twice the size of a list node, so converting a bucket of eight doubles its memory for a twelve per cent improvement in lookup — a bad trade taken in isolation, and one nobody would make deliberately. The trade is not being made for the bucket of eight. It is being made because a bucket that has reached eight under a decent hash has reached it for a reason, and the reason keeps operating: the next entries into that bucket cost the tree nothing and the list everything. The conversion is an option priced at the moment it is nearly free, on a bucket whose future is the only thing that matters about it.

Which is a different relationship between a threshold and its trade from the ones the threshold somebody chose collects. minrun and an insertion cutoff sit at a crossing where two costs are equal and both are paid on every run; the value on either side is symmetric and the constant is a balance point. Eight is not a balance point. It is the earliest place where the evidence is strong enough to act on, chosen so that acting costs nothing if the evidence turns out to be noise — and the asymmetry between a twelve per cent gain and an unbounded one is what makes that a safe place to put it.

The same asymmetry is why the tree has to be balanced at all. On a bucket of eight the difference between a balanced tree and a tree that is a list is 4 against 4.5, which is nothing; on a bucket of 192 it is 8 against 96.5, which is the entire defence.

The other three constants in the same class #

Eight is not alone. HashMap carries four numbers that govern this mechanism, and reading them together is reading the design.

The last two are the interesting ones and neither is obvious.

Untreeifying at 6 rather than at 8 is hysteresis. If both thresholds were 8, a bucket oscillating around that size would convert and unconvert on alternate operations, and each conversion is a rebuild of the whole bucket. A gap of two makes the conversion sticky, and it is the same reason a thermostat has a dead band. The site has met this shape before, in the amortised analysis of a dynamic array: what amortised means shows the same oscillation when a structure’s grow and shrink thresholds coincide, and the same fix.

Not treeifying below a capacity of 64 is the more subtle one. A small table with a long bucket usually has a long bucket because it is small, not because the hash is bad — 12 keys in 4 buckets will produce a bucket of 5 or 6 by chance alone. The right remedy for that is to resize, which spreads the keys, rather than to build a tree that will be dismantled at the next resize anyway. So below 64 buckets a bucket reaching the threshold triggers a doubling instead of a conversion.

That is a genuine piece of judgement encoded in a constant: a long bucket in a small table is evidence about the table, and a long bucket in a large table is evidence about the hash. The threshold is the point at which the evidence changes meaning, and this site’s bucketCost carries minTreeifyCapacity as a parameter for exactly that reason.

Where the threshold came from, and what it says about the design #

The mechanism was added in Java 8, in 2014, and it was added for a security reason rather than a performance one.

Between 2011 and 2012 a series of hash-collision denial-of-service attacks were published against most web frameworks. The attack is simple: a web form or JSON body becomes a hash map, the attacker supplies thousands of keys that collide under the framework’s hash function, and a request that should cost $O(n)$ costs $O(n^2)$. A few hundred kilobytes of carefully chosen request body consumed minutes of processor time.

The defences split into two kinds and Java shipped both.

Randomise the hash, so the attacker cannot compute colliding keys without knowing the seed. This is the adversary who knows the seed exactly, and it is the right answer — but for string keys, Java’s hashCode is specified in the language documentation and cannot be changed, because programs depend on its value.

Bound the damage when collisions happen anyway. That is the treeify threshold. It converts an $O(n^2)$ attack into an $O(n \log n)$ one, which is not an attack.

So the mechanism exists because a hash function’s value was frozen into a specification decades before anybody thought about adversarial input, and the only remaining lever was the collision handling. It is a structural defence adopted because the cryptographic one was unavailable, and that is why it is here and not in the many other hash tables whose hash functions can be keyed.

The argument runs the other way as well, and the other direction is the one that matters to a small map. If the maximum grows like $\log m / \log\log m$ then shrinking the table should barely move it either, so a table of sixty-four buckets at the same load ought to sit two or three under the threshold rather than comfortably below it by luck.

Both directions of that sweep answer the obvious objection to the Poisson argument, which is that a probability of six in a hundred million per bucket is not reassuring when there are a hundred million buckets.

The answer is that the relevant quantity is the maximum bucket size, not the probability for a fixed bucket, and the maximum of $m$ Poisson variables grows like $\log m / \log\log m$ — slowly enough that going from 256 buckets to 1,024 moves the longest bucket from four to five. Reaching eight requires the table to be enormous, and by then the expected number of tree bins is a handful in a structure holding millions of entries, which is exactly the “rarely used” the source comment claims.

The threshold is not chosen so that no bucket ever reaches it. It is chosen so that the number that do is bounded and small at any size — which is a stronger statement, and a checkable one, and the measurement above is the check.

The open-addressing answer to the same problem #

The previous essay measured a different structure solving a related problem, and the contrast is the clearest way to see what each one is for.

The probe nobody waits for showed Robin Hood hashing collapsing the variance of a lookup’s cost while leaving the mean untouched. Under a good hash it is a real improvement, worth a factor of ten in variance at high load. Under an adversarial hash it makes every lookup equally terrible instead of most fast and a few catastrophic, which for a percentile is arguably worse.

The treeify threshold is the opposite in both respects. Under a good hash it does exactly nothing — the numbers are identical to the digit. Under an adversarial hash it is the difference between a linear scan and a logarithmic one.

One mechanism improves the ordinary case and does not survive an adversary; the other is invisible in the ordinary case and is entirely a defence. A library that wants both has to have both, and Java, having chosen chaining, could only have the second.

Chaining against open addressing, on the failure #

There is one more comparison worth making, because the two structures fail differently and the difference decides which threshold each of them needs.

Under a hash that concentrates keys, a chained table degenerates into one long list and every other bucket stays empty. The damage is confined: lookups for keys in the good buckets are unaffected, and only the keys in the bad bucket are slow. That is why a per-bucket remedy works — treeify the one bad bucket and the table is fine again.

An open-addressed table degenerates into one long cluster, and the damage spreads. A key that hashes to an empty slot near the cluster’s end still has to walk past whatever is in the way. There is no per-bucket structure to convert, because there are no buckets; the cluster is the table.

That asymmetry explains why the treeify threshold exists in Java’s chained HashMap and has no counterpart in a Swiss table or a Robin Hood table. A remedy that acts on one bucket requires the failure to be confined to one bucket, and open addressing’s failure mode is the one that is not.

The open-addressing answer to adversarial keys is therefore the cryptographic one — a keyed hash, reseeded per process — with no structural fallback. Rust’s HashMap does exactly that and is documented as doing it. Java could not, for the reason above, and so needed the structural answer instead.

What it costs to have it #

Nothing measurable, on correct data, which is the whole design goal — and “nothing measurable” is doing some work in that sentence.

The comparison count is identical with and without the mechanism under a good hash, because the branch that would convert is never taken. What is not identical is the code: every insertion tests whether the bucket has reached the threshold, every bucket carries the possibility of being either a list or a tree, and every lookup begins by asking which it is. A test that is always false still costs a test — and by the fifth counter’s logic, an always-false test costs almost nothing, because a predictor learns it in one execution and is never surprised again.

That is a satisfying place for this phase to end. The treeify threshold is a mechanism whose common-case cost is one perfectly predictable branch per operation, whose value in the case it was written for is a factor of twenty-four, and whose probability of firing on correct data is six in a hundred million. Every one of those three numbers is measurable, and this site could measure only two of them before this phase.

That figure is worth spelling out because it is easy to miss and it is the mechanism’s real subtlety. Treeifying a bucket only helps if the tree is balanced, and the keys in a collided bucket are exactly the keys an attacker chose. A plain binary search tree fed adversarial keys is a linked list with extra pointers, and the attack would go through unchanged.

So the threshold requires a balanced tree, which requires an ordering on the keys — and a hash map’s keys need only be comparable for equality. Java’s answer is to fall back on comparing the keys’ hash codes, then their class names, then their identity hash codes, in that order, purely to obtain some total order to balance against. It is one of the least elegant pieces of code in the standard library, and it is there because a balanced tree is the only structure that survives an adversary and a balanced tree needs an order.

The mechanism that almost never fires needs three fallbacks to work in the case it was written for. Measuring it here uses a modelled $\lceil \log_2(k+1) \rceil$ for the tree’s cost rather than a real red-black tree, and every figure says so — the subject is the threshold, and putting a real balanced tree behind it would have added a distribution to a figure about a decision rule.