使用异或的 GetHashCode() 问题

Question

我的理解是，您通常应该将 xor 与 GetHashCode() 一起使用来生成 int，以通过其值（而不是通过其引用）来识别数据。 这是一个简单的例子：

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

我的想法是，我想根据属性 A 和 B 的值将 Foo 的一个实例与另一个实例进行比较。如果 Foo1.A == Foo2.A 且 Foo1.B == Foo2.B，那么我们有平等。

问题如下：

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

这两个函数都会为 GetHashCode() 生成值 3，从而导致 Equals() 返回 true。 显然，这是一个简单的示例，只有两个属性，我可以简单地比较 Equals() 方法中的各个属性。 然而，对于更复杂的类，这很快就会失控。

我知道有时只设置一次哈希码并始终返回相同的值是很有意义的。 然而，对于需要评估相等性的可变对象，我认为这是不合理的。

在实现 GetHashCode() 时处理可以轻松互换的属性值的最佳方法是什么？

另请参阅

什么是最佳算法重写 System.Object.GetHashCode？

Answer 1

首先 - 不要仅根据 GetHashCode() 实现 Equals() - 即使对象不相等，哈希码有时也会发生冲突。

GetHashCode() 的契约包括以下内容：

• 不同的哈希码意味着对象绝对不相等
• 相同的哈希码意味着对象可能相等（但也可能不相等）

Andrew Hare 建议我合并他的答案：

我会推荐您阅读了此解决方案（顺便说一句，由我们自己的 Jon Skeet 编写），以获取“更好”的计算哈希码的方法。

不，上面的速度相对较慢并且
没有多大帮助。 有些人使用
XOR（例如 a ^ b ^ c），但我更喜欢
乔什·布洛赫（Josh Bloch）的方法中显示的一种方法
“有效的Java”：

public override int GetHashCode() 
  { 
      整数哈希 = 23； 
      哈希=哈希*37+起重机配重ID； 
      哈希 = 哈希*37 + 预告片ID； 
      散列=散列*37+craneConfigurationTypeCode.GetHashCode(); 
      返回哈希值； 
  } 
  

23和37是任意数字
它们是互质的。

上述相对于 XOR 的好处
方法是如果你有一个类型
它有两个值，分别是
经常相同，对这些进行异或
值总是给出相同的
结果 (0) 而上面的结果
区分它们，除非
你真是太不幸了。

正如上面的代码片段中提到的，您可能还想看看Joshua Bloch 的书，Effective Java， 其中包含对该主题的很好的处理（哈希码讨论也适用于 .NET）。

Answer 2

Andrew 发布了一个生成更好的哈希代码的好示例，但也要记住，您不应该使用哈希代码作为相等性检查，因为它们不能保证是唯一的。

举一个简单的例子来说明为什么这被认为是一个双重对象。 它比 int 有更多可能的值，因此不可能为每个 double 都有一个唯一的 int。 哈希实际上只是第一遍，用于像字典这样的情况，当您需要快速找到密钥时，通过首先比较哈希，可以排除很大一部分可能的密钥，并且只有具有匹配哈希的密钥才需要花费完全相等检查（或其他冲突解决方法）。

Answer 3

散列总是涉及冲突，你必须处理它（例如，比较散列值，如果它们相等，则精确比较类内的值以确保类相等）。

使用简单的异或，您会遇到很多冲突。 如果您想要更少，请使用一些数学函数将值分布在不同的位上（移位、与素数相乘等）。

Answer 4

阅读重写可变对象的 GetHashCode？ C# 并考虑实现 IEquatable

Answer 5

有几种更好的哈希实现。 例如 FNV 哈希。

Answer 6

出于好奇，因为哈希码通常不是比较的好主意，所以只执行以下代码不是更好吗？还是我遗漏了一些东西？

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

Answer 7

哈希的快速生成和良好分布

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}