时间戳

首页 > 解决方案 > c ++找不到元素是具有相同哈希的unordered_set

c++ - c ++找不到元素是具有相同哈希的unordered_set

问题描述

我有矢量的 unordered_set < int > 的自定义散列函数：

struct VectorHash {
int operator()(const vector<int> &V) const {
    int hsh=V[0] + V[1];
    return  hash<int>()(hsh);
}};

对于两个这样的向量，我有相同的哈希等于 3：

vector<int> v1{2,1};
vector<int> v2{1,2};

但是，当我尝试在 unordered_set 中插入第一个向量 v1，然后通过哈希检查我的 unordered_set 中是否具有与 v2 相同的向量时，我得到了错误：

std::unordered_set<std::vector<int>, VectorHash> mySet;
mySet.insert(v1); 

if(mySet.find(v2) == mySet.end())
    cout << "didn't find" << endl;

Output:  "didn't find"

我假设如果 unordered_set 中的两个元素具有相同的哈希值，那么如果我的 unordered_set 中有 v1 find，则当我尝试查找 v2 时，方法应该返回 true。但事实并非如此。

谁能解释我的推理有什么问题？

标签： c++unordered-set

解决方案

哈希不是一切，您在这里看到的是碰撞。

两者std::vector<int>在这里具有相同的哈希值，但是在计算出哈希之后，std::unordered_map实际上会使用operator==检查元素是否相等来检查元素是否相等，在这种情况下会失败，并且无法找到元素。

碰撞在 HashMaps 中是很正常的事情，如果不提供 custom ，你可以在这里做很多事情operator==。

推荐阅读