53

我经常看到像这样的代码

int hashCode(){
  return a^b;
}

为什么异或？

4

4 回答 4

100

在所有位操作中，XOR 具有最好的位混洗特性。

这个真值表解释了原因：

A B AND
0 0  0
0 1  0
1 0  0
1 1  1

A B OR
0 0  0
0 1  1
1 0  1
1 1  1

A B XOR
0 0  0
0 1  1
1 0  1
1 1  0

正如您所看到的那样，AND 和 OR 在混合位方面做得很差。

OR 将平均产生 3/4 个一位。另一方面，AND 将平均产生 3/4 空位。只有 XOR 具有偶数位与空位分布。这使得它对于哈希码生成非常有价值。

请记住，对于哈希码，您希望尽可能多地使用密钥信息并获得良好的哈希值分布。如果你使用 AND 或 OR，你会得到偏向于有很多零的数字或有很多一的数字的数字。

于 2010-02-25T13:27:15.467 回答
23

XOR 具有以下优点：

  • 它不依赖于计算顺序，即 a^b = b^a
  • 它不会“浪费”位。如果您在其中一个组件中更改一点，最终值也会发生变化。
  • 它很快，即使在最原始的计算机上也只有一个周期。
  • 它保持均匀分布。如果你组合的两块是均匀分布的，那么组合也是如此。换句话说，它不会倾向于将摘要的范围折叠成更窄的范围。

更多信息在这里。

于 2010-02-25T13:32:36.297 回答
5

XOR 运算符是可逆的，即假设我有一个位字符串 as0 0 1并且我将它与另一个位字符串 XOR 1 1 1，输出是

0 xor 1 = 1
0     1 = 1
1     1 = 0

现在我可以再次将第一个字符串与结果进行异或以获得第二个字符串。IE

0   1 = 1
0   1 = 1
1   0 = 1

因此，这使第二个字符串成为键。其他位运算符未发现此行为

请参阅此以获取更多信息 -->为什么在密码学中使用 XOR？

于 2010-02-25T13:32:13.743 回答
1

还有另一个用例：必须比较（某些）字段而不考虑其顺序的对象。例如，如果您希望 pair(a, b)始终等于 pair (b, a)。
XOR 具有a ^ b=的属性b ^ a，因此在这种情况下可以在哈希函数中使用。

示例：（此处为完整代码）

定义：

final class Connection {
    public final int A;
    public final int B;

    // some code omitted

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Connection that = (Connection) o;

        return (A == that.A && B == that.B || A == that.B && B == that.A);
    }

    @Override
    public int hashCode() {
        return A ^ B;
    }

    // some code omitted
}

用法：

        HashSet<Connection> s = new HashSet<>();
        s.add(new Connection(1, 3));
        s.add(new Connection(2, 3));
        s.add(new Connection(3, 2));
        s.add(new Connection(1, 3));
        s.add(new Connection(2, 1));

        s.remove(new Connection(1, 2));

        for (Connection x : s) {
            System.out.println(x);
        }

        // output:
        // Connection{A=2, B=3}
        // Connection{A=1, B=3}
于 2014-03-23T13:25:59.190 回答