为什么XOR的默认方式为哈希结合? [英] Why is XOR the default way to combine hashes?
问题描述
假设你有两个散列 H(A)
和 H(B)
,你想将它们合并。我读过两个散列结合起来的好方法是将 XOR
它们,例如 XOR(H(A),H(B))
。
我发现在这里简要谈到了这些散列函数指引最好的解释的:
在另一个号码与异或大致随机分布结果两个数字仍然大致随机分布*,但现在依赖于两个值。
...
*在两个数字相结合的每个比特,一个输出0,如果两个比特相等,否则为1。换句话说,在组合的50%时,一个1将输出。因此,如果每两个输入位具有大致50%的机会的是0或1,那么也将输出位。
块引用>你能解释一下为什么后面XOR应该是结合散列函数(而不是OR或AND等)?
默认操作直觉和/或数学解决方案假设均匀随机(1位)输入,和函数输出概率分布为75%
0
和25%1
。相反的,或者说是25%,0
75%1
。XOR函数为50%
0
50%1
,因此它是很好的结合统一的概率分布这可以写出真值表中可以看出:
A | C | A和B
--- + --- + --------
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1 A | C | A或B
--- + --- + --------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1 A | C |一个XOR B
--- + --- + --------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0练习:如何的两个1位输入多个逻辑功能
A
和B
有这种均匀的输出分布?为什么XOR最适合你的问题陈述的目的是什么?Say you have two hashes
H(A)
andH(B)
and you want to combine them. I've read that a good way to combine two hashes is toXOR
them, e.g.XOR( H(A), H(B) )
.The best explanation I've found is touched briefly here on these hash function guidelines:
XORing two numbers with roughly random distribution results in another number still with roughly random distribution*, but which now depends on the two values.
...
* At each bit of the two numbers to combine, a 0 is output if the two bits are equal, else a 1. In other words, in 50% of the combinations, a 1 will be output. So if the two input bits each have a roughly 50-50 chance of being 0 or 1, then so too will the output bit.Can you explain the intuition and/or mathematics behind why XOR should be the default operation for combining hash functions (rather than OR or AND etc.)?
解决方案Assuming uniformly random (1-bit) inputs, the AND function output probability distribution is 75%
0
and 25%1
. Conversely, OR is 25%0
and 75%1
.The XOR function is 50%
0
and 50%1
, therefore it is good for combining uniform probability distributions.This can be seen by writing out truth tables:
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
Exercise: How many logical functions of two 1-bit inputs
a
andb
have this uniform output distribution? Why is XOR the most suitable for the purpose stated in your question?这篇关于为什么XOR的默认方式为哈希结合?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!