美文网首页
为什么Map桶中个数达到8才转为红黑树

为什么Map桶中个数达到8才转为红黑树

作者: 胡飞飞_1995 | 来源:发表于2019-06-01 11:01 被阅读0次

    为什么Map桶中个数超过8才转为红黑树

    源码在HashMap(jdk1.8)类一开始的注释中进行了简单的解释:


    image.png

    大意为桶中元素的数量大体遵循泊松分布,所以大概的概率如下:
    泊松分布:

    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
    更多的时候概率小于千万分之一

    还有一种民间的说法:
    红黑树的平均查找长度是log(n),如果长度为8,平均查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,而log(6)=2.6,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。

    相关文章

      网友评论

          本文标题:为什么Map桶中个数达到8才转为红黑树

          本文链接:https://www.haomeiwen.com/subject/qbpotctx.html