hashcode - 重写System.Object.GetHashCode什么是最好的算法?

  显示原文与译文双语对照的内容

在. NET System.Object.GetHashCode 方法中使用了很多地方,整个. NET 基类库。 尤其是在快速查找集合中的项目或者确定相等性时。 是否有标准的算法/最佳实践来实现我的自定义类的GetHashCode 重写,这样我就不会降低性能?

时间:

我通常和类似的实现给出josh布洛赫的 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是好的。尽管大多数例子我见过少量倾向于使用质数,至少有类似算法non-prime数字经常使用的地方。 举例来说,在not-quite-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,而不是添加为组合运算。 看起来像下面的代码,但正常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;
 }
}

编辑:注意,要注意的一点是,在将 equality-sensitive ( 因此 hashcode-sensitive ) 状态添加到一个依赖于哈希代码的集合后,应该避免更改。

按照文档 。xml:

可以重写不变量引用类型的GetHashCode 。 通常,对于可变引用类型,只在以下情况下重写 GetHashCode:

  • 可以从不可变的字段计算哈希代码;或者
  • 你可以确保可变对象的哈希代码在对象包含在依赖它的哈希代码的集合中时不会更改。

微软已经提供了一个很好的通用哈希生成器: 只需将你的属性/字段值复制到匿名类型并将它的散列:


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

这对于任何数字或者属性都适用。 它不使用装箱或者额外的资源。 它只使用已经在框架中实现的匿名类型的算法。

这是我的hashcode helper 。
它的优点是使用泛型类型参数,因此不会导致装箱:


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 库中有一个哈希类,用于这里目的。


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

//I have added the unchecked keyword to make sure 
//not get an overflow exception.
//It can be enhanced later by catching the OverflowException.

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

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

在大多数情况下,Equals() 比较多个字段,如果你的GetHash() 散列在一个字段上或者在多个域上。 你只需确保计算哈希真的是廉价的( 请没有分配) 和快速( 没有重计算当然没有数据库连接),并提供一个良好的分布。

繁重的提升应该是 Equals() 方法的一部分;哈希应该是一个非常廉价的操作,以尽可能少的项目调用 Equals() 。

和最后一个提示:不依靠 GetHashCode() 被多个应用运行稳定。 许多. NET 类型不保证它们的哈希代码在重新启动后保持不变,因此你应该只在内存数据结构中使用 GetHashCode()的值。

这是我的helper 类,它使用了 Jon 。Skeet的实现。


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

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

使用方法:


public override int GetHashCode()
{
 return HashCode.Start
. Hash(field1)
. Hash(field2)
. Hash(field3);
}

磅编辑( 四月 1 st 2014 )

我认为我不喜欢将一个扩展方法写入类型 Int32,所以我编写了一个结构来包装计算的哈希值。


public struct HashCode
{
 private readonly int hashCode;

 public HashCode(int hashCode)
 {
 this.hashCode = hashCode;
 }

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

 public static implicit operator int(HashCode hashCode)
 {
 return hashCode.GetHashCode();
 }

 public HashCode Hash<T>(T obj)
 {
 var c = EqualityComparer<T>.Default;
 var h = c.Equals(obj, default(T))? 0 : obj.GetHashCode();
 unchecked { h += this.hashCode * 31; }
 return new HashCode(h);
 }

 public override int GetHashCode()
 {
 return this.hashCode;
 }
}

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


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 导致 obj ( 如果是结构)的装箱,使用 obj.Equals(null) 可能导致 NullReferenceException的抛出,所以我使用了默认的比较器。 有关比较器默认性能的更多信息,请参见这里答案

这是个不错的选择:


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

这是我的简单方法。 我正在使用经典的生成器模式。 它是类型安全( 不装箱/取消装箱) 也与. NET compatbile 2.0 ( 没有扩展方法 等等 ) 。

它是这样使用的:


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

下面是acutal生成器类:


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

直到最近我的答案非常接近jon水瓢。 但是,我最近开始了一个使用power-of-two哈希表的项目,这是哈希表,其中内部表的大小为 8,16,32,等等,有一个好的理由,但power-of-two大小也有一些优势。

而且它几乎 sucked 。 在进行了一些实验和研究之后,我开始了re-hashing的哈希分析:


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

然后我的power-of-two哈希表不再消耗。

但这让我感到不安,因为上面的工作不应该工作。 或者更确切地说,除非原始 GetHashCode() 以非常特殊的方式较差,否则它不应该工作。

Re-mixing一个hashcode不能改进一个伟大的哈希,因为唯一可能的效果是我们引入了一些更多的冲突。

Re-mixing哈希代码不能改进可怕的哈希代码,因为唯一可能的效果是将 比如 53上的大量冲突更改为大量值 183487291.

Re-mixing一个哈希代码只能改进一个哈希代码,它至少在整个范围内避免绝对冲突( 2 32 可能的值),但在哈希表中实际使用时避免了冲突。 虽然power-of-two表的简单模使这更明显,它也有负面影响,更常见prime-number表,只是( 再散列中的额外工作会超过好处,但好处仍然存在) 并不明显。

编辑:我也使用了 open-addressing,它也会增加对碰撞的敏感度,可能比power-of-two的更多。

,好吧,这是令人不安的多少 string.GetHashCode() 可以改善这种方式( 在大约 20次的测试中,由于更少的碰撞而运行的顺序) 更令人不安的多少自己的哈希码可以改善( 远不止如此) 。

GetHashCode() 实现我将编码的过去,甚至用作答案在这个网站的基础上,身子比我会更糟。 大部分时候它是"足够好"的,但我想要更好的东西。

所以我把这个项目到一边( 那是个宠物项目), 开始看如何产生一个好的,很快在. NET well-distributed哈希代码。

最后我决定将 SpookyHash 。to移植到. NET 。 上面的代码确实是使用 SpookyHash fast-path版本产生 32位 32位 输入输出。

现在,SpookyHash不是一个很好的记忆代码 Fragment 。 我是港更少因为我hand-inlined很多speed*更好。 但这就是代码重用的目的。

然后我把项目向一边,因为正如最初的项目已经产生的问题如何产生一个更好的散列码,以便项目产生的问题如何产生一个. NET memcpy更好。

完整的代码可以在 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();
}

It also takes seed values, so if you need to deal with untrusted input and want to protect against Hash DOS attacks you can set a seed -based on uptime or similar, and make results unpredictable by attackers:


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

*A的一大惊喜是hand-inlining一个返回的旋转方法 (x <<n) | (x>> -n) 改进的东西。我将确保抖动会内联,对我来说,但分析显示。

问题是,它自己的GetHashCode() 在它的自身的Equals() 不存在的情况下将精度视为重要。 两者都是有效的选择,但不能像这样混合。 在实现你自己的版本时,你需要选择一个或者另一个,但是我不知道你想要哪一个。

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


//Unique ID from database
private int _id;

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

...