如何在 unordered_map 中发生碰撞时获取链式值？

Question

如果 c++ 中的 unordered_map 使用链接作为冲突解决。如何访问链式值/链表？

    unordered_map<int,int> diff;
    //collision : inserting two entries with same key 1
    diff.insert(make_pair(1, 7));
    diff.insert(make_pair(1, 26));

    cout<<diff[1];

输出只是 7 假设在 unordered_map 中使用链接进行碰撞，我怎样才能得到 7 和 26 resolution.What 在这种情况下 unordered_map 的行为是什么？

Answer 1

如果您希望每个键有多个值，则需要使用 unordered_multimap。您当前的代码没有存储 1 的第二个值。

https://en.cppreference.com/w/cpp/container/unordered_multimap

不过您将无法使用 operator[]。

Answer 2

第二次使用已存在的键插入将失败。

引自std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::insert - cppreference.com：

insert_return_type insert(node_type&& nh); (7) (since C++17)

7) If nh is an empty node handle, does nothing. Otherwise, inserts the element owned by nh into the container, if the container doesn't already contain an element with a key equivalent to nh.key().

7) Returns an insert_return_type with the members initialized as follows: if nh is empty, inserted is false, position is end(), and node is empty. Otherwise if the insertion took place, inserted is true, position points to the inserted element, and node is empty. If the insertion failed, inserted is false, node has the previous value of nh, and position points to an element with a key equivalent to nh.key().

Answer 3

这个问题表明了对链接的使用方式以及人们通常所说的碰撞的含义的误解。

在您的示例代码中：

unordered_map<int,int> diff;
//collision : inserting two entries with same key 1
diff.insert(make_pair(1, 7));
diff.insert(make_pair(1, 26));

两次插入具有相同的键，因此它们映射到散列中的同一个桶 table。第一个 insert 发现桶是空的，所以 {1,7} 从那个桶链接。第二次，insert 函数从桶中找到已经插入的键 1，并放弃插入。

虽然你不应该称之为“冲突”：它是两个插入调用的相同键，它被哈希函数哈希并映射到哈希中的“桶”table，但是同一个键将总是映射到同一个桶——这是散列函数和tables.

的固有属性

冲突是指两个 不同的 键映射到同一个存储桶。

哈希table支持冲突：它们允许您存储许多{key,value}对，这些对具有不同的键，这些键在同一个桶中发生碰撞。

unordered_map 不支持 重复键：即具有相同键的多个 {key, value} 对。

The output is just 7 How can I get both 7 and 26 assuming chaining is used in unordered_map for collision resolution.What is the behavior of unordered_map in such scenarios?

不能同时将{1,7}和{1,26}这两个键值对放入同一个unordered_map中。要实际允许同一个键与多个值相关联 - 因此 insert 不会搜索存储桶的链式元素以查看键是否已插入并在找到时中止 - 您必须使用 unordered_multiset相反。

当使用 unordered_multiset 时，有一些合乎逻辑的理由可以在插入多个相同键值时将其称为冲突，因为两对都不能在第一个链接节点的列表——一个节点必须将另一个节点推开或排到队列的后面——可以这么说，就像那个桶上的不同键冲突一样。尽管如此，为了避免混淆，我还是建议您保留“碰撞”术语来表示差异键冲突。

如何在 unordered_map 中发生碰撞时获取链式值？

How to get chained values in case of Collision in unordered_map?

c++

hash

unordered-map

data-structures