前言
在阅读 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_ditribution) 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 后端开发职业 .
1
Select Language