c++ - 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 impl。所以我想知道我是否做对了。

Answer 1

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

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

std::unordered_set<int, IntMod> s;

这很容易导致哈希冲突，当发生这种情况时，您需要能够比较 key 以了解 key 是否已经存在。

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