在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。

对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?


当前回答

可以尝试采用C++Boost库的方法。类似于:

class HashUtil
{
  public static int HashCombine(int seed, int other)
  {
    unchecked
    {
      return other + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
  }
}

然后:

class MyClass
{
  private string _field1;
  private int _field2;
  private AnotherClass _field3;
  private YetAnotherClass _field4;

  public override int GetHashCode()
  {
    int result = HashUtil.HashCombine(_field1.GetHashCode(), _field2);
    result = HashUtil.HashCombine(result, _field3.GetHashCode());
    return HashUtil.HashCombine(result, _field4.GetHashCode());
  }
}

其他回答

我通常会使用Josh Bloch精彩的有效Java中给出的实现。它很快,创建了一个很好的哈希,不太可能导致冲突。选择两个不同的素数,例如17和23,并执行以下操作:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

正如评论中所指出的,你可能会发现最好选择一个大素数来乘。很显然486187639很好。。。虽然我见过的大多数小数字的例子都倾向于使用素数,但至少有一些类似的算法经常使用非素数。例如,在后面的FNV示例中,我使用的数字显然很好,但初始值不是质数。(不过乘法常数是质数。我不知道这有多重要。)

这比XORing散列码的常见做法要好,主要原因有两个。假设我们有一个具有两个int字段的类型:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

顺便说一下,早期的算法是C#编译器当前用于匿名类型的算法。

这个页面提供了很多选项。我认为,在大多数情况下,上述内容“足够好”,而且非常容易记住并正确理解。FNV替代方案同样简单,但使用不同的常数和XOR代替ADD作为组合操作。它看起来像下面的代码,但正常的FNV算法对单个字节进行操作,因此这需要进行修改,以每个字节执行一次迭代,而不是每个32位哈希值。FNV也设计用于可变长度的数据,而我们在这里使用它的方式总是用于相同数量的字段值。对这个答案的评论表明,这里的代码实际上并不像上面的添加方法那样有效(在测试的示例案例中)。

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

请注意,需要注意的一点是,理想情况下,您应该防止在将其添加到依赖于哈希代码的集合后,对等式敏感(因此对哈希代码敏感)的状态发生变化。

根据文件:

可以为不可变引用类型重写GetHashCode。通常,对于可变引用类型,只有在以下情况下才应重写GetHashCode:您可以从不可变的字段计算哈希代码;或当可变对象包含在依赖其哈希代码的集合中时,可以确保该对象的哈希代码不会更改。

FNV文章的链接已断开,但这是互联网档案馆的一份副本:永恒的困惑-哈希的艺术

ReSharper用户可以使用ReSharper->Edit->generate Code->Equality Members生成GetHashCode、Equals等。

// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
    unchecked {
        int hashCode = Id;
        hashCode = (hashCode * 397) ^ IntMember;
        hashCode = (hashCode * 397) ^ OtherIntMember;
        hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
        // ...
        return hashCode;
    }
}

可以尝试采用C++Boost库的方法。类似于:

class HashUtil
{
  public static int HashCombine(int seed, int other)
  {
    unchecked
    {
      return other + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
  }
}

然后:

class MyClass
{
  private string _field1;
  private int _field2;
  private AnotherClass _field3;
  private YetAnotherClass _field4;

  public override int GetHashCode()
  {
    int result = HashUtil.HashCombine(_field1.GetHashCode(), _field2);
    result = HashUtil.HashCombine(result, _field3.GetHashCode());
    return HashUtil.HashCombine(result, _field4.GetHashCode());
  }
}

我想把我的最新发现添加到我经常提到的这个主题中。

我当前的visual studio/项目设置提供了将元组自动重构为结构的功能。这将生成如下GetHashCode函数:

