存储桶计数，单位: unordered_map

Question

在下面给出的示例程序中(来源：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？对heapsize有什么影响？堆分配什么时候完成？在存储桶重新散列时还是实际插入时？当动态释放完成时？当使用clear()或erase()时，还是两者都使用？

Answer 1

libstdc++使用的默认重新散列策略是将存储桶的最小质数提升到大于或等于请求的数量。23是20以上的最小素数。

Answer 2

哈希表的大小通常被设置为“舒适地”大于表中要存储的项的数量。这是因为随着哈希表的填充，两个不同项映射到同一存储桶的概率会增加。

正如来自维基百科(image source)的下图所示，对于一些解决冲突的方法，如果哈希表的“负载因子”--使用的桶的百分比--超过某个分数，哈希表的行为就会受到极大的影响。

​

​

因此，存储桶的数量应该始终大于哈希表中的元素数量。

将存储桶的数量设置为质数有助于确保哈希表中的条目均匀分布在其中。一般来说，任何与存储桶数量共享公因子的键都将被散列到该因子的倍数的存储桶中。因此，如果您将存储桶的数量设置为20，并且您的散列值恰好是偶数，那么您将浪费大约50%的表空间。如果你的钥匙有4、5或10这样的因子，情况会更糟。

了解了以上内容，您就可以了解为什么哈希表可能比您指定的更大:额外的空间(通常)有助于提高性能。您还可以看到为什么垃圾箱的数量将是质数:因为这样可以更好地利用您拥有的空间。将这些组合在一起使23看起来是一个合理的选择。