为什么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位inputab有多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),就会引入一些“噪声” – 上面的处理很好,在每次合并之后产生10的拖尾。 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 ,则输出是随机的。 ANDOR也是如此。 例:

 00101001 XOR 00000000 = 00101001
 00101001和00000000 = 00000000
 00101001或11111111 = 11111111

正如@Greg Hewgill所提到的,即使两个input都是随机的,使用ANDOR也会导致输出偏差。

我们之所以用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。