良好的GetHashCode()覆盖了尊重订单的Foo对象列表

EnumerableObject : IEnumerable

包装List

如果EnumerableObject a.SequenceEquals( EnumerableObject b) ,那么它们是相等的。

因此,必须实现GetHashCode 。 问题是XORing列表中的每个元素将返回具有所有且仅相同元素的任何列表的相同哈希码,而不管顺序如何。 就工作而言,这是好的,但会导致许多冲突,这将减慢检索速度等。

对于依赖于顺序的对象列表,什么是好的,快速的GetHashCode方法?

我的方式与通常组合哈希码的方式相同 – 加法和乘法:

 public override int GetHashCode() { unchecked { int hash = 19; foreach (var foo in foos) { hash = hash * 31 + foo.GetHashCode(); } return hash; } } 

(请注意,在任何描述的哈希表中使用此键后,不应向列表中添加任何内容,因为哈希值会更改。这也假设没有空条目 – 如果可能,则需要考虑到这一点。)

首先,仔细检查您是否需要哈希码。 您是否要将这些列表放入哈希映射结构(例如字典,哈希集等)? 如果没有,请忘掉它。

现在,假设您的意思是EnumerableObject已经覆盖了Equals(object) (并且因此有希望因此也实现了IEquatable ),那么这确实是必要的。 您希望平衡速度与位分布。

一个好的起点是mult + add或shift + xor,如:

 public override int GetHashCode() { int res = 0x2D2816FE; foreach(var item in this) { res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } 

(这假设您使用item.Equals()进行序列相等性比较,如果您使用的是IEqualityComparer,则需要调用其哈希码)。

从那里我们可以优化。

如果不允许使用null项,则删除null-check(注意,如果代码确实找到null,这将使代码抛出)。

如果非常大的列表很常见,我们需要减少检查的数量,同时尽量不要导致大量的冲突。 比较以下不同的实现:

 public override int GetHashCode() { int res = 0x2D2816FE; int max = Math.Min(Count, 16); for(int i = 0, i != max; ++i) { var item = this[i]; res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } public override int GetHashCode() { int res = 0x2D2816FE; int min = Math.Max(-1, Count - 16); for(int i = Count -1, i != min; --i) { var item = this[i]; res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } public override int GetHashCode() { int res = 0x2D2816FE; int step = Count / 16 + 1; for(int i = 0, i < Count; i += step) { var item = this[i]; res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } 

这些中的每一项都限制了所检查的项目总数,从而加快了执行速度,但却存在质量较差的哈希值。 哪个(如果有的话)最好取决于具有相同开头或相同结尾的集合是否更有可能。

更改上面的数字16会调整余额; 较小但速度较快但散列质量较高,散列冲突风险较低。

编辑:现在你可以使用我的SpookyHash v.2的实现 :

 public override int GetHashCode() { var hasher = new SpookyHash();//use methods with seeds if you need to prevent HashDos foreach(var item in this) hasher.Update(item.GetHashCode());//or relevant feeds of item, etc. return hasher.Final().GetHashCode(); } 

这将创建比mult + add或shift + xor更好的分布,同时也特别快(特别是在64位进程中,因为算法针对此进行了优化,尽管它也适用于32位)。

.GetHashCode()方法通常只返回基于对象引用(指针地址)的哈希。 这是因为计算可枚举列表中每个项目的哈希码可能非常耗时。 我不想覆盖现有的行为,而是使用扩展方法,只在确定性地确定哈希码的地方使用它:

 public static class EnumerableExtensions { public static int GetSequenceHashCode(this IEnumerable list) { if (list == null) return 0; const int seedValue = 0x2D2816FE; const int primeNumber = 397; return list.Aggregate(seedValue, (current, item) => (current * primeNumber) + (Equals(item, default(TItem)) ? 0 : item.GetHashCode())); } }