Nat*_*ray 135 hash cryptography bit-manipulation probability xor
假设您有两个哈希H(A)并且H(B)您想要将它们组合在一起.我已经读到了将两个哈希值组合在一起的好方法XOR,例如XOR( H(A), H(B) ).
我发现的最佳解释在这里简要介绍了这些哈希函数指南:
对具有大致随机分布的两个数字进行异或,导致另一个数字仍具有大致随机分布*,但现在取决于这两个值.
...
*在两个数字相结合的每个比特,一个输出0,如果两个比特相等,否则为1.换句话说,在组合的50%,1将输出.因此,如果两个输入位各有大约50-50的机会为0或1,那么输出位也是如此.
你能解释为什么XOR应该是组合散列函数(而不是OR或AND等)的默认操作的直觉和/或数学吗？
Yak*_*ont 155
xor是散列时使用的危险默认函数.它比和和更好,但是并没有多说.
xor是对称的,因此元素的顺序会丢失.所以xor哈希结合起来就像and.
xor将相同的值映射为零,并且应避免将"common"值映射为零:
因此,它or被映射到0,并且xor也被映射到0.因为这样的对比随机性更常见,所以你最终会得到比你想象的更多的零碰撞.
有了这两个问题,xor最终成为一个散列组合器,在表面看起来不太合适,但在进一步检查后却没有.
在现代硬件上,通常以与xor一样快的速度添加(它可能会使用更多的功率来实现这一点).添加的真值表与所讨论的位上的xor类似,但当两个值均为1时,它也会向下一位发送一个位.这会擦除较少的信息.
所以"bad"更好的是,如果"dab",结果是而xor不是0.
这仍然是对称的.我们可以以适度的成本打破这种对称性:
hash(a)<<1 + hash(a) + hash(b)
又名(a,a).((b,b)如果您使用班次解决方案,建议计算一次并建议存储).任何奇数常数而不是xor将一个xor(或k位无符号常量)双射映射到自身,因为无符号常量上的映射xor对于某些是数学模数hash(a) + hash(b),并且任何奇数常数都是相对的素数hash(a) xor hash(b).
对于一个更加漂亮的版本,我们可以检查a==b,这是有效的:
size_t hash_combine( size_t lhs, size_t rhs ) {
lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
return lhs;
}
这里我们将一些hash(a)<<1带有常量的移位版本(基本上是随机"bad"s和"dab"s - 特别是它是黄金比率的倒数作为32位定点分数)加在一起,加上一些加法和xor.这打破了对称性,并且如果输入的散列值很差(例如,假设每个分量哈希值为0),则会引入一些"噪声" - 上面处理得很好,在每个组合后生成拖拽hash(a)*3 + hash(b)和hash(a)s.我只需输出a 3).
对于那些不熟悉C/C++的人来说,a k是一个无符号整数值,足以描述内存中任何对象的大小.在64位系统上,它通常是64位无符号整数.在32位系统上,32位无符号整数.
Gre*_*ill 112
假设均匀随机(1位)输入,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位输入有多少逻辑函数a并b具有这种统一的输出分布？为什么XOR最适合您问题中所述的目的？
Mar*_*tos 29
尽管它具有方便的位混合特性,但由于其可交换性,XOR 不是结合哈希的好方法.考虑如果将{1,2,...,10}的排列存储在10元组的哈希表中会发生什么.
一个更好的选择是m * H(A) + H(B),其中m是一个很大的奇数.
图片来源:上面的合成器是Bob Jenkins的一个提示.
Leo*_*adt 17
Xor可能是组合哈希的"默认"方式,但Greg Hewgill的答案也说明了它存在缺陷的原因:两个相同哈希值的xor为零.在现实生活中,有相同的哈希比人们预期的更为常见.然后,您可能会发现在这些(并非如此罕见)的极端情况下,生成的组合哈希值始终相同(零).哈希碰撞会比你预期的要频繁得多.
在一个人为的例子中,您可能会将来自您管理的不同网站的用户的哈希密码组合在一起.不幸的是,大量用户重复使用他们的密码,并且产生的哈希值的惊人比例为零!
我希望明确指出找到此页面的其他人.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函数的推论.任何已经是一个的位都不能被OR成为零,所以它保持为1,但每个零位有机会成为一个,因此数字更大.
这意味着输入的状态对输出施加限制.如果你和任何一个90,你知道输出将等于或小于90,无论其他值是什么.
对于XOR,根据输入没有隐含的限制.在某些特殊情况下,您可以发现,如果您使用255对一个字节进行异或,则会得到相反的但是可以从中输出任何可能的字节.每个位都有机会根据另一个操作数中的相同位改变状态.