为什么 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-50 的机会为 0 或 1，那么输出位也将如此.

你能解释为什么 XOR 应该是组合散列函数(而不是 OR 或 AND 等)的默认操作背后的直觉和/或数学吗?

解决方案

假设均匀随机(1-bit)输入，AND 函数输出概率分布为 75% 0 和 25% 1.相反，OR 是 25% 0 和 75% 1.

XOR 函数为 50% 0 和 50% 1，因此有利于组合均匀概率分布.

这可以通过写出真值表看出:

 a |乙 |一个和 b---+---+--------0 |0 |00 |1 |01 |0 |01 |1 |1一个|乙 |或 b---+---+--------0 |0 |00 |1 |11 |0 |11 |1 |1一个|乙 |异或---+---+--------0 |0 |00 |1 |11 |0 |11 |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屋！