C - 为什么 boost::hash_combine 是组合散列值的最佳方式？

Question

我在其他帖子中读到这似乎是组合散列值的最佳方式。有人可以分解一下并解释为什么这是最好的方法吗？

 template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

编辑：另一个问题只是询问幻数，但我想了解整个功能，而不仅仅是这一部分。

原文由 keyboard 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

它是“最好的”是有争议的。

“好”，甚至“非常好”，至少在表面上，是很容易的。

 seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

我们假设 seed 是 hasher 或此算法的先前结果。

^= 表示左边的位和右边的位都改变了结果的位。

hasher(v) 被认为是 v 上的一个不错的哈希值。但剩下的就是防御，以防它不是一个像样的哈希。

0x9e3779b9 是一个 32 位值（如果 size_t 可以说是 64 位，它可以扩展到 64 位），包含半个 0 和半个 1。它基本上是通过将特定的无理常数近似为以 2 为底的定点值来完成的 0 和 1 的随机序列。这有助于确保如果哈希返回错误值，我们的输出中仍然会出现 1 和 0 的污点。

(seed<<6) + (seed>>2) 是传入种子的一点洗牌。

想象一下 0x 常量丢失了。想象一下，对于几乎所有传入的 v ，散列器返回常量 0x01000 。现在，种子的每一位都在哈希的下一次迭代中展开，在此期间再次展开出去。

seed ^= (seed<<6) + (seed>>2) 0x00001000 在一次迭代后变为 0x00041400 。然后 0x00859500 。当您重复该操作时，任何设置的位都会“涂抹”在输出位上。最终，左右位碰撞，进位将设置位从“偶数位置”移动到“奇数位置”。

当组合操作在种子操作上递归时，依赖于输入种子值的位会以相对快速且复杂的方式增长。添加原因会带来更多影响。 0x 常量添加了一堆伪随机位，使得无聊的哈希值在组合后占据了更多位的哈希空间。

由于加法，它是不对称的（结合 "dog" 和 "god" 的散列给出不同的结果），它处理无聊的散列值（将字符映射到它们的 ascii 值，这只涉及玩弄少数位）。而且，它相当快。

在其他情况下，加密强度较低的较慢哈希组合可能会更好。我天真地认为，使移位成为偶数和奇数移位的组合可能是一个好主意（但也许加法，它从奇数位移动偶数位，使问题变得不那么成问题：在 3 次迭代后，传入的孤种子位将碰撞并相加并导致进位）。

这种分析的缺点是只需要一个错误就可以使哈希函数变得非常糟糕。指出所有美好的事物并没有多大帮助。所以现在让它变得更好的另一件事是它相当有名并且在一个开源存储库中，我还没有听到有人指出它为什么不好。

原文由 Yakk - Adam Nevraumont 发布，翻译遵循 CC BY-SA 3.0 许可协议