为什么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) and H(B) and you want to combine them. I've read that a good way to combine two hashes is to XOR 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 and b have this uniform output distribution? Why is XOR the most suitable for the purpose stated in your question?

这篇关于为什么XOR的默认方式为哈希结合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！