Ami*_*rsh 17 c++ unordered-map
以下代码导致对哈希函数的无法解释的调用：
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
==================================
代码 （gcc 和 clang 的行为相同）
笔记：
1.bucket_count在构造函数不带参数的情况下尝试相同的方法，由于rehash，对hash函数的调用变得更加过度。但在上面的场景中，似乎没有重新哈希，也没有冲突。
2. 相关，但特别是在 MSVC 上：插入到 std::unordered_map 在 MSVC++ 的 STL 中两次调用散列函数，糟糕的设计还是特殊原因？
首先，有几个观察：
无序映射既是哈希表，又是单向链表。
见这里是begin回报的iterator哪些车型LegacyForwardIterator。
将条目插入映射需要更新哈希表和链表。
其次，关于这些容器的实现决策的几点说明：
对于单链表，通常有一个不包含任何数据的哨兵节点（对于诸如 之类的东西Node<T>，它仍然会有一个T，只是默认初始化）。我们只需要它的next指针，因为它有助于保持列表操作的规则性（即，我们不必将insert-at-the-head和insert-after-node作为不同的特殊情况编写）。
对于哈希表（假设链表存储桶，因为标准要求它），我们可以使用Node table[N]（因此每个存储桶都有自己的预分配的哨兵）或Node* table[N].
在这种情况下，由于我们实际上正在使用Node<T>并且不知道 的大小T，因此为每个存储桶存储一个指针似乎是合理的。
对于一个哈希表，其是还单链接列表，是有意义的使用每桶列表作为（部分）的所有元素列表。否则我们需要为每个节点存储两个指针，next_in_bucket并且next_in_list.
这意味着一个bucket指向的“哨兵”（one-before-the-beginning）节点实际上是前一个bucket的最后一个节点……除了列表前面的bucket，当它真的是总名单哨兵。
代码中的注释说
/* ...
* 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在这段代码中）
所以，当我们向一个已经填充的桶中添加一个元素时，步骤大致是
void insert_to_non_empty_bucket(Node *n, Key k) {
Node *sentinel = table[k];
n->next = sentinel->next;
sentinel->next = n;
}
再次注意，我们不知道也不关心这里的哨兵是前一个桶的最后一个元素，还是整个列表哨兵。无论哪种方式，代码都是相同的（这是首先使用哨兵的原因之一）。
然而，当我们将第一个元素添加到一个空桶（它不是唯一的非空桶）时，我们有一个额外的步骤：我们需要更新下一个桶的哨兵指针，以指向我们的新节点。否则我们将有两个桶都指向列表哨兵。
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. 实际上有一个 trait 控制这个，但在这种情况下它显然是错误的，这意味着最后一行必须重新计算哈希才能更新下一个存储桶。
注意。只是为了澄清，当我说上一个桶或下一个桶时，我只是在谈论列表中的位置，其中桶的出现顺序与它们变为非空时的顺序相反。它与表中的位置没有任何关系，也没有暗示任何内在顺序。
正如其他人指出的那样，无序映射只是哈希表的一种形式，在 libstdc++ 中基本上实现为单个（“全局”）链表。另外，还有一个指向此列表的存储桶数组。重要的是，存储的指针bucket[i] 并不指向属于该桶的第一个节点（根据哈希函数映射），而是指向其在全局链表中的前一个节点。原因很明显 \xe2\x80\x94 当您将一个项目添加到单链表中时，您需要更新其前任。这里，当需要向某个桶中插入元素时，需要更新该桶的第一个节点的前驱节点。
然而，全局链表的第一个节点没有任何前驱。为了使事情统一，有一个哨兵节点扮演这个角色。在libstdc++中，它是一个成员变量_M_before_begin。
假设我们有一个哈希表，其中包含属于 的键A和属于 的键。例如，它可能如下所示：Bbucket[0]Cbucket[1]
global linked list buckets[]\n------------------ ---------\n\n_M_before_begin <-------- bucket[0]\n |\n v\nnode_with_key_A \n |\n v\nnode_with_key_B <-------- bucket[1]\n |\n v\nnode_with_key_C\n |\n x\n现在，当一个新键（例如）D被添加到一个空存储桶（例如）中时bucket[2]，libstdc++ 会将其插入到全局链表的开头。
因此，这次插入后的情况如下：
\nglobal linked list buckets[]\n------------------ ---------\n\n_M_before_begin <-------- bucket[2]\n |\n v\nnode_with_key_D <-------- bucket[0]\n |\n v\nnode_with_key_A \n |\n v\nnode_with_key_B <-------- bucket[1]\n |\n v\nnode_with_key_C\n |\n x\n请注意，bucket[0]与 所node_with_key_A指向的相对应_M_before_begin 需要更新。而且，正如其他人再次指出的那样，libstdc++ 默认情况下不缓存哈希值，因此唯一的选择是如何找到存储桶索引node_with_key_A是触发哈希函数。
请注意，基本上我只是说与其他人相同，但想添加一些可能有帮助的插图。
\n这种方法的另一个结果是在查找过程中可能会调用哈希函数： https: //godbolt.org/z/K6qhWc。原因是某些存储桶的第一个元素已知，但最后一个元素未知。因此，需要解析节点键的哈希函数，以在链表遍历过程中找出节点是否仍然属于实际的桶。
\n| 归档时间： |
|
| 查看次数： |
326 次 |
| 最近记录： |