重写 GetHashCode 的最佳算法是什么?

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

有没有关于如何为我的自定义类实现GetHashCode的标准算法或最佳实践,因此我不会降低性能?

答案

我通常会使用类似于 Josh Bloch 出色的 Effective 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;
    }
}

如评论中所述,您可能会发现最好选择一个大质数乘以。显然 486187739 是个好方法…… 虽然我看到的大多数带有小数的示例都倾向于使用质数,但至少有类似的算法经常使用非质数。例如,在稍后的非FNV示例中,我使用的数字似乎很有效 - 但初始值不是素数。 (尽管乘法常数素数。我不知道它的重要性。)

由于两个主要原因,这比对哈希码进行XOR的常规做法更好。假设我们有一个带有两个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:

  • 您可以从不可变的字段中计算哈希码;要么
  • 您可以确保在对象包含在依赖于其哈希代码的集合中时,该可变对象的哈希代码不会更改。

匿名类型

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

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

这将适用于任何数量的属性。它不使用拳击。它仅使用框架中已实现的用于匿名类型的算法。

ValueTuple-C#7 的更新

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

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

我在 Helper 库中有一个 Hashing 类,可用于该目的。

/// <summary> 
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
    const int b = 378551;
    int a = 63689;
    int hash = 0;

    // If it overflows then just wrap around
    unchecked
    {
        for (int i = 0; i < input.Length; i++)
        {
            if (input[i] != null)
            {
                hash = hash * a + input[i].GetHashCode();
                a = a * b;
            }
        }
    }

    return hash;
}

然后,只需将其用作:

public override int GetHashCode()
{
    return Hashing.RSHash(_field1, _field2, _field3);
}

我没有评估其性能,因此欢迎您提供任何反馈。

这是我使用Jon Skeet 的实现的帮助程序类。

public static class HashCode
{
    public const int Start = 17;

    public static int Hash<T>(this int hash, T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked((hash * 31) + h);
    }
}

用法:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)
        .Hash(_field3);
}

如果要避免编写 System.Int32 的扩展方法:

public struct HashCode
{
    private readonly int _value;

    public HashCode(int value) => _value = value;

    public static HashCode Start { get; } = new HashCode(17);

    public static implicit operator int(HashCode hash) => hash._value;

    public HashCode Hash<T>(T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked(new HashCode((_value * 31) + h));
    }

    public override int GetHashCode() => _value;
}

它仍然是通用的,它仍然避免任何堆分配,并且使用的方式完全相同:

public override int GetHashCode()
{
    // This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
    // And the result is implicitly converted to `Int32`.
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)     
        .Hash(_field3);
}

Martin 评论后更新:

obj != null导致装箱,因此我切换到默认比较器。

  • 有关默认比较器的性能,请参见此答案
  • 有关空值哈希码的讨论,请参见此问题

编辑(2018 年 5 月):

EqualityComparer<T>.Default getter 现在是 JIT 内在函数 - 该博客文章中的 Stephen Toub 提到了pull 请求

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

繁重的工作应该是 Equals()方法的一部分;散列应该是一种非常便宜的操作,以允许在尽可能少的项目上调用 Equals()。

最后一个提示: 不要依赖 GetHashCode()在多次复制运行中保持稳定 。许多. Net 类型不能保证它们的哈希码在重新启动后保持不变,因此您应该仅将 GetHashCode()的值用于内存数据结构中。

直到最近,我的回答与 Jon Skeet 的回答非常接近。但是,我最近开始了一个项目,该项目使用 2 的幂的哈希表,即内部表的大小为 8、16、32 等的哈希表。有充分的理由偏爱素数大小,但是同样也是 2 的幂数的一些优势。

它几乎吸了。因此,经过一些实验和研究,我开始使用以下方法重新哈希散列:

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

然后我的 2 的幂的哈希表不再吸引人。

但是,这使我不安,因为上述方法不起作用。或者更确切地说,除非原始的GetHashCode()以某种特殊方式变差,否则它不起作用。

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

重新混合哈希码不能改善可怕的哈希码,因为唯一可能的效果是我们将例如值 53 上的大量冲突更改为值 18,3487,291 的大量。

重新混合哈希码只能改善哈希码,该哈希码至少在避免整个范围内的绝对冲突(2 32 个可能的值)方面做得相当好,但是在为哈希表中的实际使用取模时避免避免冲突很差。虽然 2 的幂的表的简单模数使这一点更加明显,但它对更常见的质数表也有负面影响,但效果却不那么明显(重新哈希处理的额外工作将超过收益) ,但好处仍然存在)。

编辑:我也在使用开放式寻址,这也将增加碰撞的敏感度,可能比事实为二乘幂的情况要多。

很好,这令人不安..NET (或在这里学习)中的string.GetHashCode()实现可以通过这种方式进行改进(由于较少的冲突,测试运行速度提高了约 20-30 倍),并且更多地干扰了我自己的哈希码有很多可以改进的地方(远远不止这些)。

我过去编写的所有 GetHashCode()实现(实际上已用作该站点的答案的基础)都比我经历的要差得多 。在很多时候,它对于许多用途来说都 “足够好”,但是我想要更好的东西。

