为什么当 unordered_map 由于“预留”而拥有足够的存储桶时，其大小会增加？

Question

考虑这段代码。我为 unordered_map 保留 6 个位置并插入 6 个元素。之后还有7个桶。为什么是这样？ max_load_factor 为 1，并且有足够的存储桶来容纳我插入的元素数量。

#include <iostream>
#include <unordered_map>
using namespace std;

int main () {
  unordered_map<std::string,std::string> mymap = { 
            {"house","maison"},
            {"apple","pomme"},
            {"tree","arbre"},
            {"book","livre"},
            {"door","porte"},
            {"grapefruit","pamplemousse"}
  };

    unordered_map<std::string,std::string> mymap2; // THIS ONE!!!
    mymap2.reserve(6);
    for (auto i:mymap) {
        mymap2[i.first] = i.second;
    }


    std::cout << "max_load factor " << mymap2.max_load_factor() << " mymap has " << mymap2.bucket_count() << " buckets.\n";

      for (unsigned i=0; i<mymap2.bucket_count(); ++i) {
        cout << "bucket #" << i << " contains: ";
        for (auto it = mymap2.begin(i); it!=mymap2.end(i); ++it)
            cout << "[" << it->first << ":" << it->second << "] ";
          cout << endl;
      }

  return 0;
}

输出：

max_load factor 1 mymap has 7 buckets.
bucket #0 contains: 
bucket #1 contains: [book:livre] 
bucket #2 contains: [tree:arbre] 
bucket #3 contains: [house:maison] [grapefruit:pamplemousse] 
bucket #4 contains: 
bucket #5 contains: [door:porte] 
bucket #6 contains: [apple:pomme] 

Answer 1

哈希表实现倾向于在两个理想的品质之间进行选择：

• 保持二的幂

  bucket_count()

  （即，如有必要，将传递的任何值四舍五入以保留到下一个二的幂），所以

  • a

    size_t

    可以映射哈希函数返回的值 使用 1 个 CPU 周期按位 AND 运算进入存储桶范围 （例如 8 个桶 -> 哈希值与 7 进行 AND 运算）；

  • 这会产生从哈希值中删除高阶位的不良影响，因此它们无助于随机化存储桶放置

  • Visual C++ 可以做到这一点

• 保持巅峰状态

  bucket_count()

  • 这具有非常理想的副作用，即散列值中的高阶位会影响存储桶选择，因此较低质量（即更快）的散列函数仍然经常管理更平等、更少冲突/聚类倾向的、桶的放置

  • 天真地实现了，这迫使编译器通过运行时变量

    bucket_count()

    执行 mod（“％”）操作，这可能需要例如40-90 个 CPU 周期，具体取决于 CPU。更快的替代方法是使用素数表中的索引，在调整哈希表大小时使用该硬编码常量素值切换到 mod 操作，因此编译器可以尝试使用移位、减法或加法来优化 mod ，或者如果有必要的话进行乘法（您可以在godbolt 上的这个片段中看到可能的优化类型）

  • GCC 就是这么做的；我想 clang 也是如此。

因此，总而言之 - 当您要求 6 个存储桶时，GCC 或 clang 会将其增加到某个素数 - 不一定是下一个，但在这种情况下似乎发生了 - 以减少稍后插入元素时的冲突倾向。

Answer 2

cplusplus.com 网站给出了这样的解释：

void reserve (size_type n);

请求更改容量

将容器 (

bucket_count

) 中的桶数设置为最适合包含 至少 n 个元素。

如果 n 大于当前

bucket_count

乘以

max_load_factor

，则容器的

bucket_count

会增加并强制重新哈希。

如果n低于该值，该功能可能无效。

在声明

unordered_map

变量时，它的

bucket_count

为

1

，

max_load_factor

为

1

。 然后你

reserve

6

桶大于

max_load_factor

乘以

bucket_count

根据这个定义，以我的拙见，这种行为是正确的。

我在代码的第

17

行添加了以下行，以在

bucket_count

之前显示

reserve

，事实上，它是

1

 std::cout << "BEFORE RESERVE max_load factor " << mymap2.max_load_factor() << " mymap has " << mymap2.bucket_count() << " buckets.\n";

显示如下：

BEFORE RESERVE max_load factor 1 mymap has 1 buckets.

预订后：

AFTER RESERVE max_load factor 1 mymap has 7 buckets.

因此，我认为这种行为是正常的。