其實還是因為泊松分布，
哈希，又似里！
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的時候擴容啊~
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/158496.html
標籤：其他
上一篇：CRYPTO 2019-論文閱讀：Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations（1）