std::unordered_set 中的 KeyEqual 有何用途？

Question

第三个参数的用途是KeyEqual什么std::unordered_set？哈希唯一性还不够吗？

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总是重复Hashimpl。所以我想知道我是否做得正确。

Answer 1

我们以一组int带有哈希函数的 s 为例，该函数仅执行简单的 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

Answer 2

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

该图演示了两个不同 元素碰巧具有相同哈希值的情况。因此，在进行散列时，散列值可能不唯一。

引用以下参考文献std::unordered_set：

在内部，unordered_set 中的元素不按任何特定顺序排序，而是根据其哈希值组织到存储桶中，以允许直接通过其值快速访问各个元素（平均时间复杂度恒定）。

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

唯一保证独一无二的就是钥匙！