std::unordered_set中的KeyEqual是用来做什么的？

Question

在 std::unordered_set 中，第三个参数 KeyEqual 的目的是什么？哈希唯一性不足以满足吗？

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

如果这个问题听起来很幼稚，我很抱歉。我正在从Python/PHP转移到C++ :)

目前我的KeyEqual实现总是复制Hash实现。所以我想知道我是否做得正确。

- spajak

---

听说过哈希碰撞吗？如果两个对象产生相同的哈希值，那么相等谓词将被用来判断它们是否相等。 - Praetorian

哈希唯一性足够吗？如果您的键是int，而哈希函数是[](int i){ return i % 10; }呢？ - Ryan Haining

unordered_set 的文档有什么问题？前面的评论中提到哈希冲突是第一原因，但几乎所有的 STL 容器都允许自定义比较操作。如果您需要按照自己的方式比较键或者使用没有预先存在比较运算符的键类型，该怎么办呢？ - mvidelgauz

@mvidelgauz，FYI，cplusplus.com存在一些问题，请使用cppreference代替。 - jaggedSpire

@jaggedSpire 谢谢你提供的信息。我之前不知道这些问题，我会去了解一下，但通常我会同时使用两种方法（在某些情况下还会使用其他方法）。 - mvidelgauz

Answer 1

例如，假设有一组使用简单的模 % 运算符进行哈希的 int 数组。

struct IntMod {
    constexpr std::size_t operator()(int i) const { return i % 10; }
};

std::unordered_set<int, IntMod> s;

这很容易导致哈希冲突，当发生这种情况时，您需要能够比较键来确定是否已经存在一个键。

s.insert(25);  // hash == 5
s.insert(35);  // hash == 5
assert(*s.find(25) == 25);  // both 25 and 35 are present despite the same hash
assert(*s.find(35) == 35);

如果我们添加一个只使用哈希函数的KeyEqual（就像您建议的那样默认情况下），它在第二次插入时会出现问题。

struct IntEq {
  constexpr bool operator()(int a, int b) const {
    return IntMod{}(a) == IntMod{}(b);
  }
};

std::unordered_set<int, IntMod, IntEq> s;
s.insert(25);  // hash == 5
s.insert(35);  // hash == 5
assert(*s.find(25) == 25);
assert(*s.find(35) == 35);  // now this fails. s.find(35) returns iterator to 25

- Ryan Haining

---

s.insert(35) 应该失败或替换旧元素。但是我可能在想不同的容器 :) - spajak

@spajak它只是认为35已经存在。你认为它应该如何“失败”？ - Ryan Haining

我所说的“失败”是指抛出异常。 - spajak

Answer 2

但如果我们有哈希冲突怎么办？

这张图片展示了两个不同元素的哈希值相等的情况。因此，在哈希过程中，哈希值可能不是唯一的。

---

引用 std::unordered_set 的参考文献：

在内部，unordered_set 中的元素没有按任何特定顺序排序，而是根据它们的哈希值组织成桶，以便通过它们的值直接快速访问单个元素（平均时间复杂度为常数）。

因此，一个桶可以有多个元素！这两个元素将具有相同的哈希值，但不能保证哈希值是唯一的！

---

唯一保证的是键是唯一的！

- gsamaras

---

我理解碰撞的概念。但是如果我不关心碰撞怎么办？如果我只想说“我的哈希值是100％独特的”，如果我尝试设置相同的元素，会给我异常或替换这个元素？也许这是另一个问题... - spajak

是的@spajak，这是另一个问题。容器不会为您提供此功能，因为它没有设计成这样。我的意思是它使用的哈希策略允许冲突，这就是为什么它需要“键”来确定相等性。您将不得不创建自己的容器（它将继承自STL），如果需要，将抛出异常。我编辑了您的问题，希望您不介意。 :) - gsamaras

Answer 3

不同的值不一定有不同的哈希值。例如，有无限数量的std::string对象，但对于std::hash<std::string>()(s)的结果只有2^N个std::size_t对象，因此一些“哈希碰撞”是不可避免的，尽管算法试图使它们不太可能发生。

因此，std::unordered_set和std::unordered_map需要一种方法来测试元素是否相等或不相等，即使它们的哈希值相等。

- aschepler

Answer 4

简单来说，集合需要知道两个键是否相等。 KeyEqual 是实现这一机制的方法。

请记住，两个不相等的键可能会哈希到相同的值，因此集合需要能够检查这一点。

- NPE