为什么 XOR 是组合散列的默认方式？

小开

最佳答案

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

异或函数分别为50% 0和50% 1，适合于组合均匀概率分布。

这可以通过写出真相表来看出:

 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

练习: 两个1位输入 a和 b有多少逻辑函数具有这种均匀的输出分布？为什么异或最适合你的问题中提到的目的？

小开

如果你的 XOR是一个随机输入带有偏见的输入，输出是随机的。对于 AND或 OR则不是这样。例如:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

正如@Greg Hewgill 提到的，即使都有的输入是随机的，使用 AND或者 OR也会导致有偏差的输出。

我们之所以在更复杂的事情上使用 XOR，是因为，嗯，没有必要: XOR工作得非常完美，而且它非常愚蠢——非常快。

小开

有些东西我想明确地指出给其他人谁找到这个页面。像 BlueRaja 一样，AND 和 OR 限制产量—— Danny Pflughoe 试图指出，但可以更好地定义:

首先，我想定义两个简单的函数来解释这个问题: Min ()和 Max ()。

Min (A，B)将返回 A 和 B 之间较小的值，例如: Min (1,5)返回1。

Max (A，B)将返回 A 和 B 之间较大的值，例如: Max (1,5)返回5。

如果给你: C = A AND B

然后你可以找到 C <= Min(A, B)，我们知道这一点，因为没有任何东西，可以用 A 或 B 的0位 AND 来使它们成为1。因此，每个零位都保持为零位，并且每个位都有机会变成零位(因此是一个更小的值)。

配图: C = A OR B

反过来是正确的: C >= Max(A, B)通过这个，我们看到了 AND 函数的推论。任何已经是1的比特都不能被 ORE 为0，所以它仍然是1，但是每个0比特都有机会变成1，从而变成一个更大的数。

这意味着输入的状态对输出应用限制。如果您使用任何带有90的值 AND，您知道输出将等于或小于90，而不管其他值是什么。

对于异或，没有基于输入的隐含限制。在一些特殊情况下，您可以发现，如果用255异或一个字节，就会得到相反的结果，但是任何可能的字节都可以从中输出。每个位都有机会根据另一个操作数中的相同位改变状态。

小开

Xor 可能是组合散列的“默认”方式，但格雷格•休吉尔(Greg Hewgill)的答案也显示了它的缺陷所在: 两个相同哈希值的 xor 为零。在现实生活中，相同的散列比人们想象的更常见。然后您可能会发现，在这些(并不罕见的)角落情况下，结果组合散列总是相同的(零)。散列冲突将比您预期的要频繁得多。

在一个人为的例子中，您可能会组合来自您管理的不同网站的用户的哈希密码。不幸的是，大量的用户重用他们的密码，并且令人惊讶的比例结果哈希是零！

小开

尽管 XOR 具有方便的位混合特性，但由于其交换性，它是组合散列的一种很好的方法。考虑一下，如果将{1,2，... ，10}的排列存储在包含10个元组的哈希表中，会发生什么情况。

一个更好的选择是 m * H(A) + H(B)，其中我是一个大的奇数。

图片来源: 上面的合成器是鲍勃 · 詹金斯提供的线索。

小开

xor是散列时使用的一个危险的默认函数。它比 and和 or好，但是说明不了什么。

xor是对称的，因此元素的顺序会丢失。因此，"bad"将与 "dab"进行哈希组合。

xor将成对相同的值映射为零，应避免将“公共”值映射为零:

因此，(a,a)被映射为0，而 (b,b)也被映射为0。由于这样的对几乎总是比随机性所暗示的更为常见，因此最终的碰撞数量远远超出了应有的水平。

有了这两个问题，xor最终成为一个散列组合器，表面上看起来还不错，但在进一步检查之后就不行了。

在现代硬件上，增加速度通常和 xor一样快(不可否认，它可能使用更多的电力来完成这一任务)。添加的真值表类似于所讨论位的 xor，但是当两个值都为1时，它也向下一位发送一个位。这意味着它可以删除更少的信息。

所以 hash(a) + hash(b)优于 hash(a) xor hash(b)，因为如果 a==b，结果是 hash(a)<<1而不是0。

这仍然是对称的; 因此 "bad"和 "dab"得到相同的结果仍然是一个问题。我们可以以适度的代价打破这种对称性:

hash(a)<<1 + hash(a) + hash(b)

又名 hash(a)*3 + hash(b)。(计算一次 hash(a)，如果使用 shift 解决方案，建议存储)。任何奇数常量而不是 3都会将一个“ k位”无符号整数双向映射到自身，因为无符号整数上的映射是某些 k的数学模 2^k，而任何奇数常量相对于 2^k都是素数。

对于一个更花哨的版本，我们可以检查 boost::hash_combine，它实际上是:

size_t hash_combine( size_t lhs, size_t rhs ) {
lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
return lhs;
}

在这里，我们用一个常数(基本上就是随机的 0和 1，特别是它是黄金比率的倒数，作为一个32位固定点分数)加上一些加法和一个 xor。这打破了对称性，并引入了一些“噪音”，如果传入散列值很差(即，想象每个组件散列为0-上述处理它很好，产生一个污点的 1和 0后，每个组合。在这种情况下，我的初始 3*hash(a)+hash(b)只是输出一个 0)。

将其扩展到64位(使用 π 的展开作为64位的常数，因为它在64位是奇数) :

size_t hash_combine( size_t lhs, size_t rhs ) {
if constexpr (sizeof(size_t) >= 8) {
lhs ^= rhs + 0x517cc1b727220a95 + (lhs << 6) + (lhs >> 2);
} else {
lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
}
return lhs;
}

(对于那些不熟悉 C/C + + 的人来说，size_t是一个无符号整数值，它大到足以描述内存中任何对象的大小。在64位系统上，它通常是一个64位无符号整数。在32位系统上，是一个32位无符号整数。)

小开

Java.util. 数组中不同版本 hashCode()的源代码对于坚实的、通用的散列算法是一个很好的参考。它们很容易理解并翻译成其他编程语言。

大致来说，大多数多属性 hashCode()实现遵循以下模式:

public static int hashCode(Object a[]) {
if (a == null)
return 0;


int result = 1;


for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());


return result;
}

您可以搜索其他 StackOverflow 问答，以获得更多关于 31背后的魔力以及为什么 Java 代码如此频繁地使用它的信息。它不完善，但具有很好的一般性能特征。

小开

覆盖左边的2列，尝试只使用输出来计算输入是什么。

 a | b | a AND b
---+---+--------
0 | 0 |    0
0 | 1 |    0
1 | 0 |    0
1 | 1 |    1

当你看到一个1位时，你应该算出两个输入都是1。

现在对 XOR 执行相同的操作

 a | b | a XOR b
---+---+--------
0 | 0 |    0
0 | 1 |    1
1 | 0 |    1
1 | 1 |    0

XOR 没有提供任何有关其输入的信息。

小开

XOR 有时不会忽略某些输入，比如或者和还有。

以 和(X，Y)为例，如果输入 X为 false，那么输入 为什么并不重要... ... 在组合散列时，人们可能希望输入重要。

如果你取 XOR (X，Y)然后都有输入 一直都是物质。在 Y 不重要的情况下，X 的值将不存在。如果 X 或 Y 被改变，那么输出将反映这一点。