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？ 对堆大小有什么影响？堆分配什么时候完成？在存储桶重新散列上还是在实际插入上？动态释放何时完成？何时使用

clear()

或

erase()

或同时使用？

Answer 1

libstdc++ 使用的默认重新哈希策略是向上查找大于或等于请求数量的最小质数桶。 23 是 20 以上最小的素数。

Answer 2

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

正如来自维基百科的下图（图像源）所示，对于某些冲突解决方法，如果散列表的“负载因子”（使用的存储桶的百分比）超过一定比例。

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

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

了解了上述内容，您就可以明白为什么哈希表可能比您指定的要大：额外的空间（通常）有助于提高性能。您还可以明白为什么垃圾箱的数量将是质数：因为这样可以更好地利用您所拥有的空间。将这些结合起来，23 似乎是一个合理的选择。

Answer 3

该程序演示了桶数量的增长取决于插入节点的数量。

#include <iostream>
#include <unordered_map>
#include <random>
#include <climits>

using namespace std;

int main()
{
    mt19937_64 mt;
    uniform_int_distribution<size_t> uid( 0, SIZE_MAX );
    unordered_map<size_t, char> map;
    map.max_load_factor( 1.0f );
    for( size_t r = 0; r < 0x10000; ++r )
    {
        size_t bucketsBefore = map.bucket_count();
        map.emplace( uid( mt ), 0 );
        size_t bucketsAfter = map.bucket_count();
        if( bucketsAfter == bucketsBefore )
            continue;
        cout << map.size() - 1 << " + 1: " << bucketsAfter << endl;
    }
}

这是 MSVC 的结果：

8 + 1: 64
64 + 1: 512
512 + 1: 1024
1024 + 1: 2048
2048 + 1: 4096
4096 + 1: 8192
8192 + 1: 16384
16384 + 1: 32768
32768 + 1: 65536

这是 libstdc++ (g++) / libc++ (clang) 的结果：

0 + 1: 13
13 + 1: 29
29 + 1: 59
59 + 1: 127
127 + 1: 257
257 + 1: 541
541 + 1: 1109
1109 + 1: 2357
2357 + 1: 5087
5087 + 1: 10273
10273 + 1: 20753
20753 + 1: 42043
42043 + 1: 85229

我不相信布莱恩说的话。计算某一个下界的下一个更高的素数可能需要付出很大的努力。我猜 libstdc++ 和 libc++ 使用固定步骤表。