因此,我将该项目放在一边(无论如何,这都是一个宠物项目),然后开始研究如何在. NET 中快速生成良好的,分布良好的哈希代码。

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

现在,SpookyHash 并不是一种快速记住代码的好方法。我的端口号甚至更少,因为我手工插入了很多端口以提高速度 *。但这就是代码重用的目的。

然后,我将该项目放在一边,因为就像原始项目产生了如何产生更好的哈希码的问题一样,所以那个项目也产生了如何产生更好的. NET memcpy 的问题。

然后我回来了,并产生了许多重载,可以轻松地将几乎所有本机类型( decimal †除外)馈入哈希码。

很快,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();
}

它还需要种子值,因此,如果您需要处理不受信任的输入并想要防止 Hash 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)有所改善。我本来可以确定,抖动对我而言是内联的,但分析显示并非如此。

†从. NET 角度来看, decimal不是本机的,尽管它是 C#的。它的问题在于它自己的GetHashCode()将精度视为重要,而其自己的Equals()却不。两者都是有效的选择,但并非如此。在实现自己的版本时,您需要选择一个或另一个,但是我不知道您想要哪个。

‡通过比较的方式。如果在字符串中使用,在 64 位的 SpookyHash 是大大高于string.GetHashCode()在 32 位,它们是略快于string.GetHashCode()在 64 位,这是显着地快于 SpookyHash 上 32 位,尽管仍然快足以成为一个合理的选择。

.NET Standard 2.1 及更高版本

如果使用的是. NET Standard 2.1 或更高版本,则可以使用System.HashCode结构。有两种使用方法:

HashCode.Combine

Combine方法可用于创建哈希码,最多提供 8 个对象。

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

HashCode.Add

Add方法可帮助您处理集合:

public override int GetHashCode()
{
    var hashCode = new HashCode();
    hashCode.Add(this.object1);
    foreach (var item in this.collection)
    {
        hashCode.Add(item);
    }
    return hashCode.ToHashCode();
}

GetHashCode 变得简单

您可以阅读完整的博客文章 “ GetHashCode Made Easy ”,以获取更多详细信息和评论。

使用范例

public class SuperHero
{
    public int Age { get; set; }
    public string Name { get; set; }
    public List<string> Powers { get; set; }

    public override int GetHashCode() =>
        HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}

实作

public struct HashCode : IEquatable<HashCode>
{
    private const int EmptyCollectionPrimeNumber = 19;
    private readonly int value;

    private HashCode(int value) => this.value = value;

    public static implicit operator int(HashCode hashCode) => hashCode.value;

    public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);

    public static bool operator !=(HashCode left, HashCode right) => !(left == right);

    public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));

    public static HashCode OfEach<T>(IEnumerable<T> items) =>
        items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));

    public HashCode And<T>(T item) => 
        new HashCode(CombineHashCodes(this.value, GetHashCode(item)));

    public HashCode AndEach<T>(IEnumerable<T> items)
    {
        if (items == null)
        {
            return new HashCode(this.value);
        }

        return new HashCode(GetHashCode(items, this.value));
    }

    public bool Equals(HashCode other) => this.value.Equals(other.value);

    public override bool Equals(object obj)
    {
        if (obj is HashCode)
        {
            return this.Equals((HashCode)obj);
        }

        return false;
    }

    public override int GetHashCode() => this.value.GetHashCode();

    private static int CombineHashCodes(int h1, int h2)
    {
        unchecked
        {
            // Code copied from System.Tuple a good way to combine hashes.
            return ((h1 << 5) + h1) ^ h2;
        }
    }

    private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;

    private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
    {
        var temp = startHashCode;

        var enumerator = items.GetEnumerator();
        if (enumerator.MoveNext())
        {
            temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));

            while (enumerator.MoveNext())
            {
                temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
            }
        }
        else
        {
            temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
        }

        return temp;
    }
}

这个不错:

/// <summary>
/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// </summary>
public static class HashCodeHelper
{
    private static int GetHashCodeInternal(int key1, int key2)
    {
        unchecked
        {
           var num = 0x7e53a269;
           num = (-1521134295 * num) + key1;
           num += (num << 10);
           num ^= (num >> 6);

           num = ((-1521134295 * num) + key2);
           num += (num << 10);
           num ^= (num >> 6);

           return num;
        }
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="arr">An array of objects used for generating the 
    /// hash code.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode(params object[] arr)
    {
        int hash = 0;
        foreach (var item in arr)
            hash = GetHashCodeInternal(hash, item.GetHashCode());
        return hash;
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <param name="obj4">The fourth object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and
    /// data structures like a hash table.
    /// </returns>
    public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
        T4 obj4)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
    {
        return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
    }
}

这是如何使用它:

private struct Key
{
    private Type _type;
    private string _field;

    public Type Type { get { return _type; } }
    public string Field { get { return _field; } }

    public Key(Type type, string field)
    {
        _type = type;
        _field = field;
    }

    public override int GetHashCode()
    {
        return HashCodeHelper.GetHashCode(_field, _type);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Key))
            return false;
        var tf = (Key)obj;
        return tf._field.Equals(_field) && tf._type.Equals(_type);
    }
}

https://github.com/dotnet/coreclr/pull/14863 开始 ,有一种新的生成哈希码的方法非常简单!写吧

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

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