c++ - 与 std::hash 的意外冲突

Question

我知道将无限数量的字符串散列到 32b int 中必然会产生冲突，但我希望散列函数能提供一些不错的分布。

这两个字符串有相同的哈希值是不是很奇怪？

size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
//hash0 == hash1

我知道我可以使用 boost::hash<std::string>或其他人，但我想知道 std::hash 有什么问题.我用错了吗？我不应该以某种方式“播种”它吗？

Answer 1

您对 std::hash 的使用没有任何问题.问题是特化 std::hash<std::string>由与 Visual Studio 2010 捆绑的标准库实现提供的仅使用字符串字符的子集来确定哈希值(可能是出于性能原因)。巧合的是，14 个字符的字符串的最后一个字符不属于该集合，这就是为什么两个字符串产生相同的哈希值的原因。

据我所知，这种行为符合标准，要求只有多次调用具有相同参数的哈希函数必须始终返回相同的值。然而，散列冲突的概率应该是最小的。 VS2010 实现完成了强制部分，但没有考虑到可选部分。

详见头文件xfunctional中的实现(从我的拷贝中的第 869 行开始)和 C++ 标准的第 17.6.3.4 节(latest public draft)。

如果你绝对需要一个更好的字符串散列函数，你应该自己实现它。实际上是not that hard .