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

What is the best algorithm for overriding GetHashCode?

提问人:bitbonk 提问时间:11/5/2008 最后编辑:pokebitbonk 更新时间:5/12/2022 访问量:292126

问:

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

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

.NET 算法 哈希码 gethashcode

评论

48赞 rene 3/23/2012
在阅读了这个问题和下面的文章之后,我可以实现 的覆盖。我希望这对其他人有所帮助。由 Eric Lippert 编写的 GetHashCode 指南和规则GetHashCode
6赞 Thomas Levesque 9/3/2015
“或确定平等”:不!具有相同哈希码的两个对象不一定相等。
4赞 bitbonk 9/3/2015
@ThomasLevesque 你是对的,两个具有相同哈希码的对象不一定相等。但仍然在许多实现中使用。这就是我这句话的意思。 inside 通常用作确定不等式的快捷方式,因为如果两个对象具有不同的哈希码,则它们必须是不相等的对象,并且不必执行其余的相等性检查。GetHashCode()Equals()GetHashCode()Equals()
7赞 NotEnoughData 4/2/2017
@bitbonk 通常,两者都需要查看两个对象的所有字段(如果哈希码相等或未选中,则 Equals 必须这样做)。因此,对 inside 的调用通常是多余的,可能会降低性能。 也可能能够短路,使其速度更快 - 但在某些情况下,哈希码可能会被缓存,使检查更快,因此值得。有关详细信息,请参阅此问题GetHashCode()Equals()GetHashCode()Equals()Equals()GetHashCode()
12赞 Rick Davin 1/15/2020
2020 年 1 月更新:Eric Lippert 的博客位于:learn.microsoft.com/en-us/archive/blogs/ericlippert/...

答:

1803赞 Jon Skeet 11/5/2008 #1

我通常使用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示例中,我使用了显然效果很好的数字 - 但初始值不是素数。(不过,乘法常数素数。我不知道这有多重要。

这比使用哈希码的常见做法要好,主要有两个原因。假设我们有一个包含两个字段的类型:XORint

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

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

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

// 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 文章的链接已损坏,但这是 Internet Archive 中的副本:Eternally Conconfzzled - The Art of Hashing

评论

9赞 bitbonk 11/5/2008
你提到的书中描述的算法实际上更详细一些,它特别描述了对不同数据类型的字段要做什么。例如:对于 long 类型的字段,请使用 (int)(field ^ f >>> 32),而不是简单地调用 GetHashcode。很长。GetHashCodes 就是这样实现的?
15赞 Jon Skeet 11/5/2008
是的,Int64.GetHashCode 正是这样做的。当然,在 Java 中,这需要装箱。这让我想起了 - 是时候添加这本书的链接了......
85赞 CodesInChaos 11/22/2010
23 不是一个好的选择,因为(从 .net 3.5 SP1 开始)假定某些素数具有良好的分布模。23就是其中之一。因此,如果您有一个容量为 23 的字典,则只有最后一个贡献会影响复合哈希码。所以我宁愿使用 29 而不是 23。Dictionary<TKey,TValue>GetHashCode
28赞 Jon Skeet 11/22/2010
@CodeInChaos:只有最后一个贡献会影响存储桶 - 因此,在最坏的情况下,它可能必须查看字典中的所有 23 个条目。它仍然会检查每个条目的实际哈希码,这将是便宜的。如果你有一本这么小的字典,它就不太可能有太大关系了。
25赞 Jon Skeet 1/23/2013
@Vajda:我通常使用 0 作为有效的哈希码 - 这与忽略字段不同。null
4赞 Mark G 11/5/2008 #2

我的大部分工作都是通过数据库连接完成的,这意味着我的类都具有来自数据库的唯一标识符。我总是使用数据库中的 ID 来生成哈希码。

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}

评论

1赞 pero 3/22/2010
这意味着,如果您有对象 Person 和 Account,并且它们都具有 ID = 1,则它们将具有相同的哈希码。这是不行的。
18赞 piers7 3/29/2010
实际上上面的评论是不正确的。总是存在哈希码冲突的可能性(哈希代码仅定位存储桶,而不是单个对象)。因此,对于包含混合对象的哈希代码,这样的实现将导致大量冲突,这是不可取的,但如果哈希表中只有单一类型的对象,那绝对没问题。此外,它不会均匀分布,但是 system.object 上的基本实现也没有,所以我不会太担心它......
3赞 Darrel Lee 11/24/2012
哈希码可以只是 id,因为 id 是一个整数。无需对整数调用 GetHashCode(它是一个标识函数)
3赞 nawfal 4/14/2013
@DarrelLee,但他的_id可能是 Guid。这是一个很好的编码实践,因为意图很明确。_id.GetHashCode
3赞 Jon Hanna 1/15/2014
@1224根据使用模式,由于您给出的原因,它可能很糟糕,但它也可能很棒;如果你有一个这样的数字序列,没有漏洞,那么你就有一个完美的哈希值,比任何算法都能产生。如果您知道是这种情况,您甚至可以依靠它并跳过平等检查。
67赞 Wahid Shalaly 2/23/2009 #3

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

