unordered_map 对哈希函数的过多调用
unordered_map excess calls to hash function
以下代码导致对哈希函数的无法解释的调用：
namespace foo {
using Position = tuple <int, int, int>;
std::ostream& operator<<(std::ostream& out, const Position& pos) noexcept{
return out << get<0>(pos) << ", " << get<1>(pos) << ", " << get<2>(pos);
}
struct hashFunc{
std::size_t operator()(const Position& pos) const noexcept{
int res = get<0>(pos) * 17 ^ get<1>(pos) * 11 ^ get<2>(pos);
cout << "@@@ hash function called for key: " << pos
<< ", hash: " << res << endl;
return res;
}
};
template<typename T>
void print_buckets(T&& map) {
auto num_buckets = map.bucket_count();
cout << "------------------------------" << endl;
cout << "NUM BUCKETS: " << num_buckets << endl;
for(size_t i=0; i<num_buckets; ++i) {
auto bucket_size = map.bucket_size(i);
if(bucket_size) {
cout << "BUCKET " << i << " size: " << bucket_size << endl;
}
}
cout << "------------------------------" << endl;
}
}
主要：
using namespace foo;
int main() {
// note: bucket_count specified
unordered_map <Position, std::string, hashFunc> test(10);
auto x = tuple{1,0,0};
auto z = tuple{0,1,0};
auto w = tuple{0,0,1};
cout << "==================================" << endl;
cout << "about to insert: " << x << endl;
test[x] = "hello";
print_buckets(test);
cout << "after insert of: " << x << endl;
cout << "==================================" << endl;
cout << "about to insert: " << z << endl;
test[z] = "hey";
print_buckets(test);
cout << "after insert of: " << z << endl;
cout << "==================================" << endl;
cout << "about to insert: " << w << endl;
test.insert({w, "hello"});
print_buckets(test);
cout << "after insert of: " << w << endl;
cout << "==================================" << endl;
}
输出：
==================================
about to insert: 1, 0, 0
@@@ hash function called for key: 1, 0, 0, hash: 17
------------------------------
NUM BUCKETS: 11
BUCKET 6 size: 1
------------------------------
after insert of: 1, 0, 0
==================================
about to insert: 0, 1, 0
@@@ hash function called for key: 0, 1, 0, hash: 11
@@@ hash function called for key: 1, 0, 0, hash: 17 <= why?
------------------------------
NUM BUCKETS: 11
@@@ hash function called for key: 1, 0, 0, hash: 17 <= why?
BUCKET 0 size: 1
BUCKET 6 size: 1
------------------------------
after insert of: 0, 1, 0
==================================
about to insert: 0, 0, 1
@@@ hash function called for key: 0, 0, 1, hash: 1
@@@ hash function called for key: 0, 1, 0, hash: 11 <= why?
------------------------------
NUM BUCKETS: 11
@@@ hash function called for key: 1, 0, 0, hash: 17 <= why?
BUCKET 0 size: 1
@@@ hash function called for key: 0, 1, 0, hash: 11 <= why?
BUCKET 1 size: 1
BUCKET 6 size: 1
------------------------------
after insert of: 0, 0, 1
==================================
Code （gcc 和 clang 的行为相同）
备注：
1.在构造函数没有 bucket_count 参数的情况下尝试相同的操作，由于重新哈希，对哈希函数的调用变得更加过度。但是在上面的场景中，似乎没有重新散列，也没有冲突。
2。相关，但专门针对 MSVC：Inserting to std::unordered_map calls hash function twice in MSVC++'s STL, bad design or special reason?
我无法解释为什么这样做，但它不适合发表评论，所以我将其留在答案部分。插入元素后，stdlib (10.1.0) 中有两个部分：
__hash_code __code = __h->_M_hash_code(__k);
计算要插入的元素的哈希值__k.
后面这部分代码：
{
// The bucket is empty, the new node is inserted at the
// beginning of the singly-linked list and the bucket will
// contain _M_before_begin pointer.
__node->_M_nxt = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = __node;
if (__node->_M_nxt)
// We must update former begin bucket that is pointing to
// _M_before_begin.
_M_buckets[_M_bucket_index(__node->_M_next())] = __node;
_M_buckets[__bkt] = &_M_before_begin;
}
其中_M_bucket_index为__node->_M_next()计算散列，__node指的是为__k创建的节点。
也许这有助于您或其他人进一步解释它。
可能是std::unordered_map的实现。 hash_value 没有存储到每个节点中。因此，当插入新元素或计算桶大小时，它将re-hash下一个桶中的第一个元素。
您可以尝试使用<tr1/unordered_map>来避免这个问题。示例：
#include <tr1/unordered_map>
using std::tr1::unordered_map;
注意：我不知道 tr1/unordered_map 或 unordered_map 哪个更好。
首先，有几点观察：
无序映射既是散列 table，又是 singly-linked 列表。
参见 here begin returns 一个 iterator 模型 LegacyForwardIterator.
向映射中插入条目需要同时更新哈希 table 和链表。
其次，关于这些容器的实施决策的几点说明：
对于singly-linked列表，通常有一个不包含任何数据的哨兵节点（对于Node<T>，它仍然会有一个T，只是 default-initialized)。我们只需要它的 next 指针，因为它有助于保持列表操作的规律性（即，我们不必编写 insert-at-the-head 和 insert-after-node 作为不同的特殊情况）。
对于散列 tables（假设 linked-list 个桶，因为它是标准所要求的）我们可以使用 Node table[N]（所以每个桶都有自己的哨兵预分配）或 Node* table[N].
在这种情况下，由于我们实际使用 Node<T> 并且不知道 T 的大小，因此为每个桶存储一个指针似乎是合理的。
对于散列 table 这是 也是 一个 singly-linked 列表，使用 per-bucket 是有意义的列为 all-elements 列表（的一部分）。否则我们需要为每个节点存储两个指针，next_in_bucket 和 next_in_list.
这意味着一个桶指向的“哨兵”（one-before-the-beginning）节点实际上是前一个桶的last节点...除了bucket在列表的最前面，当它真的是整体列表哨兵时。
code中的评论说
/* ...
* The non-empty buckets contain the node before the first node in the
* bucket. This design makes it possible to implement something like a
* std::forward_list::insert_after on container insertion and
* std::forward_list::erase_after on container erase
* calls. _M_before_begin is equivalent to
* std::forward_list::before_begin. Empty buckets contain
* nullptr. Note that one of the non-empty buckets contains
* &_M_before_begin which is not a dereferenceable node so the
* node pointer in a bucket shall never be dereferenced, only its
* next node can be.
（这段代码中的哨兵是_M_before_begin）
所以，当我们向already-populated桶中添加一个元素时，步骤大致是
void insert_to_non_empty_bucket(Node *n, Key k) {
Node *sentinel = table[k];
n->next = sentinel->next;
sentinel->next = n;
}
再次注意，我们不知道也不关心这里的sentinel是前一个bucket的最后一个元素，还是整个链表的sentinel。无论哪种方式，代码都是相同的（这是首先使用哨兵的原因之一）。
然而，当我们将第一个元素添加到一个空桶（并且它不是唯一的 non-empty 桶）时，我们有一个额外的步骤：我们需要更新下一个桶的哨兵指针，指向我们的新节点。否则我们会有两个桶都指向列表哨兵。
void insert_to_empty_bucket(Node *n, Key k) {
Node *sentinel = &list_sentinel; // ie, &_M_before_begin
n->next = sentinel->next;
sentinel->next = n;
// update the *next* bucket in the table
table[n->next->key] = n;
}
最后：在这个实现中，Node没有缓存key，所以没有n->next->key。实际上有一个特征控制这个，但在这种情况下它显然是错误的，这意味着最后一行必须 re-compute 哈希才能更新下一个桶。
注意。澄清一下，当我说 上一个桶 或 下一个桶 时，我只是在谈论列表中的位置，桶以相反的顺序出现他们成为 non-empty 的时间。它与 table 中的位置没有任何关系，也不暗示任何内在顺序。
正如其他人指出的那样，无序映射只是散列的一种形式 table，在 libstdc++ 中基本上作为单个（“全局”）链表实现。另外，还有一个指向此列表的桶数组。重要的是 bucket[i] 中存储的指针不是指向属于这个桶的第一个节点 （根据哈希函数映射），而是 取而代之的是它在全局列表中的前身。原因很明显——当您将一个项目添加到 singly-linked 列表中时，您需要更新其前身。这里，当你需要向某个桶中插入一个元素时，你需要更新这个桶的第一个节点的前驱。
但是，全局链表的第一个节点没有任何前驱。为了使事情统一，有一个哨兵节点扮演这个角色。在libstdc++中，它是一个成员变量_M_before_begin.
假设我们有一个散列 table，其中键 A 和 B 属于 bucket[0]，键 C 属于 bucket[1]。例如，它可能如下所示：
global linked list buckets[]
------------------ ---------
_M_before_begin <-------- bucket[0]
|
v
node_with_key_A
|
v
node_with_key_B <-------- bucket[1]
|
v
node_with_key_C
|
x
现在，当一个新密钥，比如 D，被添加到一个空桶，比如 bucket[2]，libstdc++ 将它插入 at the beginning of the global linked list。
因此本次插入后的情况如下：
global linked list buckets[]
------------------ ---------
_M_before_begin <-------- bucket[2]
|
v
node_with_key_D <-------- bucket[0]
|
v
node_with_key_A
|
v
node_with_key_B <-------- bucket[1]
|
v
node_with_key_C
|
x
注意 bucket[0] 对应于 _M_before_begin needs to be updated 指向的 node_with_key_A。而且，正如其他人再次指出的那样，默认情况下 libstdc++ 不缓存哈希值，因此如何找到 node_with_key_A 的桶索引的唯一选择是触发哈希函数。
请注意，基本上我只是说的和其他人一样，但想添加一些可能有帮助的插图。
这种方法的另一个结果是在查找过程中可能会调用散列函数：https://godbolt.org/z/K6qhWc。原因是某些桶的第一个元素是已知的，但不知道最后一个。因此需要解析节点key的hash函数，在链表遍历时判断节点是否还属于实际的bucket。
以下代码导致对哈希函数的无法解释的调用：
namespace foo {
using Position = tuple <int, int, int>;
std::ostream& operator<<(std::ostream& out, const Position& pos) noexcept{
return out << get<0>(pos) << ", " << get<1>(pos) << ", " << get<2>(pos);
}
struct hashFunc{
std::size_t operator()(const Position& pos) const noexcept{
int res = get<0>(pos) * 17 ^ get<1>(pos) * 11 ^ get<2>(pos);
cout << "@@@ hash function called for key: " << pos
<< ", hash: " << res << endl;
return res;
}
};
template<typename T>
void print_buckets(T&& map) {
auto num_buckets = map.bucket_count();
cout << "------------------------------" << endl;
cout << "NUM BUCKETS: " << num_buckets << endl;
for(size_t i=0; i<num_buckets; ++i) {
auto bucket_size = map.bucket_size(i);
if(bucket_size) {
cout << "BUCKET " << i << " size: " << bucket_size << endl;
}
}
cout << "------------------------------" << endl;
}
}
主要：
using namespace foo;
int main() {
// note: bucket_count specified
unordered_map <Position, std::string, hashFunc> test(10);
auto x = tuple{1,0,0};
auto z = tuple{0,1,0};
auto w = tuple{0,0,1};
cout << "==================================" << endl;
cout << "about to insert: " << x << endl;
test[x] = "hello";
print_buckets(test);
cout << "after insert of: " << x << endl;
cout << "==================================" << endl;
cout << "about to insert: " << z << endl;
test[z] = "hey";
print_buckets(test);
cout << "after insert of: " << z << endl;
cout << "==================================" << endl;
cout << "about to insert: " << w << endl;
test.insert({w, "hello"});
print_buckets(test);
cout << "after insert of: " << w << endl;
cout << "==================================" << endl;
}
输出：
==================================
about to insert: 1, 0, 0
@@@ hash function called for key: 1, 0, 0, hash: 17
------------------------------
NUM BUCKETS: 11
BUCKET 6 size: 1
------------------------------
after insert of: 1, 0, 0
==================================
about to insert: 0, 1, 0
@@@ hash function called for key: 0, 1, 0, hash: 11
@@@ hash function called for key: 1, 0, 0, hash: 17 <= why?
------------------------------
NUM BUCKETS: 11
@@@ hash function called for key: 1, 0, 0, hash: 17 <= why?
BUCKET 0 size: 1
BUCKET 6 size: 1
------------------------------
after insert of: 0, 1, 0
==================================
about to insert: 0, 0, 1
@@@ hash function called for key: 0, 0, 1, hash: 1
@@@ hash function called for key: 0, 1, 0, hash: 11 <= why?
------------------------------
NUM BUCKETS: 11
@@@ hash function called for key: 1, 0, 0, hash: 17 <= why?
BUCKET 0 size: 1
@@@ hash function called for key: 0, 1, 0, hash: 11 <= why?
BUCKET 1 size: 1
BUCKET 6 size: 1
------------------------------
after insert of: 0, 0, 1
==================================
Code （gcc 和 clang 的行为相同）
备注：
1.在构造函数没有 bucket_count 参数的情况下尝试相同的操作，由于重新哈希，对哈希函数的调用变得更加过度。但是在上面的场景中，似乎没有重新散列，也没有冲突。
2。相关，但专门针对 MSVC：Inserting to std::unordered_map calls hash function twice in MSVC++'s STL, bad design or special reason?
我无法解释为什么这样做，但它不适合发表评论，所以我将其留在答案部分。插入元素后，stdlib (10.1.0) 中有两个部分：
__hash_code __code = __h->_M_hash_code(__k);
计算要插入的元素的哈希值__k.
后面这部分代码：
{
// The bucket is empty, the new node is inserted at the
// beginning of the singly-linked list and the bucket will
// contain _M_before_begin pointer.
__node->_M_nxt = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = __node;
if (__node->_M_nxt)
// We must update former begin bucket that is pointing to
// _M_before_begin.
_M_buckets[_M_bucket_index(__node->_M_next())] = __node;
_M_buckets[__bkt] = &_M_before_begin;
}
其中_M_bucket_index为__node->_M_next()计算散列，__node指的是为__k创建的节点。
也许这有助于您或其他人进一步解释它。
可能是std::unordered_map的实现。 hash_value 没有存储到每个节点中。因此，当插入新元素或计算桶大小时，它将re-hash下一个桶中的第一个元素。
您可以尝试使用<tr1/unordered_map>来避免这个问题。示例：
#include <tr1/unordered_map>
using std::tr1::unordered_map;
注意：我不知道 tr1/unordered_map 或 unordered_map 哪个更好。
首先，有几点观察：
无序映射既是散列 table，又是 singly-linked 列表。
参见 here
beginreturns 一个iterator模型 LegacyForwardIterator.向映射中插入条目需要同时更新哈希 table 和链表。
其次，关于这些容器的实施决策的几点说明：
对于singly-linked列表，通常有一个不包含任何数据的哨兵节点（对于
Node<T>，它仍然会有一个T，只是 default-initialized)。我们只需要它的next指针，因为它有助于保持列表操作的规律性（即，我们不必编写 insert-at-the-head 和 insert-after-node 作为不同的特殊情况）。对于散列 tables（假设 linked-list 个桶，因为它是标准所要求的）我们可以使用
Node table[N]（所以每个桶都有自己的哨兵预分配）或Node* table[N].在这种情况下，由于我们实际使用
Node<T>并且不知道T的大小，因此为每个桶存储一个指针似乎是合理的。对于散列 table 这是 也是 一个 singly-linked 列表，使用 per-bucket 是有意义的列为 all-elements 列表（的一部分）。否则我们需要为每个节点存储两个指针，
next_in_bucket和next_in_list.这意味着一个桶指向的“哨兵”（one-before-the-beginning）节点实际上是前一个桶的last节点...除了bucket在列表的最前面，当它真的是整体列表哨兵时。
code中的评论说
/* ... * The non-empty buckets contain the node before the first node in the * bucket. This design makes it possible to implement something like a * std::forward_list::insert_after on container insertion and * std::forward_list::erase_after on container erase * calls. _M_before_begin is equivalent to * std::forward_list::before_begin. Empty buckets contain * nullptr. Note that one of the non-empty buckets contains * &_M_before_begin which is not a dereferenceable node so the * node pointer in a bucket shall never be dereferenced, only its * next node can be.（这段代码中的哨兵是
_M_before_begin）
所以，当我们向already-populated桶中添加一个元素时，步骤大致是
void insert_to_non_empty_bucket(Node *n, Key k) {
Node *sentinel = table[k];
n->next = sentinel->next;
sentinel->next = n;
}
再次注意，我们不知道也不关心这里的sentinel是前一个bucket的最后一个元素，还是整个链表的sentinel。无论哪种方式，代码都是相同的（这是首先使用哨兵的原因之一）。
然而，当我们将第一个元素添加到一个空桶（并且它不是唯一的 non-empty 桶）时，我们有一个额外的步骤：我们需要更新下一个桶的哨兵指针，指向我们的新节点。否则我们会有两个桶都指向列表哨兵。
void insert_to_empty_bucket(Node *n, Key k) {
Node *sentinel = &list_sentinel; // ie, &_M_before_begin
n->next = sentinel->next;
sentinel->next = n;
// update the *next* bucket in the table
table[n->next->key] = n;
}
最后：在这个实现中，Node没有缓存key，所以没有n->next->key。实际上有一个特征控制这个，但在这种情况下它显然是错误的，这意味着最后一行必须 re-compute 哈希才能更新下一个桶。
注意。澄清一下，当我说 上一个桶 或 下一个桶 时，我只是在谈论列表中的位置，桶以相反的顺序出现他们成为 non-empty 的时间。它与 table 中的位置没有任何关系，也不暗示任何内在顺序。
正如其他人指出的那样，无序映射只是散列的一种形式 table，在 libstdc++ 中基本上作为单个（“全局”）链表实现。另外，还有一个指向此列表的桶数组。重要的是 bucket[i] 中存储的指针不是指向属于这个桶的第一个节点 （根据哈希函数映射），而是 取而代之的是它在全局列表中的前身。原因很明显——当您将一个项目添加到 singly-linked 列表中时，您需要更新其前身。这里，当你需要向某个桶中插入一个元素时，你需要更新这个桶的第一个节点的前驱。
但是，全局链表的第一个节点没有任何前驱。为了使事情统一，有一个哨兵节点扮演这个角色。在libstdc++中，它是一个成员变量_M_before_begin.
假设我们有一个散列 table，其中键 A 和 B 属于 bucket[0]，键 C 属于 bucket[1]。例如，它可能如下所示：
global linked list buckets[]
------------------ ---------
_M_before_begin <-------- bucket[0]
|
v
node_with_key_A
|
v
node_with_key_B <-------- bucket[1]
|
v
node_with_key_C
|
x
现在，当一个新密钥，比如 D，被添加到一个空桶，比如 bucket[2]，libstdc++ 将它插入 at the beginning of the global linked list。
因此本次插入后的情况如下：
global linked list buckets[]
------------------ ---------
_M_before_begin <-------- bucket[2]
|
v
node_with_key_D <-------- bucket[0]
|
v
node_with_key_A
|
v
node_with_key_B <-------- bucket[1]
|
v
node_with_key_C
|
x
注意 bucket[0] 对应于 _M_before_begin needs to be updated 指向的 node_with_key_A。而且，正如其他人再次指出的那样，默认情况下 libstdc++ 不缓存哈希值，因此如何找到 node_with_key_A 的桶索引的唯一选择是触发哈希函数。
请注意，基本上我只是说的和其他人一样，但想添加一些可能有帮助的插图。
这种方法的另一个结果是在查找过程中可能会调用散列函数：https://godbolt.org/z/K6qhWc。原因是某些桶的第一个元素是已知的，但不知道最后一个。因此需要解析节点key的hash函数，在链表遍历时判断节点是否还属于实际的bucket。