        public override int GetHashCode()
        {
            int hashCode = -2088324004;
            hashCode = hashCode * -1521134295 + AuftragGesperrt.GetHashCode();
            hashCode = hashCode * -1521134295 + Auftrag_gesperrt_von.GetHashCode();
            hashCode = hashCode * -1521134295 + Auftrag_gesperrt_am.GetHashCode();
            return hashCode;
        }

编辑:为了澄清AuftragGesperrt、Auftrag _gesperrt_von和Auftrag-gesperrt _am是财产。如果微软的开发人员使用这个功能,这可能是一个不错的解决方案。

直到最近,我的回答都很接近乔恩·斯基特的回答。然而,我最近开始了一个使用两个哈希表的幂的项目,即内部表大小为8、16、32等的哈希表。

而且非常糟糕。因此,经过一点实验和研究后,我开始用以下方法重新散列我的散列:

public static int ReHash(int source)
{
  unchecked
  {
    ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
    ulong d = 0xE2ADBEEFDEADBEEF ^ c;
    ulong a = d += c = c << 15 | c >> -15;
    ulong b = a += d = d << 52 | d >> -52;
    c ^= b += a = a << 26 | a >> -26;
    d ^= c += b = b << 51 | b >> -51;
    a ^= d += c = c << 28 | c >> -28;
    b ^= a += d = d << 9 | d >> -9;
    c ^= b += a = a << 47 | a >> -47;
    d ^= c += b << 54 | b >> -54;
    a ^= d += c << 32 | c >> 32;
    a += d << 25 | d >> -25;
    return (int)(a >> 1);
  }
}

然后我的两个哈希表的能力就不再糟糕了。

但这让我很不安,因为上面的方法不应该奏效。或者更准确地说,除非原始的GetHashCode()以非常特殊的方式很差,否则它不应该工作。

重新混合哈希代码并不能改善一个好的哈希代码,因为唯一可能的效果是我们引入了更多的冲突。

重新混合哈希代码并不能改善糟糕的哈希代码,因为唯一可能的效果是我们将值53上的大量冲突更改为值183487291的大量冲突。

重新混合哈希代码只能改进哈希代码,该哈希代码至少在避免整个范围内的绝对冲突(232个可能值)方面做得相当好,但在为哈希表中的实际使用而进行模化时,在避免冲突方面做得很差。虽然二次幂表的简单模使这一点更加明显,但它对更常见的素数表也有负面影响,这并不是那么明显(重新散列的额外工作将超过好处,但好处仍然存在)。

编辑:我还使用了开放寻址,这也会增加对冲突的敏感度,也许比二的幂更敏感。

好吧,这令人不安的是,.NET(或这里的研究)中的string.GetHashCode()实现可以通过这种方式改进多少(由于较少的冲突,测试运行速度大约快20-30倍),更令人不安我自己的哈希代码可以改进多少(远远不止于此)。

我过去编写的所有GetHashCode()实现,实际上都是这个网站上答案的基础,比我想象的要糟糕得多。很多时候,它对于很多用途来说“足够好”,但我想要更好的东西。

所以我把这个项目放在一边(反正它是一个宠物项目),开始研究如何在.NET中快速生成一个好的、分布良好的哈希代码。

最后,我决定将SpookyHash移植到.NET。实际上,上面的代码是使用SpookyHash从32位输入生成32位输出的快速路径版本。

现在,SpookyHash不是一个好的快速记忆代码。我的端口就更少了,因为我手动内联了很多端口以提高速度*。但这就是代码重用的目的。

然后我把这个项目放在一边,因为正如最初的项目产生了如何产生更好的哈希代码的问题,所以这个项目产生了怎样产生更好的.NET memcpy的问题。

然后我回来了,并生成了大量重载,以便将几乎所有的原生类型(十进制†除外)轻松地输入到哈希代码中。

它速度很快,鲍勃·詹金斯(Bob Jenkins)值得称赞,因为我移植的原始代码速度更快,尤其是在64位机器上,算法经过了优化。

完整的代码可以在https://bitbucket.org/JonHanna/spookilysharp/src但是考虑到上面的代码是它的简化版本。

然而,由于它现在已经写好了,因此可以更容易地使用它:

public override int GetHashCode()
{
  var hash = new SpookyHash();
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

它还需要种子值,因此,如果您需要处理不受信任的输入,并希望防止哈希DoS攻击,您可以根据正常运行时间或类似情况设置种子,并使攻击者无法预测结果:

private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
  //produce different hashes ever time this application is restarted
  //but remain consistent in each run, so attackers have a harder time
  //DoSing the hash tables.
  var hash = new SpookyHash(hashSeed0, hashSeed1);
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

*这方面的一个大惊喜是,手动内联返回(x<<n)|(x>>-n)的旋转方法改进了性能。我本可以确定抖动会为我内联,但评测显示的情况并非如此。

†十进制虽然来自C#,但从.NET角度看不是本机。它的问题是,它自己的GetHashCode()将精度视为重要,而它自己的Equals()则没有。两者都是有效的选择,但不是那样混合。在实现自己的版本时,您需要选择执行一个或另一个,但我不知道您想要哪个。

‡通过比较。如果在字符串上使用,64位的SpookyHash要比32位的string.GetHashCode()快得多,这比64位的string.GetHashCode()要快得多。