我没有评估它的性能,所以欢迎任何反馈。

评论

29赞 nightcoder 4/4/2010
好吧,如果字段是值类型,它会导致装箱。
7赞 Tim Schmelter 2/24/2014
“以后可以通过捕获 OverflowException 来增强” 其重点是避免 overflow 上的异常,这是 上所期望的。因此,如果值溢出并且根本不会造成伤害,这并没有错。uncheckedGetHashCodeint
2赞 Nathan Adams 4/17/2015
此算法的一个问题是,任何充满 null 的数组都将始终返回 0,无论其长度如何
3赞 James Newton-King 7/20/2016
此帮助程序方法还分配一个新对象
2赞 David Schwartz 10/29/2016
正如@NathanAdams提到的,完全跳过的事实可能会给你带来意想不到的结果。与其跳过它们,不如只使用一些常量值,而不是 when 为 null。nullinput[i].GetHashCode()input[i]
31赞 Bert Huijben 2/23/2009 #4

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

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

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

评论

12赞 sleske 4/15/2010
“在大多数情况下,当 Equals() 比较多个字段时,GetHash() 是否在一个字段或多个字段上进行哈希处理并不重要。”这是危险的建议,因为对于仅在未散列字段中不同的对象,您将遇到散列冲突。如果这种情况经常发生,基于哈希的集合(HashMap、HashSet 等)的性能将下降(在最坏的情况下高达 O(n))。
12赞 sleske 4/15/2010
这实际上发生在 Java 中:在早期版本的 JDK 中,String.hashCode() 只考虑字符串的开头;如果您在 HashMap 中使用字符串作为键,这会导致性能问题,而这些键仅在末尾有所不同(这很常见,例如对于 URL)。因此,算法发生了变化(我相信在 JDK 1.2 或 1.3 中)。
4赞 Bert Huijben 4/16/2010
如果那个字段“提供了良好的分布”(我回答的最后一部分),那么一个字段就足够了。如果它不能提供良好的分布,那么(就在那时)你需要另一个计算。(例如,仅使用另一个提供良好分布的字段,或使用多个字段)
0赞 supercat 9/8/2013
我不认为执行内存分配有问题,只要它只在第一次使用时这样做(后续调用只是返回缓存的结果)。重要的不是应该竭尽全力避免碰撞,而是应该避免“系统性”碰撞。如果类型有两个字段,并且这些字段经常相差 1,则哈希值 将为此类记录的 90% 分配 1、2、4 或 8 的哈希值。使用 [未经检查的算术] 可能会产生更多冲突......GetHashCodeintoldXnewXoldX^newXoldX+newX
1赞 supercat 9/8/2013
...比更复杂的函数,但是如果每个哈希值有两个关联的事物,则具有 500,000 个不同哈希值的 1,000,000 个事物的集合将非常好,如果一个哈希值有 500,001 个事物而其他事物各有一个,则非常糟糕。
111赞 nightcoder 4/5/2010 #5

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

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

评论

5赞 nawfal 4/14/2013
无需单独使用,因为它已经T[]IEnumerable<T>
5赞 nawfal 4/14/2013
您可以重构这些方法,并将核心逻辑限制为一个函数
15赞 Chui Tey 8/23/2013
顺便说一句,31 是 CPU 上的移位和减法,速度非常快。
5赞 ANeves 2/9/2015
@nightcoder您可以使用参数
7赞 Pharap 6/12/2015
@ChuiTey 这是所有梅森素数的共同点。
13赞 Magnus 10/7/2010 #6

这是一个很好的:

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

评论

