c++ 找不到元素是 unordered_set 具有相同的散列

Question

我有 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 方法应该 return 为真，当我尝试找到 v2。但事实并非如此。

有人能解释一下我的推理有什么问题吗？

Answer 1

I assume that if two elements in unordered_set have the same hash then if I have v1 in my unordered_set, find method should return true, when I try to find v2.

该假设不正确，相同的哈希值并不意味着对象相等。

unordered_map 使用相等谓词来确定键相等性（默认 std::equal_to）。

Answer 2

哈希不是一切，您在这里看到的是一种冲突。

这里两个std::vector<int>的hash值是一样的，但是hash计算出来后，std::unordered_map实际上会用operator==来检查元素是否相等，在这种情况下失败，无法找到元素。

冲突在 HashMaps 中是很正常的事情，如果不提供自定义 operator==。

Answer 3

如果您恰好需要唯一标识符但不自动比较值，您可以使用 (unordered_)map<int, vector<int>> 并使用该 VectorHash 函数生成 int 键：

unordered_map<int, vector<int>> map;

int key=V[0] + V[1]
map[key] = V;

Answer 4

你还需要为 unordered_set 提供一个比较器，如果你想让这两个元素匹配，你可以按照以下方式做一些事情：

struct VectorComparator {
  bool operator()(const std::vector<int> & obj1, const std::vector<int> & obj2) const
  {
    if ((obj1[0] + obj1[1]) == (obj2[0] + obj2[1]))
      return true;
    return false;
  }
};

并像这样创建您的 unordered_set

std::unordered_set<std::vector<int>, VectorHash, VectorComparator> mySet;

那么你应该得到你期望的结果

c++ 找不到元素是 unordered_set 具有相同的散列

c++ cannot find element is unordered_set with the same hash

c++

unordered-set