c++ - 优于 C++ unordered_set 的哈希函数

Question

我希望通过 C++ 实现哈希函数 std::unordered_set<char> .我最初尝试使用 boost::hash_range:

namespace std
{
template<> struct hash<unordered_set<char> >
size_t operator(const unordered_set<char> &s)(
{
    return boost::hash_range(begin(s), end(s))
};
}

但后来我意识到因为集合是无序的，所以迭代顺序不稳定，因此散列函数是错误的。对我来说有哪些更好的选择？我想我可以 std::set而不是 std::unordered_set ，但是仅仅因为它更容易散列而使用有序集似乎……是错误的。

Answer 1

这里提出了一个非常相似的问题，尽管是在 C# 中:

Hash function on list independant of order of items in it

在那里，Per 给出了一个很好的独立于语言的答案，应该让你走上正确的轨道。简而言之，对于输入

x₁, …, x_n

你应该把它映射到

f(x₁) op … op f(x_n)

在哪里

• f 是单个元素(在您的情况下为整数)的良好哈希函数
• op 是交换运算符，例如 xor 或 plus

散列整数起初可能毫无意义，但您的目标是使两个相邻的整数彼此不同，以便与 op 结合时不会产生相同的结果。例如如果您使用 + 作为运算符，您希望 f(1)+f(2) 给出与 f(0)+f(3) 不同的结果。

如果标准哈希函数不是 f 的理想候选者并且您找不到，请查看链接的答案以获取更多详细信息...