为什么HashMap链表存储结构转换为红黑树的长度临界点是8?

  1. 分布规律

    概率统计学,在随机哈希代码下,链表长度超过8的概率非常非常小

    ​ 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

  2. 时间复杂度

    首先只有红黑树的效率高过链表才有转换的必要

    红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3

    链表的平均查找长度为n/2，当长度为6时，查找长度为6/2=3 这时和红黑树效率持平

    当长度一致为8时，平均查找长度为8/2=4

    2.1 为什么不是6?

    转化为树结构是有成本的

    2.2 为什么不是7?

    如果超过7则转换为数,低于7则转换为链表,就有可能导致频繁的转换,转换是有成本的

    所以中间加了个缓冲,转换的临界点设定为了8和6