全部评论
另外有个思路,是别的地方看到的: 只有长度N >= 7的时候,红黑树的平均查找长度lgN才会小于链表的平均查找长度N/2,这个可以画函数图来确定,lgN 与N/2的交点处N约为6.64。 为什么设置为8而不是7呢?一个原因是为了防止出现频繁的链表与树的转换,当大于8的时候链表转红黑树,小于6的时候红黑树转链表,中间这段作为缓冲。 不知道这么理解对不对?
看过一篇文章,理想状态下哈希表的每个“箱子”中,元素的数量遵守泊松分布。当负载因子为 0.75 时,公式中的 λ 约等于 0.5,箱子中元素个数和概率的关系在个数为8的时候,概率最小。
mark,被面试官问过
链表转红黑树的开销和冲突带来的额外开销的一个权衡吧,在hash函数足够好的情况下链表长度大于8的概率极小。😅
如果是7 你又问为什么不是8
这题我知道我知道,如果他是7或者9的话,你又要问为什么不是8,但是他总得有个数吧
相关推荐