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

Question

EnumerableObject : IEnumerable<Foo>

包裹一个 List<Foo>

如果EnumerableObject a.SequenceEquals( EnumerableObject b),那么他们是平等的.

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

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

Answer 1

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

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

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

Answer 2

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

现在,假设您的意思是EnumerableObject 由于某种原因已经覆盖Equals(object)(并且希望因此也实现IEquatable<EnumerableObject>),那么这确实是必要的.您希望平衡速度与位分布.

一个好的起点是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位).

Answer 3

该.GetHashCode()方法通常只返回基于对象引用（指针地址）的哈希值。这是因为计算可枚举列表中每个项目的哈希码可能非常耗时。与其覆盖现有行为，我更喜欢使用扩展方法，并且仅在需要确定性地确定哈希码时才使用它：

public static class EnumerableExtensions
{
    public static int GetSequenceHashCode<TItem>(this IEnumerable<TItem> 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()));
    }
}