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

[Macolor21]

前言

在阅读 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 后端开发职业 .

简历地址

重新附上简历地址

重新附上简历地址

应该是MD语法问题

[dooonabe]

简历 404 了

[lff0305]

由源码可知,TreeNode 光是属性数就多于 Node, 再看 Oracle 文档 中变量的初始值,引用类型初始为 NULL.引用类型内存占用为 32 位系统 4 字节,64 位系统 8 字节. <==== 这个不对, 通常情况下 64 位默认也是 4 字节,参考 JVM 的压缩指针.

[Macolor21]

@lff0305 谢谢指正，在 Hotspot 上确实找到了有关压缩 OOPS 的相关内容。https://wiki.openjdk.java.net/display/HotSpot/CompressedOops

[Macolor21]

在 JRockit JVM 上也找到了相关说明 https://docs.oracle.com/cd/E13150_01/jrockit_jvm/jrockit/geninfo/diagnos/memman.html

To reduce the memory usage for address references on 64-bit systems, the JRockit JVM can use compressed references. Compressed references reduce the address references to 32 bits, and can be used as long as the entire heap can be addressed with 32 bits.

[keshawnvan]

杭州考虑吗？

[Macolor21]

@keshawnvan 可以考虑，请问您看过我的简历吗？

[keshawnvan]

@Macolor21 看了下，社招的话工作经验有点短了

[Macolor21]

@keshawnvan 好的，了解。

[keshawnvan]

@Macolor21 可以加个好友，以后有机会了邀请你。微信：fkx0703