std::unordered_map<>默认重新哈希后的bucket_count() [英] std::unordered_map<> bucket_count() after default rehash

问题描述

如果我不断向 unordered_map 添加值，那么每次元素数量超过 bucket_count()(假设 max_load_factor = 1)时都会发生重新散列.

If i keep adding values to an unordered_map then every time the number of elements exceeds the bucket_count() (assuming max_load_factor = 1) rehashing takes place.

我很困惑的是重新散列后的桶大小.

What I am very confused about is the bucket size after rehashing.

#include <iostream>
#include <unordered_map>
int main() {
   std::unordered_map<size_t, size_t> mp;

   for (size_t i = 0; i < 1000; ++i) {
      mp[i] = i;
      std::cout << " count: " << mp.bucket_count() << std::endl;
   }
}

输出 3 7 17 37 79 167 337 709 1493

This outputs 3 7 17 37 79 167 337 709 1493

我注意到桶的大小是主要的并且大约翻了一番.然而，它也不是最接近 2 的下一个幂的素数.

I have noticed that the bucket size is prime and approximately doubles. However it is not the closest prime to the next power of 2 either.

这种桶大小增加背后的方法是什么.我很惊讶或很愚蠢，以至于在 cplusplus.com 等标准参考资料中找不到任何相关内容

What is the methodology behind this bucket size increase. I was surprised or stupid enough that I couldn't find anything about it in standard references such as cplusplus.com

推荐答案

重新散列后的桶大小将取决于编译器.您看到的具体数字可以通过获取当前存储桶大小，乘以 2，然后从 __prime_list 数组中获取大于该值的最近素数来找到:https://github.com/g5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/shared/hashtable-aux.cc

The bucket sizes after rehashing will be compiler specific. The specific numbers you are seeing can be found by taking the current bucket size, multiplying by 2, and then taking the nearest prime larger than that value from the __prime_list array here: https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/shared/hashtable-aux.cc

这篇关于std::unordered_map<>默认重新哈希后的bucket_count()的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！