JDK1.8的HashMap为什么是链表长度大于8之后

JDK1.8的HashMap为什么是链表长度大于8之后转化为红黑树?为什么不是7,为什么不是9,出于什么考虑?#百度##腾讯##去哪儿##阿里巴巴##Java工程师##网易#
全部评论
另外有个思路,是别的地方看到的: 只有长度N >= 7的时候,红黑树的平均查找长度lgN才会小于链表的平均查找长度N/2,这个可以画函数图来确定,lgN 与N/2的交点处N约为6.64。 为什么设置为8而不是7呢?一个原因是为了防止出现频繁的链表与树的转换,当大于8的时候链表转红黑树,小于6的时候红黑树转链表,中间这段作为缓冲。 不知道这么理解对不对?
4 回复 分享
发布于 2017-10-28 20:02
看过一篇文章,理想状态下哈希表的每个“箱子”中,元素的数量遵守泊松分布。当负载因子为 0.75 时,公式中的 λ 约等于 0.5,箱子中元素个数和概率的关系在个数为8的时候,概率最小。
3 回复 分享
发布于 2017-10-28 19:31
mark,被面试官问过
1 回复 分享
发布于 2017-10-28 19:26
链表转红黑树的开销和冲突带来的额外开销的一个权衡吧,在hash函数足够好的情况下链表长度大于8的概率极小。😅
点赞 回复 分享
发布于 2017-10-28 19:08
如果是7 你又问为什么不是8 
点赞 回复 分享
发布于 2017-10-28 19:19
这题我知道我知道,如果他是7或者9的话,你又要问为什么不是8,但是他总得有个数吧
点赞 回复 分享
发布于 2017-10-28 23:22
点赞 回复 分享
发布于 2021-04-23 16:14

相关推荐

点赞 22 评论
分享
牛客网
牛客企业服务