gpt4 book ai didi

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

转载 作者:IT老高 更新时间:2023-10-28 12:42:54 37 4
gpt4 key购买 nike

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

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);
}

编辑:另一个问题只是询问魔数(Magic Number),但我想了解整个功能,而不仅仅是这一部分。

最佳答案

“最好”是有争议的。

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

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

我们假设 seedhasher 的先前结果或者这个算法。

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

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

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

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

想象一下 0x常量丢失了。想象一下哈希器返回常量 0x01000几乎每一个 v传入。现在,种子的每一位都在哈希的下一次迭代中展开,在此期间它再次展开。

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

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

由于加法,它是不对称的(组合 "dog""god" 的哈希值会产生不同的结果),它处理无聊的哈希值(将字符映射到它们的 ascii 值,这只涉及旋转少量位)。而且,速度相当快。

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

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

关于C++ - 为什么 boost::hash_combine 是组合散列值的最佳方式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35985960/

37 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com