题 覆盖System.Object.GetHashCode的最佳算法是什么?


在.NET中 System.Object.GetHashCode 在整个.NET基类库中,很多地方都使用了方法。特别是在快速查找集合中的项目或确定相等性时。是否有关于如何实现的标准算法/最佳实践 GetHashCode 覆盖我的自定义类,所以我不降低性能?


1218
2017-11-04 20:53


起源


在阅读了这个问题和下面的文章后,我可以实现覆盖 GetHashCode。我希望这会对其他人有所帮助。 Eric Lippert编写的GetHashCode指南和规则 - rene
“或确定平等”:不!具有相同哈希码的两个对象不一定相等。 - Thomas Levesque
@ThomasLevesque你是对的,具有相同哈希码的两个对象不一定相等。但是仍然 GetHashCode() 用于非常多的实现 Equals()。这就是我对该陈述的意思。 GetHashCode() 内 Equals() 通常用作确定的快捷方式 不等式,因为如果两个对象有一个 不同 哈希码它们必须是不相等的对象,并且不必执行其余的相等检查。 - bitbonk
@bitbonk通常都是 GetHashCode() 和 Equals() 需要查看两个对象的所有字段(如果哈希码相等或未经检查,则Equals必须执行此操作)。因此,打电话给 GetHashCode() 内 Equals() 通常是多余的,可能会降低性能。 Equals() 也可以短路,使其更快 - 但在某些情况下,哈希码可以被缓存,使得 GetHashCode() 检查更快,所以值得。看到 这个问题 更多。 - NotEnoughData


答案:


我通常会选择像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;
    }
}

正如评论中所指出的,你可能会发现最好选择一个大的素数乘以。显然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:

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

1362
2017-11-04 20:56



你提到的书中描述的算法实际上更加详细一些,它特别描述了为不同数据类型的字段做什么。例如:对于长期使用类型的字段(int)(字段^ f >>> 32)而不是简单地调用GetHashcode。是long.GetHashCodes实现了那种方式? - bitbonk
是的,Int64.GetHashCode正是这样做的。当然,在Java中需要拳击。这让我想起了 - 给这本书添加一个链接的时间...... - Jon Skeet
23是不错的选择,因为(截至.net 3.5 SP1) Dictionary<TKey,TValue> 假定以某些素数为模的良好分布。 23是其中之一。因此,如果您有一个容量为23的词典,那么只有最后一个贡献 GetHashCode 影响复合哈希码。所以我宁愿用29而不是23。 - CodesInChaos
@CodeInChaos:只有最后一个贡献会影响存储桶 - 所以在最坏的情况下,它可能需要查看 全部23 字典中的条目。它仍然会检查每个条目的实际哈希码,这将是便宜的。如果你有一本很小的字典,那就不太重要了。 - Jon Skeet
@Vajda:我通常使用0作为有效的哈希码 null  - 这与忽略该字段不同。 - Jon Skeet


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

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

这适用于任何数量的属性。它不使用拳击或额外资源。它只是使用已在框架中为匿名类型实现的算法。


302
2018-01-07 21:38



