HashMap的泊松分布

1. 泊松分布公式：

2. HashMap泊松分布的解释推导：

    /**
     * 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.
     *
     * 翻译：
     *     尽管因为调整粒度而产生较大的方差，但是理想的情况，在随机hashCodes下，桶中节	点的频率遵循泊松分布。
     *     默认调整阈值为0.75的条件下，泊松分布中的概率参数λ=0.5。
     * 解释：
     * 	   k表示数量，这里指桶中节点的个数。
     *     λ表示事件的频率。这里λ=0.5，代表理想情况下，平均100个桶，50个数据，则1个桶有数据的概率是0.5。
     *     忽略方差，把λ代入。则求一个桶中出现k个节点的概率，公式为：
     * @param k
     * @return
     */
    private static String poisson(int k) {
        //泊松分布 Java
        double value = Math.exp(-0.5) * Math.pow(0.5, k) / IntMath.factorial(k);
        //格式化参数，保留10位小数。
        return new BigDecimal(value+"").setScale(10, ROUND_HALF_UP).toPlainString();
    }

3. 打印结果：

    public static void main(String[] args) {
        System.out.println("1个桶中出现1个节点的概率:" + poisson(1));
        System.out.println("1个桶中出现2个节点的概率:" +poisson(2));
        System.out.println("1个桶中出现3个节点的概率:" +poisson(3));
        System.out.println("1个桶中出现4个节点的概率:" +poisson(4));
        System.out.println("1个桶中出现5个节点的概率:" +poisson(5));
        System.out.println("1个桶中出现6个节点的概率:" +poisson(6));
        System.out.println("1个桶中出现7个节点的概率:" +poisson(7));
        System.out.println("1个桶中出现8个节点的概率:" +poisson(8));//亿分之六
        System.out.println("1个桶中出现9个节点的概率:" +poisson(9));
    }

Console:
	1个桶中出现1个节点的概率:0.3032653299
	1个桶中出现2个节点的概率:0.0758163325
	1个桶中出现3个节点的概率:0.0126360554
	1个桶中出现4个节点的概率:0.0015795069
	1个桶中出现5个节点的概率:0.0001579507
	1个桶中出现6个节点的概率:0.0000131626
	1个桶中出现7个节点的概率:0.0000009402
	1个桶中出现8个节点的概率:0.0000000588//亿分之六
	1个桶中出现9个节点的概率:0.0000000033

4. 解释树化的两个条件：

1. 为什么链表长度达到8？
   因为达到8个元素的时候，概率已经很低了。此时树化，性价比会很高。
   既不会因为链表太长(8)导致复杂度加大，也不会因为概率太高导致太多节点树化。
2. 为什么数组长度达到64？

/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
翻译：应该至少为4 * TREEIFY_THRESHOLD = 32，以避免大小调整和树化阈值之间发生冲突。

补充：至于为什么λ=0.5，应该是这样计算的：
假设n是HashMap的数组长度