为什么在计算哈希码时要使用异或运算符？

Question

在这篇MSDN文章中，http://msdn.microsoft.com/en-us/library/ms132123.aspx介绍了Class Equalitycomparer并提供了一个例子。在比较盒子的示例中，它使用了以下类 -

class BoxSameDimensions : EqualityComparer<Box>
{
    public override bool Equals(Box b1, Box b2)
    {
        if (b1.Height == b2.Height & b1.Length == b2.Length
            & b1.Width == b2.Width)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public override int GetHashCode(Box bx)
    {
        int hCode = bx.Height ^ bx.Length ^ bx.Width;
        return hCode.GetHashCode();
    }
}

我不理解这行代码：int hCode = bx.Height ^ bx.Length ^ bx.Width;

有人可以解释一下吗？为什么要用异或运算符？

- Paul Stanley

---

请查看以下链接：https://dev59.com/yXRC5IYBdhLWcg3wOeSB 和 https://dev59.com/EnVC5IYBdhLWcg3wihqv。 - GSerg

还可以参考https://dev59.com/Z3E95IYBdhLWcg3wY85l#2334251和http://csharpindepth.com/ViewNote.aspx?NoteID=27（后者解释了为什么异或可能实际上是一个不好的选择） - Jeff B

Answer 1

^ 运算符是按位异或运算符。

在这种情况下，它被用作从三个整数生成哈希码的便捷方法。 （我认为这不是一个很好的方法，但这是另一个问题...）

奇怪的是，在构造哈希码之后，他们再次对其使用 GetHashCode()，对于 int 来说这完全没有意义，因为它将返回 int 本身 - 因此这是一个无操作。

这就是他们应该写成的样子：

public override int GetHashCode(Box bx)
{
    return bx.Height ^ bx.Length ^ bx.Width;
}

这个SO回答解释了为什么XOR有时候表现得相当好：为什么在java hashCode()中经常使用XOR，但很少使用其他位运算符？ 注意：我不喜欢像那样对三个整数使用xor的哈希码，因为：

a ^ b ^ a == b

换句话说，如果对哈希码有贡献的第一个和最后一个整数相同，则它们根本不会对最终哈希码产生影响——它们会互相抵消，结果总是中间整数。

如果只使用两个整数，则情况更糟：

a ^ a == 0

对于两个整数，如果它们相同，则哈希码将为零。

- Matthew Watson

---

是的，谢谢！我正在学习这个，觉得很奇怪！ - Paul Stanley

值得一提的是，在那些越界整数运算为未定义行为的语言中，异或操作符具有任何操作数组合都会产生定义行为的优点，但在那些整数类型可以干净地包装的语言中，加法同样快捷且易用，并避免了你描述的问题情况。 - supercat

所以如果我们可以保证整数列表是不同的，那么这是否可以视为计算哈希代码的好方法？ - Mike T

Answer 2

就像你可能已经知道的那样，GetHashCode()是将对象映射到数字的函数，以使得不同对象获得相同数字的概率尽可能地小（显然这个数字应该对于同一对象始终保持不变，而且函数应该快速）。从所有布尔运算符（AND、OR、NOT、XOR）中，XOR给出了最佳的位分布（请看OR、AND、XOR布尔运算表）。然而，我建议你检查一下这种方法：重写System.Object.GetHashCode的最佳算法是什么？（使用质数分布属性的哈希函数）。

- fex