为什么 std::unordered_set 即使负载因子限制没有被打破也会被重新散列？

Question

Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count().

此外，[unord.req]/15也有类似的规则：

The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container's bucket count, and z is the container's maximum load factor.

但是，请考虑以下示例：

#include <unordered_set>
#include <iostream>

int main()
{
    std::unordered_set<int> s;
    s.emplace(1);
    s.emplace(42);
    std::cout << s.bucket_count() << ' ';
    std::cout << (3 > s.max_load_factor() * s.bucket_count()) << ' ';
    s.emplace(2);
    std::cout << s.bucket_count() << ' ';
}

使用 GCC 8.0.1，输出

3 0 7

这意味着在放置 2 之后，虽然新的元素数量 (3) 不大于 max_load_factor()*bucket_count()（请注意第二个输出为 0），但会发生重新散列.为什么会这样？

Answer 1

来自 26.2.7 无序关联容器

The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound.
b.load_factor()           Returns the average number of elements per bucket.

b.max_load_factor()       Returns a positive number that the container attempts 
                          to keep the load factor less than or equal to. The container
                          automatically increases the number of buckets as necessary
                          to keep the load factor below this number.

我同意，max_load_factor描述的第一部分表明负载因子可以达到该值，但在第二部分和前面的引用中明确指出负载因子将保持在该值以下这个号码。所以，你发现了cppreference的错误。

在您的代码中，如果不重新散列，在第三次插入后您的 s.load_factor 将等于 s.max_load_factor()。

编辑：为了回答我检查过的问题的变化 VS unordered_set 的实现，它被实现为

// hash table -- list with vector of iterators for quick access

然后你要求一个迭代器，使用例如lower_bound，您获得列表元素的迭代器，它不会因重新散列而失效。所以，它同意 [unord.req]/15.

Answer 2

你混淆了 bucket_count() 已经随着迭代器失效而改变的事实。迭代器仅在重新散列的情况下无效，如果新的元素数量小于或等于 max_load_factor()*bucket_count()（顺便说一句，如果 size()>max_load_factor()*bucket_count() 重新散列 can发生，但不必发生）。

由于您的示例不是这种情况，因此没有发生重新散列并且迭代器仍然有效。但是，必须增加桶数以容纳新元素。

我用 Mac OSX 的 clang 做了一些实验（扩展你的代码），即使在 rehash(size()) 之后迭代器仍然有效（这确实改变了元素的桶关联，通过遍历存储桶并打印其内容直接进行测试）。

Answer 3

自 Issue 2156 以来，重新哈希条件已更改。改之前，当新的元素个数不少于max_load_factor()*bucket_count()时发生rehash，改之后变成"greater than"。

GCC 8.0.1 未实现此更改。已经有一个bug report，它已经在GCC 9中修复了。

为什么 std::unordered_set 即使负载因子限制没有被打破也会被重新散列？

Why is std::unordered_set rehashed even if the load factor limit is not broken?

c++

hash

stl

unordered-set