重写System.Object.GetHashCode的最佳算法是什么？

我在Helper库中有一个Hashing类,我将它用于此目的.

/// 
 
/// 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
/// 
/// array of objects, parameters combination that you need
/// to get a unique hash code for them
/// Hash code
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(this int hash, T obj)
    {
        var h = EqualityComparer.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 obj)
    {
        var h = EqualityComparer.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.Defaultgetter现在是一个JIT内在 - 在这篇博客文章中,Stephen Toub提到了pull请求.

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

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

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

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

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

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

好吧,令人不安的是string.GetHashCode(),.NET(或此处的研究)中的实现可以通过这种方式进行多少改进(由于冲突更少,测试运行速度提高了大约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从.NET的角度来看,† 不是原生的,尽管它来自C#.它的问题在于它自己GetHashCode()将精度视为重要而其本身Equals()则不然.两者都是有效的选择,但不是那样的混合.在实现您自己的版本时,您需要选择一个或另一个,但我不知道您想要哪个.

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

这个不错:

/// 

/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// 
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;
        }
    }

    /// 

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

    /// 

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

    /// 

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

    /// 

    /// Returns a hash code for the specified objects
    /// 
    /// The first object.
    /// The second object.
    /// 
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// 
    public static int GetHashCode(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);
    }
}

如果使用的是.NET Core 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 Made Easy ”，以获取更多详细信息和评论。

使用范例

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

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

实作

public struct HashCode : IEquatable
{
    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 item) => new HashCode(GetHashCode(item));

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

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

    public HashCode AndEach(IEnumerable 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 item) => item?.GetHashCode() ?? 0;

    private static int GetHashCode(IEnumerable 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;
    }
}

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

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

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

这是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(this int hash, T value)
        where T : struct
    {
        unchecked { return hash * 23 + value.GetHashCode(); }
    }
}

用法:

public class MyType
{
    public string Name { get; set; }

    public string Description { get; set; }

    public int Value { get; set; }

    public IEnumerable Children { get; set; }

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

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

这是我简单化的方法.我正在使用经典的构建器模式.它是类型安全(没有装箱/拆箱),也适用于.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 item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

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

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

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

    public void AddItems(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(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}

ReSharper用户可以使用生成GetHashCode，等于等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;
    }
}