为什么 XOR 是组合哈希的默认方式? [英] Why is XOR the default way to combine hashes?

问题描述

假设你有两个散列 H(A) 和 H(B) 并且你想组合它们.我读过结合两个哈希的好方法是 XOR 他们，例如XOR(H(A), H(B)).

我发现的最佳解释是在这些 哈希函数指南中简要介绍的::p><块引用>对两个具有大致随机分布的数字进行异或运算会导致另一个数字仍然具有大致随机分布*，但现在取决于这两个值.
...
* 在要组合的两个数字的每个位上，如果两个位相等，则输出 0，否则输出 1.换句话说，在 50% 的组合中，将输出 1.因此，如果两个输入位每个都有大约 50-50 的机会是 0 或 1，那么输出位也是如此.

您能否解释一下为什么 XOR 应该是组合哈希函数(而不是 OR 或 AND 等)的默认操作背后的直觉和/或数学?

解决方案

假设均匀随机(1位)输入，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一个 |乙 |a 或 b---+---+--------0 |0 |00 |1 |11 |0 |11 |1 |1一个 |乙 |异或 b---+---+--------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屋！