是的,匿名 GetHashCode 实现是非常有效的(顺便说一句,它与Jon Skeet的回答相同),但这个解决方案的唯一问题是你在任何地方生成一个新实例 GetHashCode 呼叫。它可能有点开销,特别是在密集访问大散列集合的情况下...... - digEmAll
这适用于VB w / .NET 4.0,但查看IL,它正在使用 box 调用,因为该类型使用泛型。没有取消装箱,但从我在这里阅读,仅仅存在拳击表明这可能有点低效。似乎是VB的唯一选择,因为没有相应的 checked/`未选中。 - Kumba
@digEmAll好点,我没有考虑创建新对象的开销。 Jon Skeet的答案是最有效的,不会使用拳击。 (@Kumba要解决VB中的未选中状态,只需使用Int64(long)并在计算后截断它。) - Rick Love
可以这么说 new { PropA, PropB, PropC, PropD }.GetHashCode() 太 - sehe
VB.NET必须在匿名类型创建中使用Key: New With {Key PropA}.GetHashCode() 否则,GetHashCode将不会为具有相同“标识”属性的不同对象返回相同的哈希码。 - David Osborne


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

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

94
2018-04-04 18:26



没必要 T[] 已经分开了 IEnumerable<T> - nawfal
您可以重构这些方法并将核心逻辑限制为一个函数 - nawfal
顺便提一下,31是CPU上的移位和减法,这是非常快的。 - Chui Tey
@nightcoder你可以使用 PARAMS。 - ANeves
@ChuiTey这就是全部 Mersenne Primes 有共同点。 - Pharap


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

我没有评估其表现,所以欢迎任何反馈。


57
2018-02-23 11:46



好吧,如果字段是值类型,它将导致装箱。 - nightcoder
+1为 null 检查大多数其他(否则可能更好)的答案都没有包括在内。 - Mark Hurd
“以后可以通过捕获OverflowException来增强”的全部内容 unchecked 是为了避免需要溢出的异常 GetHashCode。因此,如果值溢出则不正确 int 并且它根本没有伤害。 - Tim Schmelter
该算法的一个问题是,任何充满空值的数组总是返回0,无论其长度如何 - Nathan Adams
这个辅助方法也分配了一个新对象[] - James Newton-King


这是我的帮助类使用 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);
}

马丁评论后更新:

obj != null 导致拳击所以我切换到默认的比较器。

编辑(2018年5月):

EqualityComparer<T>.Default getter现在是JIT内在的 - 拉请求 斯蒂芬·图布提到了 这篇博文


49
2017-09-04 12:32



我会改变第三运算符的行: var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode(); - Bill Barry
我相信三元运算符 obj != null 将编译成一个 box 将指定内存的指令 T 是一种值类型。相反,你可以使用 obj.Equals(null) 这将编译为虚拟调用 Equals 方法。 - Martin Liversage
因为 this.hashCode != h。它不会返回相同的值。 - Şafak Gür
抱歉,设法删除我的评论而不是编辑它。是否更有利于创建一个新结构然后将hashCode更改为非readonly并执行:“unchecked {th​​is.hashCode ^ = h * 397;}返回此结果;”例如? - Erik Karlsson
不变性有其好处(为什么可变结构是邪恶的?)。关于性能,我做的很便宜,因为它没有在堆中分配任何空间。 - Şafak Gür


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

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

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


26
2018-02-23 11:55



“在大多数情况下,Equals()比较多个字段,如果你的GetHash()在一个字段或多个字段上进行哈希处理并不重要。”这是一个危险的建议,因为对于仅在非散列字段中不同的对象,您将获得散列冲突。如果经常发生这种情况,基于散列的集合(HashMap,HashSet等)的性能将降低(在最坏的情况下最多为O(n))。 - sleske
这实际上发生在Java中:在早期版本的JDK String.hashCode()中只考虑字符串的开头;如果你在字符串中使用字符串作为HashMaps中的密钥,这会导致性能问题,这种密钥在最后只有不同(例如对于URL来说很常见)。因此改变了算法(我认为在JDK 1.2或1.3中)。 - sleske
如果那个字段“提供了良好的分布”(我的答案的最后一部分),那么一个字段就足够了......如果它 不提供良好的分配,然后(然后)你需要另一个计算。 (例如,只使用另一个领域 不 提供良好的分发,或使用多个领域) - Bert Huijben
我不认为有问题 GetHashCode 执行内存分配, 只要它第一次使用它才会这样做 (后续调用只返回缓存结果)。重要的不是人们应该竭尽全力避免碰撞,而是应该避免“系统性”碰撞。如果一个类型有两个 int 领域 oldX 和 newX 经常相差一个,哈希值为 oldX^newX 将分配90%的此类记录哈希值为1,2,4或8.使用 oldX+newX [未经检查的算术]可能会产生更多碰撞...... - supercat
...而不是更复杂的功能,但如果每个哈希值有两个相关的东西,那么拥有500,000个不同哈希值的1,000,000个东西的集合将非常好,如果一个哈希值具有500,001个事物而其他哈希值各有一个则非常糟糕。 - supercat


直到最近,我的答案将非常接近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);
  }
}

然后我的二次幂哈希表再也没有了。

这让我感到不安,因为上述情况不应该奏效。或者更确切地说,除非是原件,否则它不应该起作用 GetHashCode() 以一种非常特殊的方式很穷。

重新混合哈希码不能改进很好的哈希码,因为唯一可能的效果是我们引入了一些冲突。

重新混合哈希码不能改善可怕的哈希码,因为唯一可能的效果是我们改变例如哈希码。值53的大量碰撞到大量的值18,3487,291。

重新混合哈希码只能改进哈希码,这种哈希码在避免整个范围内的绝对冲突方面至少做得相当好(232 可能的值)但是在模块化以便在哈希表中实际使用时,很难避免冲突。虽然两个幂表的简单模数使这一点变得更加明显,但它对更常见的素数表也产生了负面影响,但这并不是那么明显(重新划分的额外工作将超过收益) ,但好处仍然存在)。

编辑:我也使用开放寻址,这也会增加对碰撞的敏感度,或许比它是二次幂的事实更多。

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

我过去编写的所有GetHashCode()实现,确实用作本网站答案的基础,比我经历的要糟糕得多。大部分时间它对于大部分用途都“足够好”,但我想要更好的东西。

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

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

现在,SpookyHash不是一个很好的快速记住代码片段。我的端口更是如此,因为我为了更好的速度而手动插入了大量的内容*。但这就是代码重用的目的。

然后我把  因为正如原始项目产生了如何生成更好的哈希代码的问题,因此该项目产生了如何产生更好的.NET memcpy的问题。

然后我回来了,并产生了很多重载,以便轻松地提供所有原生类型(除了 decimal†)成哈希码。

它的速度很快,鲍勃詹金斯应该获得大部分功劳,因为我移植的原始代码更快,特别是在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) 改善了一切。我本可以肯定的是,对于我来说,抖动会内联,但是分析显示不然。

decimal 虽然它来自C#,但它不是.NET的本机。它的问题在于它自己的问题 GetHashCode() 将精确度视为自身的重要性 Equals() 才不是。两者都是有效的选择,但不是那样的混合。在实现您自己的版本时,您需要选择一个或另一个,但我不知道您想要哪个。

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


19
2018-01-14 14:15



当将多个哈希值组合成一个时,我倾向于使用 long 中间结果的值,然后将最终结果下移到a int。这看起来是个好主意吗?我关心的是一个人使用例如hash =(hash * 31)+ nextField,然后匹配值对只会影响散列的高27位。让计算扩展到a long包装内容可以最大限度地减少这种危险。 - supercat
@supercat它取决于你最后的munging的分布。 SpookilySharp库通过将指针传递给blittable类型,或者直接传递它所处理的枚举之一,但是如果你还没有blittable,那么理想情况下(因为它不需要创建对象)可以确保分发是好的。数据或合适的枚举,然后调用 .Update() 根据上面的答案,多个值将成功。 - Jon Hanna
@JonHanna你愿意更准确地解决你遇到的有问题的行为吗?我正在尝试实现一个使实现值对象变得微不足道的库(ValueUtils)我喜欢一个测试集,证明在二次幂哈希表中哈希混淆不佳。 - Eamon Nerbonne
@EamonNerbonne我没有比“整体时间慢得多”更精确的东西。正如我在编辑中添加的那样,我使用开放寻址的事实可能比二次幂因素更重要。我打算在一个特定的项目上做一些测试用例,我会比较几种不同的方法,所以在那之后我可能会有更好的答案,尽管这不是一个高优先级(一个没有迫切需要的个人项目) ,所以当我到达它时我会接受它...) - Jon Hanna
@JonHanna:是的,我知道个人项目进度如何 - 祝你好运!在任何情况下,我都认为我没有说出最后的评论:我的意思是要求提出有问题的意见,而不一定是问题的细节。我喜欢将它用作测试集(或测试集的灵感)。无论如何 - 祝你的宠物项目好运:-)。 - Eamon Nerbonne


这个不错:

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

12
2017-10-07 10:51



@Magnus,你能解释一下吗? 为什么 这是一个很好的? - David Rutten
Keys如何确定? GetHashCode()不接受任何参数,因此需要使用需要以某种方式确定的两个键来调用此参数。对不起,没有进一步的解释,这看起来很聪明,但不是那么好。 - Michael Stum♦
当您使用object而不是泛型时,您将获得装箱和内存分配,这是GetHashCode中不需要的。因此,泛型是可行的方法。 - CodesInChaos
尾随班次/ xor步骤(h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15); 有一个代码:它们不依赖于任何输入,看起来非常多余。 - sehe
@Magnus是的,我会删除原来的评论。请注意,这可能不像其他解决方案那么快,但正如你所说的那样无关紧要。分布很棒,比大多数解决方案都要好,所以+1来自我! :) - nawfal


这是我的简单方法。我正在使用经典的构建器模式。它是类型安全(没有装箱/拆箱),也适用于.NET 2.0(没有扩展方法等)。

它使用如下:

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

这是真正的建设者类:

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

8
2018-03-22 12:15



你可以像在Mangus的回答中那样避免在gethashcode函数中创建对象。只需调用该死的静态哈希函数(谁关心启动哈希)。此外,你可以使用 AddItems<T>(params T[] items) 在helper类中经常使用的方法(比调用 AddItem(T) 每一次)。 - nawfal
你发现做了什么好处 this.result * Prime2 * item.GetHashCode() 经常使用的时候 this.result * Prime2 + item.GetHashCode()? - nawfal
这是一个错字,谢谢! - bitbonk
我不能用 AddItems<T>(params T[] items) 更常见的原因是 typeof(T1) != typeof(T2) 等等 - bitbonk
哦,是的,我错过了。 - nawfal


这是另一个流畅的实现 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);
    }
}

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


8
2018-01-20 23:41