1赞 Michael Stum 10/8/2010
密钥是如何确定的?GetHashCode() 不接受任何参数,因此它需要使用两个需要以某种方式确定的 Key 来调用这个参数。对不起,没有进一步的解释,这看起来很聪明,但不是那么好。
0赞 gehho 10/8/2010
为什么需要通用重载?类型并不重要(并且未在代码中使用),因为所有对象都有一个方法,因此您始终可以将该方法与 array 参数一起使用。还是我在这里遗漏了什么?GetHashCode()params
4赞 CodesInChaos 11/22/2010
当您使用对象而不是泛型时,您将获得装箱和内存分配,这是您在 GetHashCode 中不需要的。因此,泛型是必经之路。
1赞 sehe 4/23/2011
尾随的移位/异或步骤(有一个代码味道:它们不依赖于任何输入,对我来说看起来非常多余。h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15);
1赞 nawfal 12/25/2012
@Magnus是的,我会删除我的原始评论。请注意,这可能不如这里的其他一些解决方案快,但正如您所说,这并不重要。分布很棒,比这里的大多数解决方案都要好,所以从我这里得到+1!:)
549赞 Rick Love 1/8/2011 #7

ValueTuple - C# 7 更新

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

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

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

匿名类型(原始答案)

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

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

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

评论

90赞 digEmAll 1/8/2011
是的,匿名实现非常有效(顺便说一句,它与 Jon Skeet 的答案中的相同),但此解决方案的唯一问题是您在任何调用时都会生成一个新实例。这可能有点开销,尤其是在密集访问大型哈希集合的情况下......GetHashCodeGetHashCode
5赞 Rick Love 4/3/2011
@digEmAll 很好,我没有考虑创建新对象的开销。乔恩·斯基特(Jon Skeet)的回答是最有效的,不会使用拳击。(@Kumba要解决 VB 中的未选中问题,只需使用 Int64(长整型)并在计算后将其截断。
20赞 David Osborne 8/20/2014
VB.NET 必须在匿名类型创建中使用 Key:否则,GetHashCode 不会为具有相同“标识”属性的不同对象返回相同的哈希码。New With {Key PropA}.GetHashCode()
4赞 Rick Love 10/21/2015
@Keith在这种情况下,我会考虑将 IEnumerable 保存为某个位置的列表值,而不是在每次计算哈希码时枚举它。在许多情况下,每次在 GetHashCode 中计算 ToList 可能会损害性能。
9赞 cactuaroid 8/16/2018
对于那些喜欢这个的人,现在可以在 C#7 上使用,无需 GC 压力@digEmAll顾虑。快速简单的哈希码组合(PropA, PropB, PropC, PropD).GetHashCode()
8赞 bitbonk 3/22/2011 #8

这是我的简单方法。为此,我使用了经典的构建器模式。它是类型安全的(没有装箱/取消装箱),并且还与 .NET 2.0 兼容(没有扩展方法等)。

它的使用方式如下:

public override int GetHashCode()
{
    HashBuilder b = new HashBuilder();
    b.AddItems(this.member1, this.member2, this.member3);
    return b.Result;
} 

这是 acutal builder 类:

internal class HashBuilder
{
    private const int Prime1 = 17;
    private const int Prime2 = 23;
    private int result = Prime1;

    public HashBuilder()
    {
    }

    public HashBuilder(int startHash)
    {
        this.result = startHash;
    }

    public int Result
    {
        get
        {
            return this.result;
        }
    }

    public void AddItem<T>(T item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

    public void AddItems<T1, T2>(T1 item1, T2 item2)
    {
        this.AddItem(item1);
        this.AddItem(item2);
    }

    public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
    }

    public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3, 
        T4 item4)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
    }

    public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3, 
        T4 item4, T5 item5)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
        this.AddItem(item5);
    }        

    public void AddItems<T>(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}

评论

0赞 nawfal 4/14/2013
您可以避免在 gethashcode 函数中创建对象,就像 Mangus 的答案一样。只需调用该死的静态哈希函数(谁关心起始哈希)。此外,您可以在帮助程序类中更频繁地使用方法(而不是每次调用)。AddItems<T>(params T[] items)AddItem(T)
0赞 nawfal 4/14/2013
你发现经常使用有什么好处?this.result * Prime2 * item.GetHashCode()this.result * Prime2 + item.GetHashCode()
0赞 bitbonk 4/15/2013
我不能更频繁地使用,因为等等。AddItems<T>(params T[] items)typeof(T1) != typeof(T2)
2赞 Hassan Faghihi 12/1/2012 #9

Microsoft 在几种散列方式中处于领先地位...

//for classes that contain a single int value
return this.value;

//for classes that contain multiple int value
return x ^ y;

//for classes that contain single number bigger than int    
return ((int)value ^ (int)(value >> 32)); 

