在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。

对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?


当前回答

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

重型起吊应是Equals()方法的一部分;哈希应该是一个非常便宜的操作,以便能够对尽可能少的项目调用Equal()。

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

其他回答

这是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,因为添加泛型参数也会添加装箱操作。

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

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

截至https://github.com/dotnet/coreclr/pull/14863,有一种生成哈希代码的新方法非常简单!只要写

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

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

我在使用上面选择的实现时遇到了浮点和小数的问题。

此测试失败(浮点数;哈希值相同,即使我将2个值切换为负值):

        var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
        var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

但是这个测试通过了(int):

        var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
        var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

我改变了我的实现,不再对原始类型使用GetHashCode,它似乎工作得更好

    private static int InternalComputeHash(params object[] obj)
    {
        unchecked
        {
            var result = (int)SEED_VALUE_PRIME;
            for (uint i = 0; i < obj.Length; i++)
            {
                var currval = result;
                var nextval = DetermineNextValue(obj[i]);
                result = (result * MULTIPLIER_VALUE_PRIME) + nextval;

            }
            return result;
        }
    }



    private static int DetermineNextValue(object value)
    {
        unchecked
        {

                int hashCode;
                if (value is short
                    || value is int
                    || value is byte
                    || value is sbyte
                    || value is uint
                    || value is ushort
                    || value is ulong
                    || value is long
                    || value is float
                    || value is double
                    || value is decimal)
                {
                    return Convert.ToInt32(value);
                }
                else
                {
                    return value != null ? value.GetHashCode() : 0;
                }
        }
    }

我通常会使用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;
    }
}

正如评论中所指出的,你可能会发现最好选择一个大素数来乘。很显然486187639很好。。。虽然我见过的大多数小数字的例子都倾向于使用素数,但至少有一些类似的算法经常使用非素数。例如,在后面的FNV示例中,我使用的数字显然很好,但初始值不是质数。(不过乘法常数是质数。我不知道这有多重要。)

这比XORing散列码的常见做法要好,主要原因有两个。假设我们有一个具有两个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:您可以从不可变的字段计算哈希代码;或当可变对象包含在依赖其哈希代码的集合中时,可以确保该对象的哈希代码不会更改。

FNV文章的链接已断开,但这是互联网档案馆的一份副本:永恒的困惑-哈希的艺术