HashMap里面的一个细节

扫了一眼Java8的HashMap的代码，发现一个细节，觉得值得一记。

我们知道Java8里面的HashMap做了一个改动，就是当hashkey conflict的时候，以前都是用一个LinkedList把这些key串起来。这个做法，中规中矩，大一数据结构课上就有学过，Java也沿用了十几年。

但是后来有人发现问题了，这样恶意用户可以通过精心构造key，使得大量的entry都落到同一个list上，活生生的把一个O(1)的读取变成O(n)的。于是Java8里面，HashMap做了一个TradeOff，如果一个key下面的list太长，就把这个list转成tree，这样好歹是O(logn)的时间复杂度，不会被轻易DDOS。

那么问题来了，我们应该怎么量化这个“太长”，list的长度超过多少，我们就应该把它转为tree，因为我在内存中存放treeNode的成本是普通node的两倍，所以这个值不宜过小，当然也不宜过大，不然这个代码被调用的几率太小，写了它干嘛。

这个时候HashMap的作者做了一个分析，展现了他们作为专业软件工程师和普通战五渣JAVA农之间的区别，直接引用注释。

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的load factor，HashMap每个slot可能存在值的几率是0.5，每个HashMap的slot下的Entry个数符合泊松分布，我们只要把Entry下个数k带入泊松分布的公式 (exp(-0.5) * pow(0.5, k) / factorial(k))，就可以得到平常情况（非恶意构造key）下list转tree的概率，如果长度达到8时才转，这种情况发生概率是0.00000006。够低了，所以这个阈值定的8。

这里的分析方式，可以用在很多地方，比如我有一个实时处理模块，单位时间最大吞吐是w，写入的平均量是p（p<w)，在这个模块前面加个buffer，一旦模块负荷满，而且buffer也填满，就停止接收上游日志，我这个buffer应该设多大，才可以保障6个9的高可用。这时就是(exp(-w)*pow(w,k)/factorial(k))，解出k来，减去w就是应该的buffer capacity。