为什么XOR是组合哈希的默认方法？

Question

假设您有两个哈希H(A)，H(B)并且想要将它们组合在一起。我已经读到，将两个散列组合在一起的一种好方法是使用XOR它们，例如XOR( H(A), H(B) )。这些哈希函数准则在此简要地介绍了我找到的最佳解释：对两个具有大致随机分布的数字进行异或运算会导致另一个仍具有大致随机分布*的数字，但现在取决于这两个值。 ... *在要组合的两个数字的每一位，如果两位相等，则输出0，否则为1。换句话说，在50％的组合中，将输出1。因此，如果两个输入位各自有大约50-50的可能性为0或1，那么输出位也是如此。您能解释为什么XOR应该是用于组合哈希函数（而不是OR或AND等）的默认操作的直觉和/或数学方法吗？

Answer 1

xor是在散列时使用的危险默认函数。它比and和更好or，但这并不多。

xor是对称的，因此元素的顺序丢失了。因此，"bad"哈希组合与相同"dab"。

xor 将成对的相同值映射为零，并且应避免将“公共”值映射为零：

因此，(a,a)被映射为0，(b,b)也被映射为0。由于这样的对几乎总是比随机性所暗示的更为普遍，因此最终在零处产生的碰撞要多得多。

遇到这两个问题，xor最终是一个哈希组合器，看起来表面上还算不错，但经过进一步检查后才发现。

在现代硬件上，添加速度通常与添加速度差不多xor（公认的，它可能会使用更多功能来实现此目的）。加法运算的真值表与所xor讨论的位类似，但是当两个值均为1时，它还会向下一位发送一个位。这意味着它将删除较少的信息。

因此，与if相比，结果hash(a) + hash(b)要好于0。hash(a) xor hash(b)a==bhash(a)<<1

这仍然是对称的。所以"bad"并"dab"得到同样的结果仍然是一个问题。我们可以以适度的成本打破这种对称性：

hash(a)<<1 + hash(a) + hash(b)

又名hash(a)*3 + hash(b)。（hash(a)如果使用班次解决方案，建议一次计算并存储）。而不是任何奇数常量，3将双射地将一个“ k-bit”无符号整数映射到自身，因为无符号整数的映射对2^k某些对象而言是数学模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;

}

在这里，我们将一些seed带有常数的移位版本加在一起（基本上是随机的0s和1s，特别是32位固定点分数的黄金分割率的倒数），加上一些加法和一个xor。这打破对称，并介绍了一些“噪声”，如果传入的散列值是差（即，每一个部件散列想象到0 -上述处理得很好，产生的涂抹1和0。之后的每个结合我的幼稚3*hash(a)+hash(b)简单地一个输出0中这种情况）。

（对于不熟悉C / C ++的人，a size_t是一个无符号整数值，该值足以描述内存中任何对象的大小。在64位系统上，它通常是64位无符号整数。在32位系统上，一个32位无符号整数。）

Answer 2

Xor可能是组合哈希的“默认”方式，但是Greg Hewgill的答案也表明了它有陷阱的原因：两个相同哈希值的Xor为零。在现实生活中，存在相同的散列比人们预期的更常见。然后，您可能会发现在这些（不是那么少见的）极端情况下，所得到的组合哈希值始终相同（零）。哈希冲突比您预期的要频繁得多。

在一个人为的示例中，您可能正在组合来自您管理的不同网站的用户的哈希密码。不幸的是，大量用户重复使用了他们的密码，并且产生的哈希值中令人惊讶的比例为零！