如何检索无序地图的碰撞？

Question

我有两个共享密钥 ("eggs") 的元素（6 和 747）。我想找到共享一个键的所有元素（比方说 "eggs"，但在现实生活中我会为每个键都这样做）。怎么做？

一定有办法从数据结构中取回容器或其他东西。 . .

Answer 1

您仍然将键的值误认为是键的散列。但要按要求回答问题：您可以将 unordered_map 的 bucket() 成员函数与桶迭代器一起使用：

std::unordered_map<int,int,dumbest_hash> m;
m[0] = 42;
m[1] = 43;

size_t bucket = m.bucket(1); 

for(auto it = m.begin(bucket), e = m.end(bucket); it != e; ++it) {
    cout << "bucket " << bucket << ": " << it->first << " -> " << it->second << '\n';
}

demo

用简单且基本正确的术语来说，无序容器在接口方面模仿有序容器。这意味着如果 map 不允许您拥有重复的键，那么 unordered_map 也不会。

unordered确实使用哈希函数来加速查找，但是如果两个键具有相同的哈希值，则它们不一定具有相同的值。为了保持与有序容器相似的行为，unordered_set 和 unordered_map 只会在元素实际相等（使用 operator== 或提供的比较器）时才考虑元素相等，而不是当它们的哈希值发生冲突时.

为了正确看待事情，我们假设 "eggs" 和 "chicken" 具有相同的散列值并且没有进行相等性检查。那么下面的代码就是 "correct":

unordered_map<string, int> m;
m["eggs"] = 42;
m.insert(make_pair("chicken", 0)); // not inserted, key already exists
assert(m["chicken"] == 42);

但是如果你想在同一个映射中允许重复键，只需使用unordered_multimap。

Answer 2

无序映射没有共享键的元素。

无序多图可以。

使用 umm.equal_range(key) 获取 pair 迭代器，描述映射中与给定键匹配的元素。

但是，请注意 "collision" 在谈论散列容器时通常指的是具有相同散列键的元素，而不是相同的键。

此外，考虑使用 unordered_map<key, std::vector<value>> 而不是多图。

如何检索无序地图的碰撞？

How to retrieve collisions of unordered map?

c++

hash

stl

hash-collision

data-structures