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

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


当前回答

截至https://github.com/dotnet/coreclr/pull/14863,有一种生成哈希代码的新方法非常简单!只要写

public override int GetHashCode()
    => HashCode.Combine(field1, field2, field3);

这将生成高质量的哈希代码,而无需担心实现细节。

其他回答

ValueTuple-C#7更新

正如@cactuaroid在评论中提到的,可以使用值元组。这节省了一些击键,更重要的是纯粹在堆栈上执行(无垃圾):

(PropA, PropB, PropC, PropD).GetHashCode();

(注意:使用匿名类型的原始技术似乎在堆上创建了一个对象,即垃圾,因为匿名类型被实现为类,尽管编译器可能会对此进行优化。对这些选项进行基准测试会很有趣,但元组选项应该更优。)

匿名类型(原始答案)

Microsoft已经提供了一个很好的通用HashCode生成器:只需将属性/字段值复制到匿名类型并对其进行哈希:

new { PropA, PropB, PropC, PropD }.GetHashCode();

这适用于任何数量的财产。它不使用拳击。它只是使用了框架中已经实现的匿名类型的算法。

这是我的哈希码助手。它的优点是它使用泛型类型参数,因此不会导致装箱:

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
         unchecked
         {
             return 31 * arg1.GetHashCode() + arg2.GetHashCode();
         }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            return 31 * hash + arg3.GetHashCode();
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, 
        T4 arg4)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            hash = 31 * hash + arg3.GetHashCode();
            return 31 * hash + arg4.GetHashCode();
        }
    }

    public static int GetHashCode<T>(T[] list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    public static int GetHashCode<T>(IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    /// <summary>
    /// Gets a hashcode for a collection for that the order of items 
    /// does not matter.
    /// So {1, 2, 3} and {3, 2, 1} will get same hash code.
    /// </summary>
    public static int GetHashCodeForOrderNoMatterCollection<T>(
        IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            int count = 0;
            foreach (var item in list)
            {
                hash += item.GetHashCode();
                count++;
            }
            return 31 * hash + count.GetHashCode();
        }
    }

    /// <summary>
    /// Alternative way to get a hashcode is to use a fluent 
    /// interface like this:<br />
    /// return 0.CombineHashCode(field1).CombineHashCode(field2).
    ///     CombineHashCode(field3);
    /// </summary>
    public static int CombineHashCode<T>(this int hashCode, T arg)
    {
        unchecked
        {
            return 31 * hashCode + arg.GetHashCode();   
        }
    }

此外,它还具有扩展方法来提供流畅的界面,因此您可以这样使用它:

public override int GetHashCode()
{
    return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}

或者像这样:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}

直到最近,我的回答都很接近乔恩·斯基特的回答。然而,我最近开始了一个使用两个哈希表的幂的项目,即内部表大小为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()要快得多。

在Equals()比较多个字段的大多数情况下,GetHash()对一个字段或多个字段进行散列并不重要。您只需确保计算哈希值非常便宜(请不要分配)和快速(没有繁重的计算,当然也没有数据库连接),并提供良好的分布。

重型起吊应是Equals()方法的一部分;哈希应该是一个非常便宜的操作,以便能够对尽可能少的项目调用Equal()。

最后一个提示:不要依赖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());
  }
}