我怎么知道在我插入 unordered_map 之后是否发生了 `rehash`？

Question

我了解 unordered_ stl 容器保留多个桶，这些桶的数量根据容器中元素的数量而变化。插入时，如果超过一定的限制，容器将重新散列以使用更多的桶，因此每个桶都不太满并且搜索速度更快。这会使迭代器无效。

这意味着我不应该将迭代器保存在 unordered 容器中。除了我可以，如果我在重新哈希后更新它们。但我找不到可靠的方法来检查 insert（无论是 emplace 还是其他）是否导致重新哈希。

我应该监控 bucket_count() 吗？

cppreference 表示 Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count()。那是有保证的吗？这样做靠谱吗？

bool will_rehash = (max_load_factor()*bucket_count()) > size()+1;

Answer 1

我不认为重新散列（作为实际使用散列函数的过程）会在散列映射增长时发生：

计算散列（相对）计算量大
请参阅下面我快速编译的示例，其中我制作了一个自定义哈希仿函数，它跟踪它被调用的时间：
- 每当桶计数增加时，没有迹象表明哈希函数被调用 => 我们可以推断发生了重新桶而不是重新哈希

这意味着，可以监视存储桶计数以推断迭代器是否应该失效（假设失效发生在重新存储桶的那一刻）

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

typedef unordered_map<string, string> str_map;

struct my_hash {
    void        reset(void) { calls_ = 0; }
    size_t      calls(void) { return calls_; }
    size_t      operator()(const string& key) const {
                 ++my_hash::calls_;
                 return hash_fn_(key);
                }
 private:
        str_map native_hash_fn_;
str_map::hasher hash_fn_{native_hash_fn_.hash_function()};
  static size_t calls_;
};

size_t my_hash::calls_ = 0;


int main ()
{
 typedef unordered_map<string, string, my_hash> myMapType;
 myMapType mymap(1, my_hash());
 myMapType::hasher hash = mymap.hash_function();

 cout << "mymap has " << mymap.bucket_count() << " buckets" << endl;

 mymap["abc1"] = "blah"; // add 3 values
 mymap["abc2"] = "blah"; // just to see the hash calls tracking
 mymap["abc3"] = "blah"; // is working
 cout << "hash calls: " << hash.calls() << endl;
 hash.reset();

 for(size_t i=0; i < 10; ++i) {
  mymap[to_string(i)] = "blah";
  cout << "buckets: " << mymap.bucket_count() << endl;
  cout << "hash calls: " << hash.calls() << endl;
  hash.reset();
 }

 cout << "mymap has " << mymap.bucket_count() << " buckets" << endl;
}

输出：

mymap has 2 buckets
hash calls: 3
buckets: 5
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 23
hash calls: 1
buckets: 23
hash calls: 1
buckets: 23
hash calls: 1
mymap has 23 buckets

免责声明：尽管如此，我坚信在容器大小发生变化后引用迭代器并不是一个好的编程习惯。即使它可能不会导致某些致命的/未定义的行为，它也可能（并且很可能会）对编程逻辑造成一些副作用。对于散列映射，请考虑使用 begin() 迭代器的情况：几次 insertions/emplacements 之后它将不再是真正的 begin。即使没有发生重新分桶，一些新条目也可能会安装在它前面（这可能会影响编程逻辑）。

我怎么知道在我插入 unordered_map 之后是否发生了 `rehash`？

How do i know whether `rehash` happened after i insert into an unordered_map?

c++

unordered-map