//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();

//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode(); 

我可以猜到对于多个大 int,您可以使用这个:

int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;

多类型也是如此:首先将所有值转换为使用,然后 int 值将被异或化,结果就是您的哈希值。intGetHashCode()

对于那些使用哈希作为 ID(我的意思是唯一值)的人来说,哈希自然被限制在位数,我认为哈希算法是 5 个字节,至少是 MD5。

您可以将多个值转换为哈希值,其中一些值是相同的,因此请勿将其用作标识符。(也许有一天我会使用你的组件)

评论

8赞 Jon Hanna 1/14/2014
使用整数来制作哈希码是一种众所周知的反模式,它往往会导致与实际值发生特别多的冲突。
0赞 Hassan Faghihi 9/16/2015
这里的每个人都使用整数,并且从来没有任何保证哈希值是相同的,它只是试图尽可能多地变化,因为很少发生碰撞。
0赞 Jon Hanna 9/16/2015
是的,但你的第二个和第五个不要试图避免碰撞。
1赞 Jon Hanna 9/19/2015
是的,这种反模式很常见。
2赞 Jon Hanna 9/21/2015
有一个平衡需要达到。使用像 Spookyhash 这样非常好的哈希代码,你会得到更好的冲突避免,但它的计算时间比任何一个都要长得多(但当涉及到对大量数据进行哈希处理时,Spookyhash 非常快)。在 xoring 之前对其中一个值进行简单的偏移只是减少碰撞的边际额外成本。质数乘法再次增加时间和质量。因此,在轮班或多班之间哪个更好是值得商榷的。虽然普通异或经常在真实数据上有很多冲突,但最好避免
59赞 Şafak Gür 9/4/2013 #10

这是我使用 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 readonly 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);
}

编辑(2018 年 5 月):getter 现在是 JIT 内部函数 - Stephen Toub 在这篇博文中提到了拉取请求EqualityComparer<T>.Default

评论

1赞 Bill Barry 9/6/2014
我会将三级运算符的行更改为:var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode();
0赞 Martin Liversage 9/14/2014
我相信三元运算符将编译为一条指令,如果是值类型,则该指令将分配内存。相反,您可以使用 which 将编译为该方法的虚拟调用。obj != nullboxTobj.Equals(null)Equals
0赞 Şafak Gür 6/15/2015
因为。它不会返回相同的值。this.hashCode != h
0赞 Erik Karlsson 6/15/2015
对不起,设法删除我的评论而不是编辑它。创建一个新的结构体,然后将 hashCode 更改为 non-readonly 并执行: “unchecked { this.hashCode ^= h * 397;例如,返回这个;“?
0赞 Şafak Gür 6/15/2015
不可变性有它的好处(为什么可变结构是邪恶的?关于性能,我所做的非常便宜,因为它不会在堆中分配任何空间。
27赞 Jon Hanna 1/14/2014 #11

直到最近,我的答案与乔恩·斯基特(Jon Skeet)的答案非常接近。但是,我最近启动了一个使用二次幂哈希表的项目,即内部表大小为 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);
  }
}

然后我的 2 次幂哈希表不再糟糕了。

这让我感到不安,因为上述方法应该不起作用。或者更准确地说,除非原版以一种非常特殊的方式很差,否则它不应该起作用。GetHashCode()

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

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

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

编辑:我还使用了开放式寻址,这也会增加对冲突的敏感度,也许比它是二次方的事实更重要。

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

我过去编写的所有 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();
}

它还需要种子值,因此,如果您需要处理不受信任的输入并希望防范哈希 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 的原生版本,尽管它是 C# 版本。它的问题在于,它自己认为精度很重要,而它自己则不然。两者都是有效的选择,但不是那样混合。在实现你自己的版本时,你需要选择做一个,或者另一个,但我不知道你想要哪个。decimalGetHashCode()Equals()

‡作为比较。如果在字符串上使用,则 64 位上的 SpookyHash 比 32 位快得多,而 32 位比 64 位略快,这比 32 位上的 SpookyHash 快得多,但仍然足够快,是一个合理的选择。string.GetHashCode()string.GetHashCode()

评论

