使用异或的 GetHashCode() 问题

StackOverflow https://stackoverflow.com/questions/1008633

  •  06-07-2019
  •  | 
  •  

题

我的理解是，您通常应该将 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 的最佳算法是什么？

有帮助吗？

解决方案

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

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

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

安德鲁·黑尔建议我合并他的答案：

我建议你阅读 这个解决方案 （由我们自己的 乔恩·斯基特, 顺便说一下）计算哈希码的“更好”方法。

不，以上相对较慢，无济于事。有些人使用XOR（例如A ^ B ^ C），但我更喜欢Josh Bloch的“有效Java”中显示的方法：

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}

23和37是联合总数的任意数字。

上面的好处比XOR方法的好处是，如果您的类型具有两个相同的值，那么x的值始终会给出相同的结果（0），而除非您非常区分它们不幸。

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

其他提示

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

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

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

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

读 重写可变对象的 GetHashCode？C＃ 并考虑实施 IEquatable<T>

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

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

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

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;
}

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top