为什么XOR是哈希合并的默认方式？
假设你有两个哈希H(A)和H(B) ，你想合并它们。 我已经读过，将两个哈希合并的一个好方法就是将它们XOR ，例如XOR( H(A), H(B) ) 。
我已经find了最好的解释，在这里简要地谈谈这些散列函数的指导方针 ：
对两个数字进行大致随机分布的结果，导致另一个数字仍然具有大致随机分布*，但现在取决于这两个值。
…
*在两个数字的每一位进行组合，如果两个位相等，则输出0，否则为1.换句话说，在50％的组合中，将输出1。 所以如果两个input比特各自有0或1的几率，那么输出比特也是如此。
你能解释为什么XOR应该成为哈希函数（而不是OR或AND等）的默认操作的直觉和/或math吗？
假设均匀随机（1位）input，AND函数输出概率分布为75％ 0和25％ 1 。 相反，OR为25％ 0和75％ 1 。
XOR函数为50％ 0和50％ 1 ，因此它可以组合均匀的概率分布。
通过写出真值表可以看出这一点：
a | b | a AND b ---+---+-------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 a | b | a OR b ---+---+-------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 1 a | b | a XOR b ---+---+-------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0
练习：两个1位inputa和b有多less个逻辑函数具有统一的输出分布？ 为什么XOR最适合您的问题中陈述的目的？
xor是哈希时使用的一个危险的默认函数。 这比和和还好，但这并不多。
xor是对称的，所以元素的顺序是丢失的。 所以"bad"将哈希组合为"dab"相同。
异或映射相同的值为零，你应该避免映射“公共”值为零：
所以(a,a)被映射为0，而(b,b)也被映射为0.由于这样的对比随机性可能意味着更为常见，所以最终在零处碰撞的次数比您应该达到的要多得多。
有了这两个问题，xor最终变成了一个散列组合器，看起来在表面上看起来不错，但在进一步的检查之后却没有。
在现代的硬件上，通常和xor的速度一样快（不过可以肯定的是，它可能会使用更多的功率来实现这个function）。 添加的真值表与所讨论的位上的xor类似，但是当两个值均为1时，它也会向下一位发送一个位。这会消除较less的信息。
所以hash(a) + hash(b)更好，如果a==b ，结果是hash(a)<<1而不是0。
这仍然是对称的。 我们可以用适度的成本来打破这种对称性：
hash(a)<<1 + hash(a) + hash(b)
又名hash(a)*3 + hash(b) 。 （计算hash(a)一次，如果使用移位解决scheme，则build议存储）。 任何奇数常量而不是3会将size_t （或k位无符号常量）双射映射到自身，因为无符号常量上的映射对于某个k是math模2^k k ，任何奇数常数都与2^k相对。
对于更boost::hash_combine版本，我们可以检查boost::hash_combine ，它是有效的：
size_t hash_combine( size_t lhs, size_t rhs ) { lhs^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2); return lhs; }
在这里，我们将带有常数（基本上是随机0 s和1 s – 特别是黄金比例为32比特的固定点分数的倒数）的seed一些移位版本加在一起，并加上一个xor。 这破坏了对称性，并且如果传入的散列值很差（即，想象每个分量散列为0），就会引入一些“噪声” – 上面的处理很好，在每次合并之后产生1和0的拖尾。 0 ）。
对于那些不熟悉C / C ++的人来说， size_t是一个无符号的整数值，它的大小足以描述内存中任何对象的大小。 在64位系统上，它通常是一个64位无符号整数。 在32位系统上，一个32位无符号整数。
尽pipe具有方便的比特混合特性，XOR 不是由于其交换性而将哈希合并的好方法。 考虑如果将{1,2，…，10}的排列存储在10元组哈希表中会发生什么情况。
一个更好的select是m * H(A) + H(B) ，其中m是一个很大的奇数。
信用：上面的组合是鲍勃jenkins的一个小费。
Xor可能是组合哈希的“默认”方法，但是Greg Hewgill的回答也显示了为什么它有其缺陷：两个相同哈希值的异或为零。 在现实生活中，相同的哈希比人们所期望的更普遍。 您可能会发现，在这些（并不罕见）的angular落案例中，所得到的组合散列总是相同的（零）。 哈希碰撞比您期望的要多得多。
在一个人为的例子中，您可能将来自您pipe理的不同网站的用户的散列密码组合在一起。 不幸的是，大量的用户重用他们的密码，并且得到的哈希值的比例惊人的是零！
有些东西我想明确指出其他谁find这个网页。 AND和OR限制BlueRaja的输出 – Danny Pflughoe试图指出，但可以更好地定义：
首先我要定义两个简单的函数，我将用它来解释这个：Min（）和Max（）。
Min（A，B）将返回A和B之间较小的值，例如：Min（1，5）返回1。
Max（A，B）将返回A和B之间较大的值，例如：Max（1，5）返回5。
如果给出： C = A AND B
那么你可以发现C <= Min(A, B)我们知道这一点，因为没有什么可以和A或B的0位使它们变成1。 所以每个零位都保持一个零位，每一位都有机会变成一个零位（因此一个较小的值）。
用： C = A OR B
反之亦然： C >= Max(A, B)由此我们看到AND函数的必然结果。 任何一个已经是一个的位都不能被或为零，所以它保持一个，但是每个零位有机会成为一个，因此是一个更大的数字。
这意味着input的状态对输出施加限制。 如果你和90的任何东西，你知道输出将等于或小于90，无论其他值是什么。
对于XOR，不存在基于input的隐含限制。 在特殊情况下，你可以发现，如果你用255来异或一个字节，你会得到相反的结果，但是可以输出任何可能的字节。 每一位都有机会根据另一个操作数中的相同位来改变状态。
如果您对具有偏置input的随机input进行XOR ，则输出是随机的。 AND和OR也是如此。 例：
00101001 XOR 00000000 = 00101001 00101001和00000000 = 00000000 00101001或11111111 = 11111111
正如@Greg Hewgill所提到的，即使两个input都是随机的，使用AND或OR也会导致输出偏差。
我们之所以用XOR来处理更复杂的事情，是因为没有必要： XOR完美运行，而且非常快速。
java.util.Arrays中各种版本的hashCode()的源代码是实用的常规使用散列algorithm的很好的参考。 他们很容易理解并翻译成其他编程语言。
粗略地说，大多数属性的hashCode()实现遵循这种模式：
public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; }
您可以search其他的StackOverflow问答以获得更多关于31后面魔术的信息，以及Java代码为什么如此频繁地使用它。 这是不完善的，但具有非常好的一般性能特点。
覆盖左边的2列，并尝试确定input使用的是输出。
a | b | a AND b ---+---+-------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1
当你看到一个1位的时候，你应该算出两个input都是1。
现在对XOR也做同样的事情
a | b | a XOR b ---+---+-------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0
XOR不提供任何关于它的input。
