JAVA8 的 HashMap 中 TREEIFY_THRESHOLD 常量为什么是 8 ?

前言

在阅读 JDK1.8 中 HashMap 的源码过程中,发现了 TREEIFY_THRESHOLD 和 UNTREEIFY_THRESHOLD 两个新增变量。也就是树化阈值和树退化阈值。好奇为什么这两个值是 8 和 6,而非其他常量，于是记录下探究过程。

分析注解

 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * ( http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million

注解中写到（理想情况下，在随机哈希码和默认大小调整阈值为 0.75 的情况下,存储桶中元素个数出现的频率遵循泊松分布,平均参数为 0.5，有关 k 值下,随机事件出现频率的计算公式为 (exp(-0.5) * pow(0.5, k) /factorial(k))）

上面的注解给出了一些关键字和又一个未知的数字 0.5，以及一个数学公式。根据泊松分布维基百科得知，该公式为泊松分布的概率质量函数。由公式我们得知参数 0.5 是单位时间（或单位面积）内随机事件的平均发生率。

再看维基百科中 Statistical Inference （统计推断）中 Parameter estimation （参数估计）提到给定 n 个测量值的样本,使用 MLE，也就是最大似然估计，我们可以估算出 Lambda 的估算值.

所以我们大概能猜测出 a parameter of about 0.5 on average 是 oracle 公司进行大量测试后的平均值.

根据泊松分布概率质量函数,一个哈希桶达到 9 个元素的概率小于一千万分之一. 选定阈值为 8 猜测是基于泊松分布和类似与 DEFAULT_LOAD_FACTOR 一样，基于一些空间和效率之间取的一个平均值。接下来分析为什么退化阈值为 6.

代码解析

#若 loHead 的节点数量小于,则红黑树退化
if (lc <= UNTREEIFY_THRESHOLD)
    tab[index] = loHead.untreeify(map);
else {
    tab[index] = loHead;
if (hiHead != null)
    loHead.treeify(tab);
}
#若链表数量大于或等于(树化阈值-1)则退化,
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 是因为 binCount 是 0 为第一个节点.
    treeifyBin(tab, hash);

由代码我们得知，树化和树退化方法的判断都是闭区间，如果都是 8,则可能陷入(树化<=>树退化)的死循环中. 若是 7,则当极端情况下(频繁插入和删除的都是同一个哈希桶)对一个链表长度为 8 的的哈希桶进行频繁的删除和插入，同样也会导致频繁的树化<=>非树化.

由此,选定 6 的原因一部分是需要低于 8，但过于接近也会导致频繁的结构变化。

那为什么不是 6 以下呢？我也是这么想得.查看 TreeNode 和 Node 的源码

//树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
//链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

由源码可知,TreeNode 光是属性数就多于 Node, 再看Oracle 文档中变量的初始值,引用类型初始为 NULL.引用类型内存占用为 32 位系统 4 字节,64 位系统 8 字节.

故,不选定低于 6 的退化阈值一方面是因为红黑树不一定在低元素时效率更好（事实上由 MIN_TREEIFY_CAPACITY=64 参数，只有容量大于 64 时才会开启树化），另一方面则是红黑树相比链表占用了更多的引用。

以上的结论均是个人研究，另外，广州 /深圳求一份 JAVA 后端开发职业 .

JAVA8 的 HashMap 中 TREEIFY_THRESHOLD 常量为什么是 8 ?

前言

分析注解

代码解析

简历地址