xor
是一种在哈希时使用的危险默认函数。它比and
和or
好,但这并不说太多。
xor
是对称的,因此元素的顺序丢失了。所以"bad"
将与"dab"
结合哈希相同。
xor
将成对相同的值映射为零,并且您应该避免将“常见”值映射为零:
因此,(a,a)
被映射为0,(b,b)
也被映射为0。由于此类对几乎总是比随机性暗示的更常见,因此在零处发生的碰撞比应有的要多得多。
由于这两个问题,xor
最终成为一个看起来还不错但经过进一步检查会变得不行的哈希组合器。
在现代硬件上,加法通常与xor
的速度差不多(诚然,它可能需要更多的功率来完成这项工作)。添加的真值表在相关位上与xor
类似,但当两个值都为1时,它还会将一个位发送到下一个位。这意味着它擦除的信息更少。
因此,hash(a) + hash(b)
比hash(a) xor hash(b)
更好,如果a==b
,则结果为hash(a)<<1
而不是0。
这仍然是对称的;因此,"bad"
和"dab"
得到相同的结果仍然是个问题。我们可以以适度的代价打破这个对称性:
hash(a)<<1 + hash(a) + hash(b)
也被称为 hash(a)*3 + hash(b)
。(如果使用移位方案,则建议计算并存储一次 hash(a)
)。选择任意奇数常量代替 3
,将“k
位”无符号整数双射到自身,因为无符号整数的映射在模数为某个k
的数学下取模于2^k
,而任何奇数常量都与2^k
互质。
对于更高级的版本,我们可以查看 boost::hash_combine
,它实际上是:
size_t hash_combine( size_t lhs, size_t rhs ) {
lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
return lhs;
}
这里我们将一些偏移版本的lhs
与常数相加(基本上是随机的0
和1
- 特别地,它是32位定点小数的黄金比例倒数),并进行一些加法和异或操作。这样可以破坏对称性,并在输入的哈希值很差时引入一些“噪音”(例如,假设每个组件都哈希为0-上述方法可以很好地处理,每次组合后生成一堆1
和0
)。我的简单的3*hash(a)+hash(b)
在这种情况下只会输出0
)。
将此扩展到64位(使用pi的扩展作为我们的64位常数,因为它在64位时是奇数):
size_t hash_combine( size_t lhs, size_t rhs ) {
if constexpr (sizeof(size_t) >= 8) {
lhs ^= rhs + 0x517cc1b727220a95 + (lhs << 6) + (lhs >> 2);
} else {
lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
}
return lhs;
}
(对于那些不熟悉C/C++的人来说,size_t
是一个无符号整数值,它足以描述内存中任何对象的大小。在64位系统上,它通常是一个64位无符号整数。在32位系统上,它是一个32位无符号整数。)