0赞 supercat 4/25/2014
当将多个哈希值合并为一个时,我倾向于将值用于中间结果,然后将最终结果压缩为 .这似乎是个好主意吗?我担心的是,例如使用 hash=(hash*31)+nextField,那么匹配值对只会影响哈希的上 27 位。让计算扩展到 a 并将内容包装起来将最大限度地减少这种危险。longintlong
0赞 Jon Hanna 4/25/2014
@supercat这取决于您最终咀嚼的分布。SpookilySharp 库将确保分发是好的,理想情况下(因为它不需要创建对象)通过将指针传递给 blittable 类型,或传递它直接处理的枚举对象之一,但如果您还没有 blittable 数据或合适的枚举,那么根据上面的答案使用多个值进行调用就可以了。.Update()
0赞 Eamon Nerbonne 6/1/2014
@JonHanna你愿意更准确地描述你遇到的问题行为吗?我正在尝试实现一个使实现值对象变得微不足道的库(ValueUtils),我希望有一个测试集,在二次幂哈希表中证明哈希混溶性差。
0赞 Jon Hanna 6/2/2014
@EamonNerbonne我真的没有比“总体时间慢”更精确的东西了。正如我在编辑中添加的那样,我使用开放式寻址的事实可能比 2 的幂因素更重要。我确实计划在某个特定项目上做一些测试用例,在这些项目中,我将比较几种不同的方法,因此在那之后我可能会为您提供更好的答案,尽管这不是高优先级(一个没有迫切需求的个人项目,所以我会在到达它时进行处理......
0赞 Eamon Nerbonne 6/2/2014
@JonHanna:是的,我知道个人项目进度如何——祝你好运!无论如何,我发现我没有很好地表达最后一条评论:我的意思是询问有问题的意见,而不一定是导致的问题的细节。我很想把它作为一个测试集(或测试集的灵感)。无论如何 - 祝你的宠物项目好运:-)。
11赞 Scott Wegner 1/21/2014 #12

这是 Jon Skeet 在上面发布的算法的另一个流畅实现,但不包括分配或装箱操作:

public static class Hash
{
    public const int Base = 17;

    public static int HashObject(this int hash, object obj)
    {
        unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
    }

    public static int HashValue<T>(this int hash, T value)
        where T : struct
    {
        unchecked { return hash * 23 + value.GetHashCode(); }
    }
}

用法:

public class MyType<T>
{
    public string Name { get; set; }

    public string Description { get; set; }

    public int Value { get; set; }

    public IEnumerable<T> Children { get; set; }

    public override int GetHashCode()
    {
        return Hash.Base
            .HashObject(this.Name)
            .HashObject(this.Description)
            .HashValue(this.Value)
            .HashObject(this.Children);
    }
}

编译器将确保由于泛型类型约束而不与类一起调用。但是没有编译器支持,因为添加泛型参数也会添加装箱操作。HashValueHashObject

0赞 HokieMike 9/29/2014 #13

我遇到了浮点数和小数的问题,使用上面选择的实现作为答案。

此测试失败(浮点数;即使我将 2 个值切换为负值,哈希值也相同):

        var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
        var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

但是这个测试通过了(使用整数):

        var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
        var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

我更改了我的实现,不将 GetHashCode 用于原始类型,它似乎效果更好

    private static int InternalComputeHash(params object[] obj)
    {
        unchecked
        {
            var result = (int)SEED_VALUE_PRIME;
            for (uint i = 0; i < obj.Length; i++)
            {
                var currval = result;
                var nextval = DetermineNextValue(obj[i]);
                result = (result * MULTIPLIER_VALUE_PRIME) + nextval;

            }
            return result;
        }
    }



    private static int DetermineNextValue(object value)
    {
        unchecked
        {

                int hashCode;
                if (value is short
                    || value is int
                    || value is byte
                    || value is sbyte
                    || value is uint
                    || value is ushort
                    || value is ulong
                    || value is long
                    || value is float
                    || value is double
                    || value is decimal)
                {
                    return Convert.ToInt32(value);
                }
                else
                {
                    return value != null ? value.GetHashCode() : 0;
                }
        }
    }

评论

2赞 Mark Hurd 9/30/2014
如果您另有打算,则不会影响 : , , , 并且可能全部溢出到这里。uncheckedConvert.ToInt32uintlongfloatdoubledecimal
3赞 Dbl 10/22/2014 #14

与 nightcoder 的解决方案非常相似,只是如果您愿意,可以更轻松地提高素数。

PS:这是你吐在嘴里的时候之一,知道这可以重构为一个有 9 个默认值的方法,但它会更慢,所以你只是闭上眼睛并试图忘记它。

/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
    private const int PrimeOne = 17;
    private const int PrimeTwo = 23;

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();
            hash = hash * PrimeTwo + arg10.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();

            return hash;
        }
    }

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

            return hash;
        }
    }

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

            return hash;
        }
    }

    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();

            return hash;
        }
    }
}

