std::unordered_map 和 boost::unordered_map 为桶预留了多少空间，为什么？

Question

当您将元素插入

unordered_map

且新元素数量大于

max_load_factor()*bucket_count()

时，容器会增长（桶数增长）并发生重新哈希。

我做了一个简单的实验：我创建了一个分配器，每次调用方法

allocate(size_type n)

时都会打印分配的内存大小，并将其与

unordered_map

一起使用。在循环中，我将新元素插入到该容器中（每次迭代中一个元素）。

对于

std::unordered_map

我得到了这些数字：

2, 5, 11, 23, 47, 97, 199, 409, 823, 1741, 3739, 7517, 15173, 30727, 62233, 126271

对于

boost

：

18, 30, 54, 98, 194, 390, 770, 1544, 3080, 6152, 12290, 24594, 49158, 98318

我的问题是：

std::unordered_map

和

boost::unordered_map

使用什么策略来确定以下要创建的桶数量？这些数字是硬编码的还是计算出来的？为什么这样的策略被认为是好的？

编辑： 实现取决于编译器。我使用 gcc 7.5 和 boost 1.65.1，但任何答案（对于任何实现）都会很有趣。

Answer 1

libstdc++

它使用首要策略。这意味着新的桶数将被计算为大于或等于所需数量的最小质数。为了使操作更快，素数被硬编码在 C 风格的数组中，

__prime_list

。

此策略是首选，因为它会导致较少的哈希冲突。

提升

它公开了两种不同类型的策略：mix64 和 prime。该策略是在编译时通过

pick_policy

类型特征选择的，具体取决于积分类型。例如，如果

std::numeric_limits<std::size_t>::digits

为 64 并且

std::numeric_limits<std::size_t>::radix

为 2，则选择 mix64 策略。

同样在这种情况下，原因源于性能：mix64 策略通常比 prime 策略更快。