c++ - 我如何知道 `rehash` 是否发生在我插入 unordered_map 之后？

Question

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

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

我应该监控 bucket_count() 吗？

cppreference表示 只有当新的元素数量大于 max_load_factor()*bucket_count() 时才会发生重新散列。那是有保证的吗？这样做靠谱吗？

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

Answer 1

我不认为一旦 hash-map 增长就会发生重新散列(作为实际参与散列函数的过程):

1. 计算散列(相对)计算量大
2. 请看下面我快速编译的例子，我在其中制作了一个自定义哈希仿函数，它跟踪它被调用的时间:
   • 每当存储桶计数增加时，没有迹象表明哈希函数被调用 => 我们可以推断发生了重新存储而不是重新散列

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

#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() 迭代器的情况:在几次插入/放置之后，它将不再是真正的 begin。即使没有发生重新分桶，一些新条目也可能会安装在它前面(这可能会影响编程逻辑)。