为什么unordered_map桶的大小是8?

   日期:2020-10-05     浏览:198    评论:0    
核心提示:其实还是因为泊松分布。STL中的hashmap就unordered_map。它记录的键是元素的哈希值,通过对比元素的哈希值来确定元素的值。unordered_map的底层实现是hashtable,采用开链法(也就是用桶)来解决哈希冲突,当桶的大小超过8时,就自动转为红黑树进行组织。而转换为红黑树,尤其是红黑树的插入删除遍历的复杂度最坏时间复杂度都是log(n),一旦转为红黑树哈希表的性能将大大降低,所以只有桶中包含足够多的元素以供使用时,我们才会使用rbtree。那为什么这个数字是8呢?官方给出这样一张

其实还是因为泊松分布。
哈希,又似里!
STL中的hashmap就是unordered_map。它记录的键是元素的哈希值,通过对比元素的哈希值来确定元素的值。unordered_map的底层实现是hashtable,采用开链法(也就是用桶)来解决哈希冲突,当桶的大小超过8时,就执行rehash操作(hashmap是转为rbtree)。那为什么这个数字是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

即,在理想情况下,在随机哈希代码下,桶中的节点频率遵循泊松分布,而经过统计,桶的长度超过8的概率非常非常小,那7也不错,9也可以,为什么是8?这牵扯到哈希以位运算的扩容机制,当桶的大小为2的幂次方时,计算的效率最高,所以8是一个合理的选择。

然后我兴致冲冲的去看源码,在 /usr/include/c++/4.8.2/tr1/unordered_map:86,发现初始化的桶大小写死为 10 (黑人问号?)???

explicit
unordered_map(size_type n = 10,
      const hasher& hf = hasher(),
      const key_equal& eql = key_equal(),
      const allocator_type& a = allocator_type())
: Base(n, hf, Internal::mod_range_hashing(),
   Internal::default_ranged_hash(),
   eql, Internal::extract1st<std::pair<const Key, T> >(), a)
{  }

当然是10啦,因为10*0.8=8,当为8的时候扩容啊~

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服