若桶中链表元素个数大于等于8时,链表转换成树结构;若桶中链表元素个数小于等于6时,树结构还原成链表。
理想情况下使用随机的哈希码,容器中节点分布在hash桶中的频率遵循泊松分布;
依照泊松分布计算出hash桶中元素个数与概率如下:
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
因此原因有2
- 1.桶的长度超过8的概率非常非常小。所以作者是根据
概率统计而选择了8作为阀值。 - 2.之所以没有直接使用红黑树的结构,是因为红黑树的节点比链表节点大,占用空间更大,而且链表比较短的时候查询也足够快,因此没必要直接使用红黑树的结构。