评论

2赞 JJS 12/28/2016
不处理 null。
6赞 Charles Burns 9/2/2016 #15

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

// 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;
    }
}
25赞 James Ko 11/23/2017 #16

截至 https://github.com/dotnet/coreclr/pull/14863,有一种生成哈希码的新方法,超级简单!只需编写

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

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

评论

0赞 Dan J 12/14/2017
这看起来像是一个甜蜜的补充......有什么方法可以知道将附带哪个版本的 .NET Core?
1赞 James Ko 12/14/2017
@DanJ 多么巧合的是,corefx 的更改在您发表评论前几个小时就合并了:)该类型计划在 .NET Core 2.1 中提供。HashCode
0赞 Dan J 12/14/2017
这真是太棒了 - 而且周转时间相当长。点赞。:)
0赞 James Ko 12/16/2017
@DanJ 更好的消息是,它现在应该在 dotnet-core MyGet 源上托管的 CoreFX 的夜间版本上可用。
0赞 Dan J 12/18/2017
甜蜜的 - 这对我的工作没有帮助,因为我们不是那么前沿,但很高兴知道。干杯!
6赞 Timo 5/15/2018 #17

如果我们的房产不超过 8 个(希望如此),这是另一种选择。

ValueTuple是一个结构,似乎有一个可靠的实现。GetHashCode

这意味着我们可以简单地这样做:

// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();

让我们看一下 .NET Core 的当前实现。ValueTupleGetHashCode

这是来自 ValueTuple

    internal static int CombineHashCodes(int h1, int h2)
    {
        return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
    }

    internal static int CombineHashCodes(int h1, int h2, int h3)
    {
        return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
    }

这是来自 HashHelper

    public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();

    public static int Combine(int h1, int h2)
    {
        unchecked
        {
            // RyuJIT optimizes this to use the ROL instruction
            // Related GitHub pull request: dotnet/coreclr#1830
            uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
            return ((int)rol5 + h1) ^ h2;
        }
    }

英文:

  • 向左旋转(圆周移位)h1 5 个位置。
  • 将结果和 h1 相加。
  • 用 h2 对结果进行异或。
  • 首先对 { static random seed, h1 } 执行上述操作。
  • 对于每一项,对上一项结果和一项(例如 h2)执行操作。

很高兴更多地了解此 ROL-5 哈希代码算法的属性。

遗憾的是,为了我们自己而推迟可能没有我们希望和期望的那么快。相关讨论中的此评论说明了直接调用的性能更高。另一方面,这是内部的,所以我们必须复制代码,牺牲我们在这里获得的大部分内容。此外,我们有责任记住首先使用随机种子。我不知道如果我们跳过这一步会有什么后果。ValueTupleGetHashCodeHashHelpers.CombineCombine

评论

1赞 cactuaroid 8/17/2018
假设为 0 忽略它,等于因此它与 相同。根据此页面,它被称为“改良的伯恩斯坦”。h1 >> 27h1 << 5h1 * 32h1 * 33 ^ h2
1赞 Steven Coco 4/28/2019 #18

这是一个静态帮助程序类,用于实现 Josh Bloch 的实现;并提供显式重载来“防止”装箱,并专门为长原语实现哈希值。

您可以传递与您的 equals 实现匹配的字符串比较。

由于 Hash 输出始终为 int,因此您可以只链接 Hash 调用。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;


namespace Sc.Util.System
{
    /// <summary>
    /// Static methods that allow easy implementation of hashCode. Example usage:
    /// <code>
    /// public override int GetHashCode()
    ///     => HashCodeHelper.Seed
    ///         .Hash(primitiveField)
    ///         .Hsh(objectField)
    ///         .Hash(iEnumerableField);
    /// </code>
    /// </summary>
    public static class HashCodeHelper
    {
        /// <summary>
        /// An initial value for a hashCode, to which is added contributions from fields.
        /// Using a non-zero value decreases collisions of hashCode values.
        /// </summary>
        public const int Seed = 23;

        private const int oddPrimeNumber = 37;


        /// <summary>
        /// Rotates the seed against a prime number.
        /// </summary>
        /// <param name="aSeed">The hash's first term.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int rotateFirstTerm(int aSeed)
        {
            unchecked {
                return HashCodeHelper.oddPrimeNumber * aSeed;
            }
        }


