Java 8 HashMap默认树化阈值设为8的原因探究

Great question about Java 8 HashMap's treeification threshold—this is one of those deep-dive details that reveals how much empirical testing and statistical analysis went into the JDK's core collections. Let's break this down step by step:

First: Why LinkedLists (Not Arrays) for Buckets? #

You hit the nail on the head here. Buckets use doubly linked lists of Nodes instead of arrays for a few key reasons:

• Arrays require preallocating fixed space, which is totally wasteful when most buckets stay empty or hold just 1 element (the norm with good hash functions).
• Collision probability is extremely low in practice—HashMap's dynamic resizing keeps load factors around 0.75, so most buckets never grow beyond a couple elements.
• While array inserts are technically O(1) amortized, that benefit only kicks in after resizing. For tiny N (1-7 elements), linked lists are more memory-efficient and just as fast, since you're only traversing a handful of nodes anyway.

Why Treeify at 8 Elements? The Core Tradeoff #

As you noted, TreeNodes take roughly twice as much memory as regular Nodes: a Node has hash, key, value, and next (4 fields), while a TreeNode adds prev, parent, left, right, and a red flag—so it's a much heavier object.

The JDK team had to balance two competing factors:

1. Lookup speed: Linked list lookup is O(N), red-black tree lookup is O(log N).
2. Memory overhead: Trees use more memory per element, which is a waste if buckets stay small.

The Statistical & Benchmarking Reason #

First, real-world hash collisions follow a Poisson distribution. The probability of a bucket having 8 elements is astronomically low—around 0.00000006% (6e-8%). That means treeifying at 8 is a safety net for extremely rare cases, not something that happens regularly.

Second, let's compare the cost for small N:

• For N=1-4: Linked list traversal averages 1-2 steps; tree lookup averages log2(N) steps, but with higher constant overhead (more pointer checks, color balancing). No net gain here—trees are just wasteful.
• At N=8: Linked list traversal averages 4 steps; tree lookup averages 3 steps. But more importantly, the O(log N) curve starts pulling away from O(N) here. Benchmarks from the JDK team showed that at this point, the speed gain from tree lookups outweighs the extra memory cost of TreeNodes.

Visualizing the Time-Space Balance #

Since I can't embed an interactive graph here, let's outline a simplified plot that shows the tradeoff:

• X-axis: Number of elements in the bucket (N, 1 to 10)
• Y-axis: Relative "cost" (combines time and memory; lower = better)

Key Trends in the Plot: #

• N=1-7: The linked list line sits below the tree line—linked lists are cheaper because the memory overhead of trees cancels out any tiny time savings.
• N=8: The tree line crosses below the linked list line—now the O(log N) speed gains are bigger than the extra memory cost.
• N>8: The gap widens rapidly—trees become far more efficient as N grows, since O(log N) scales way better than O(N).

To make this concrete, here's a simplified cost comparison (numbers are relative, based on JDK benchmarks):

Final Takeaway #

The 8-element threshold isn't a magic number—it's the result of analyzing real-world collision patterns and benchmarking the exact point where the speed benefits of red-black trees outweigh their memory costs. The JDK team optimized for the common case (small buckets, linked lists) and added a safety net for the rare cases where collisions pile up, ensuring HashMap stays fast and memory-efficient across all use cases.

内容的提问来源于stack exchange，提问作者wild_nothing