std::unordered_set 中的 KeyEqual 有什么用？

Question

std::unordered_set 中的第 3 个参数 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 实现。所以我想知道我是否做对了。

Answer 1

但是如果我们发生哈希冲突怎么办？

图片演示了两个不同元素恰好具有相等哈希值的情况。因此，哈希值可能不是在哈希处理时是唯一的。

引用 std::unordered_set 的 ref:

Internally, the elements in the unordered_set are not sorted in any particular order, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their values (with a constant average time complexity on average).

所以一个桶可以有多个元素！这两个元素会有相同的哈希值，不保证唯一！

唯一保证唯一的是 key!

Answer 2

很简单，集合需要知道两个键是否相等。 KeyEqual 是这样做的机制。

请记住，比较不相等的两个键可能散列为相同的值，并且集合需要能够检查这一点。

Answer 3

不同的值不一定有不同的哈希值。例如，std::string 个对象实际上有无限多个，但 std::hash<std::string>()(s) 的结果只有 2^N 个 std::size_t 个对象，所以一些 "hash collisions" 是不可避免的，尽管算法试图让它们不太可能。

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

Answer 4

让我们举个例子，一组 ints 带有一个散列函数，它只做一个简单的 mod % 操作

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

std::unordered_set 中的 KeyEqual 有什么用？

What is KeyEqual in std::unordered_set for?

c++

std

unordered-set

c++-standard-library