为什么XOR的默认方式为哈希结合？

问题描述

假设你有两个散列 H（A）和 H（B），你想将它们合并。我读过两个散列结合起来的好方法是将 XOR 它们，例如 XOR（H（A），H（B））。

我发现在这里简要谈到了这些的：

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的默认方式为哈希结合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！