        /// <summary>
        /// Contributes a boolean to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aBoolean">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, bool aBoolean)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (aBoolean
                                ? 1
                                : 0);
            }
        }

        /// <summary>
        /// Contributes a char to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aChar">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, char aChar)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aChar;
            }
        }

        /// <summary>
        /// Contributes an int to the developing HashCode seed.
        /// Note that byte and short are handled by this method, through implicit conversion.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aInt">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, int aInt)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aInt;
            }
        }

        /// <summary>
        /// Contributes a long to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aLong">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, long aLong)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (int)(aLong ^ (aLong >> 32));
            }
        }

        /// <summary>
        /// Contributes a float to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aFloat">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, float aFloat)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + Convert.ToInt32(aFloat);
            }
        }

        /// <summary>
        /// Contributes a double to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aDouble">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, double aDouble)
            => aSeed.Hash(Convert.ToInt64(aDouble));

        /// <summary>
        /// Contributes a string to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aString">The value to contribute.</param>
        /// <param name="stringComparison">Optional comparison that creates the hash.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(
                this int aSeed,
                string aString,
                StringComparison stringComparison = StringComparison.Ordinal)
        {
            if (aString == null)
                return aSeed.Hash(0);
            switch (stringComparison) {
                case StringComparison.CurrentCulture :
                    return StringComparer.CurrentCulture.GetHashCode(aString);
                case StringComparison.CurrentCultureIgnoreCase :
                    return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.InvariantCulture :
                    return StringComparer.InvariantCulture.GetHashCode(aString);
                case StringComparison.InvariantCultureIgnoreCase :
                    return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.OrdinalIgnoreCase :
                    return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
                default :
                    return StringComparer.Ordinal.GetHashCode(aString);
            }
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// Each element may be a primitive, a reference, or a possibly-null array.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, IEnumerable aArray)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (object item in aArray) {
                ++countPlusOne;
                if (item is IEnumerable arrayItem) {
                    if (!object.ReferenceEquals(aArray, arrayItem))
                        aSeed = aSeed.Hash(arrayItem); // recursive call!
                } else
                    aSeed = aSeed.Hash(item);
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// You must provide the hash function for each element.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <param name="hashElement">Required: yields the hash for each element
        /// in <paramref name="aArray"/>.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (T item in aArray) {
                ++countPlusOne;
                aSeed = aSeed.Hash(hashElement(item));
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null object to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, object aObject)
        {
            switch (aObject) {
                case null :
                    return aSeed.Hash(0);
                case bool b :
                    return aSeed.Hash(b);
                case char c :
                    return aSeed.Hash(c);
                case int i :
                    return aSeed.Hash(i);
                case long l :
                    return aSeed.Hash(l);
                case float f :
                    return aSeed.Hash(f);
                case double d :
                    return aSeed.Hash(d);
                case string s :
                    return aSeed.Hash(s);
                case IEnumerable iEnumerable :
                    return aSeed.Hash(iEnumerable);
            }
            return aSeed.Hash(aObject.GetHashCode());
        }


        /// <summary>
        /// This utility method uses reflection to iterate all specified properties that are readable
        /// on the given object, excluding any property names given in the params arguments, and
        /// generates a hashcode.
        /// </summary>
        /// <param name="aSeed">The developing hash code, or the seed: if you have no seed, use
        /// the <see cref="Seed"/>.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <param name="propertySelector"><see cref="BindingFlags"/> to select the properties to hash.</param>
        /// <param name="ignorePropertyNames">Optional.</param>
        /// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashAllProperties(
                this int aSeed,
                object aObject,
                BindingFlags propertySelector
                        = BindingFlags.Instance
                        | BindingFlags.Public
                        | BindingFlags.GetProperty,
                params string[] ignorePropertyNames)
        {
            if (aObject == null)
                return aSeed.Hash(0);
            if ((ignorePropertyNames != null)
                    && (ignorePropertyNames.Length != 0)) {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (!propertyInfo.CanRead
                            || (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
                        continue;
                    aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            } else {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (propertyInfo.CanRead)
                        aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            }
            return aSeed;
        }


        /// <summary>
        /// NOTICE: this method is provided to contribute a <see cref="KeyValuePair{TKey,TValue}"/> to
        /// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on the Key or Value here if that itself is a KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePair">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
            => aSeed.Hash(keyValuePair.Key)
                    .Hash(keyValuePair.Value);

        /// <summary>
        /// NOTICE: this method is provided to contribute a collection of <see cref="KeyValuePair{TKey,TValue}"/>
        /// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
        /// KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePairs">The values to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeysAndValues<TKey, TValue>(
                this int aSeed,
                IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
        {
            if (keyValuePairs == null)
                return aSeed.Hash(null);
            foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
                aSeed = aSeed.HashKeyAndValue(keyValuePair);
            }
            return aSeed;
        }
    }
}

