为什么在Java的hashCode()方法中经常使用异或运算符，而其他位运算符很少被使用？

Question

我经常看到类似以下代码：

int hashCode(){
  return a^b;
}

为什么要用异或运算（XOR）？

- Andrei N

---

可能重复 --> https://dev59.com/-HM_5IYBdhLWcg3wcCnc - Bhaskar

Answer 1

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的1比特位。而AND则相反，平均产生3/4的零比特位。只有XOR具有一比特位与零比特位分布均匀的特点。这使得它在哈希码生成中非常有价值。

请记住，在哈希码中，您要尽可能使用键的所有信息并获得良好的哈希值分布。如果您使用AND或OR，您将获得偏向于具有许多零或许多一的数字。

- Nils Pipenbrinck

Answer 2

XOR 具有以下优点：

• 它不依赖运算的顺序，即 a^b = b^a。
• 它不会"浪费"比特。如果在组件中的任何一个比特发生变化，则最终值也将发生变化。
• 它非常快速，在即使是最原始的计算机上也只需要一个周期。
• 它保留了均匀分布。如果您合并的两个部分是均匀分布的，那么合并后的结果也是如此。换句话说，它不会使摘要的范围收缩到更窄的带状区间内。

更多信息请参见这里。

- dogbane

---

如果所有输入位都是独立的，异或操作不会浪费位，但如果合并强相关的位，则可能会浪费很多位。例如，如果有一种类型表示范围在0-65535之间的一对数字，并通过将这些数字进行异或运算形成哈希，则每个值中为零的上16位在哈希码中也将为零。更糟糕的是，如果不成比例的实例（例如10％）具有匹配的两个数字，则同样比例的实例将返回哈希值为零。 - supercat

Answer 3

XOR运算符是可逆的，即假设我有一个位串为0 0 1，我将其与另一个位串1 1 1进行XOR运算，输出结果为

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

现在我可以再次使用异或运算符将第一个字符串与结果进行异或，从而得到第二个字符串。例如：

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

因此，这使得第二个字符串成为关键。其他位运算符不具备这种行为。

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

- Bhaskar

---

hashCode 不需要被反转。 - Andrei N

是的，但在密码学中XOR的一个用途是其可逆性质。 - Bhaskar

Answer 4

还有另一种用例：对象中需要比较某些字段而不考虑它们的顺序。例如，如果您希望对成对的 (a, b) 始终等于成对的 (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}

- Display Name