如何检索无序映射的冲突？ [英] How to retrieve collisions of unordered map?

问题描述

我有两个元素（6和747）共享它们的键（鸡蛋）。我想找到所有分享关键的元素（让我们来说鸡蛋，但是我会在现实生活中为每一个关键字做这个）。如何做到这一点？

必须有一种方法来从数据结构中获取容器或东西。 。

解决方案

您仍然用密钥的哈希将密钥的值 。但是要回答问题：您可以使用桶迭代器使用 unordered_map 的 bucket（）成员函数： p>

  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< 桶<<桶< ：<<它 - >第一<  - ><<它 - >第二< '\\\
'; 
} 
  

演示

在简单而且大多数正确的术语中，无序容器在接口方面模仿其有序的对应物。这意味着如果映射不会允许您拥有重复的密钥，那么也不会 unordered_map 。

unordered 使用哈希函数加快查找，但如果两个键具有相同的哈希值，他们将不一定具有相同的价值。为了保持行为类似于有序容器， unordered_set 和 unordered_map 只会在元素相等时考虑元素（使用 operator == 或提供的比较器），而不是当他们的哈希值冲突时。

我们假设egg和chicken具有相同的哈希值，并且没有相等的检查。那么以下代码将是正确的：

  unordered_map< string，int> m; 
 m [eggs] = 42; 
 m.insert（make_pair（chicken，0））; //未插入，键已存在
 assert（m [chicken] == 42）; 
  

但是，如果要在同一张地图中允许重复的键，只需使用 unordered_multimap 。

I have two elements (6 and 747) that share their key ("eggs"). I want to find all the elements that share a key (let's say "eggs", but I would in real life do that for every key). How to do that?

There must be a way to get a container or something back from the data structure . . .

解决方案

You're still mistaking key's value with key's hash. But to answer question as asked: you can use unordered_map's bucket() member function with bucket iterators:

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

In simple and mostly correct terms, unordered containers imitate their ordered counterparts in terms of interface. That means that if a map will not allow you to have duplicate keys, then neither will unordered_map.

unordered do employ hashing function to speed up the lookup, but if two keys have the same hash, they will not necessarily have the same value. To keep the behaviour similar to the ordered containers, unordered_set and unordered_map will only consider elements equal when they're actually equal (using operator== or provided comparator), not when their hashed values collide.

To put things in perspective, let's assume that "eggs" and "chicken" have the same hash value and that there's no equality checking. Then the following code would be "correct":

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

But if you want allow duplicate keys in the same map, simply use unordered_multimap.

这篇关于如何检索无序映射的冲突？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！