评论

0赞 Steven Coco 5/9/2019
Yipes:我发现了一个错误!该方法已修复:它调用 .HashKeysAndValuesHashKeyAndValue
148赞 Muhammad Rehan Saeed 6/11/2019 #19

System.HashCode

如果使用的是 .NET Standard 2.1 或更高版本,则可以使用 System.HashCode 结构。在早期的框架上,它可从 Microsoft.Bcl.HashCode 包中获得。有两种使用方法:

哈希代码.Combine

该方法可用于创建哈希代码,最多给定八个对象。Combine

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

哈希代码.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”,了解更多详细信息和评论。System.HashCode

使用示例

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

什么是好的算法?

性能

计算哈希码的算法需要快速。一个简单的算法通常会是一个更快的算法。不分配额外内存的处理器也将减少对垃圾回收的需求,这反过来也会提高性能。

特别是在 C# 哈希函数中,您经常使用停止溢出检查的关键字来提高性能。unchecked

确定性

哈希算法必须是确定性的,即给定相同的输入,它必须始终产生相同的输出。

减少碰撞

计算哈希代码的算法需要将哈希冲突保持在最小值。哈希冲突是指对两个不同对象的两次调用产生相同的哈希代码时发生的情况。请注意,碰撞是允许的(有些人有误解,认为它们不是),但应将其保持在最低限度。GetHashCode

许多哈希函数都包含幻数,如 或 。这些是特殊的素,与使用非素数相比,由于其数学特性有助于减少哈希冲突。1723

哈希均匀性

一个好的哈希函数应该在其输出范围内尽可能均匀地映射预期的输入,即它应该根据均匀分布的输入输出广泛的哈希值。它应该具有哈希均匀性。

预防的 DoS

在 .NET Core 中,每次重启应用程序时,都会获得不同的哈希代码。这是一项安全功能,用于防止拒绝服务攻击 (DoS)。对于 .NET Framework,通过添加以下 App.config 文件来启用此功能:

<?xml version ="1.0"?>  
<configuration>  
   <runtime>  
      <UseRandomizedStringHashAlgorithm enabled="1" />  
   </runtime>  
</configuration>

由于此功能,哈希代码不应在创建它们的应用程序域之外使用,不应将其用作集合中的键字段,并且不应保留它们。

在此处阅读有关此内容的更多信息。

加密安全?

该算法不必是加密哈希函数。这意味着它不必满足以下条件:

  • 生成生成给定哈希值的消息是不可行的。
  • 查找具有相同哈希值的两条不同消息是不可行的。
  • 对消息的微小更改应使哈希值发生如此广泛的更改,以致新哈希值看起来与旧哈希值不相关(雪崩效应)。

评论

4赞 Timo 7/10/2020
这是一个很好的答案。此外,您可以考虑将“速度”更改为“性能”,并添加无分配属性。内置类型也满足了这一点。HashCode
0赞 Thiago Silva 2/18/2021
这与上面@ricklove最近更新的答案相比如何?ValueTuple.GetHashCode()
3赞 Muhammad Rehan Saeed 2/18/2021
这是一个静态方法,它不会分配任何东西,而将从在堆栈上分配开始。HashCode.CombineValueTuple
3赞 Amos Egel 3/9/2021
HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers)- 这是一个很好的语法:)
0赞 maraaaaaaaa 12/31/2021
they should never be used as key fields in a collection,这难道不是哈希码的全部意义吗?哈希表、哈希集、字典的存在?
0赞 Ivan Sanz Carasa 4/20/2020 #20

如果你想从HashCodenetstandard2.1

public static class HashCode
{
    public static int Combine(params object[] instances)
    {
        int hash = 17;

        foreach (var i in instances)
        {
            hash = unchecked((hash * 31) + (i?.GetHashCode() ?? 0));
        }

        return hash;
    }
}

注意:如果与 一起使用,它将由于装箱而分配内存struct

0赞 ivan.ukr 1/26/2021 #21

可以尝试采用 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());
  }
}
-1赞 t0b4cc0 2/18/2021 #22

我想将我的最新发现添加到我经常回来的这个线程中。

我当前的 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是属性。如果微软开发人员使用此功能,它可能不是一个太糟糕的解决方案。