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。所以我想知道我是否做对了。
最佳答案
让我们举个例子,一组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
关于c++ - std::unordered_set 中的 KeyEqual 有什么用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39107488/