提问人：Dr. Debasish Jana 提问时间：3/1/2017 最后编辑：Dr. Debasish Jana 更新时间：3/1/2017 访问量：6559
存储桶计数（以unordered_map为单位）
Bucket count in unordered_map
问：
在下面给出的示例程序中（来源：http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/)
// unordered_map::rehash
#include <iostream>
#include <string>
#include <unordered_map>
int main ()
{
std::unordered_map<std::string,std::string> mymap;
mymap.rehash(20);
mymap["house"] = "maison";
mymap["apple"] = "pomme";
mymap["tree"] = "arbre";
mymap["book"] = "livre";
mymap["door"] = "porte";
mymap["grapefruit"] = "pamplemousse";
std::cout << "current bucket_count: " << mymap.bucket_count() << std::endl;
return 0;
}
输出变为：
current bucket_count: 23
为什么存储桶计数变为 23？
对堆有什么影响？堆分配何时完成？在存储桶重新散列还是在实际插入时？动态释放何时完成？何时使用或两者兼而有之？clear()erase()
答：
5赞
Brian Bi
3/1/2017
#1
libstdc++ 使用的默认 rehash 策略是将存储桶的最小质数增加到大于或等于请求的数量。23 是 20 以上的最小素数。
评论
1赞
Dr. Debasish Jana
3/1/2017
对堆有什么影响？堆分配何时完成？在存储桶重新散列还是在实际插入时？动态释放何时完成？当使用 clear（） 或 erase（） 或两者兼而有之时？
1赞
Brian Bi
3/1/2017
@Dr.DebasishJana 请不要使用评论来问 5 个问题，而是发布 5 个新问题。评论只能用于要求澄清。
3赞
Richard
3/1/2017
#2
哈希表的大小通常比表中存储的项目数“舒适”地大。这是因为两个不同项目映射到同一存储桶的概率会随着哈希表的填充而增加。
如下图所示，对于某些冲突解决方法，如果哈希表的“负载因子”---使用的存储桶的百分比超过一定比例，则哈希表的行为会受到严重影响---。
因此，存储桶的数量应始终大于哈希表中的元素数量。
将存储桶数设置为质数有助于确保哈希表中的条目均匀分布在哈希表中。通常，任何与存储桶数共享公因数的键都将被哈希处理为该因子的倍数的存储桶。因此，如果将存储桶数设置为 20，而哈希值恰好是偶数，则将浪费大约 50% 的表空间。如果您的密钥具有 4、5 或 10 等系数，情况会更糟。
了解了上述内容后，您就可以明白为什么哈希表可能比您指定的要大：额外的空间（通常）有助于提高性能。您还可以看到为什么垃圾箱的数量会是一个素数：因为这样可以更好地利用您拥有的空间。结合这些使 23 似乎是一个合理的选择。
评论