What is the best algorithm for overriding GetHashCode?

技术背景

在 C# 编程中，GetHashCode 方法用于返回对象的哈希代码，它在哈希表等数据结构中起着关键作用。一个好的 GetHashCode 实现可以提高哈希表的性能，减少哈希冲突的发生。然而，不同的场景和数据类型可能需要不同的哈希算法。因此，了解如何选择和实现最佳的 GetHashCode 算法是很重要的。

实现步骤

经典算法

参考 Josh Bloch 在《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;
    }
}

使用 ValueTuple

C# 7 及以上版本可以使用 ValueTuple 来生成哈希代码，它在栈上执行，避免了垃圾回收：

(PropA, PropB, PropC, PropD).GetHashCode();

使用 System.HashCode

在 .NET Standard 2.1 或更高版本中，可以使用 System.HashCode 结构体：

• HashCode.Combine：用于创建最多包含八个对象的哈希代码。

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

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

自定义哈希辅助类

可以创建自定义的哈希辅助类来实现哈希代码的生成：

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
        unchecked
        {
            return 31 * arg1.GetHashCode() + arg2.GetHashCode();
        }
    }

    // 其他重载方法...
}

核心代码

经典算法

public override int GetHashCode()
{
    unchecked
    {
        int hash = 17;
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

使用 System.HashCode

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

自定义哈希辅助类

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
        unchecked
        {
            return 31 * arg1.GetHashCode() + arg2.GetHashCode();
        }
    }
}

最佳实践

• 性能优先：选择简单的算法，避免额外的内存分配和复杂的计算。
• 确定性：确保算法是确定性的，即相同的输入始终产生相同的输出。
• 减少冲突：使用质数和合适的算法来减少哈希冲突的发生。
• 哈希均匀性：使哈希函数的输出尽可能均匀分布。
• 防止 DoS 攻击：在 .NET Core 中，每次重启应用程序时哈希代码会不同，这是为了防止 DoS 攻击。在 .NET Framework 中，可以通过配置文件启用此功能。

常见问题

哈希冲突

哈希冲突是指两个不同的对象产生相同的哈希代码。虽然哈希冲突是允许的，但应该尽量减少。可以通过选择合适的质数和算法来减少哈希冲突的发生。

哈希代码的稳定性

不要依赖 GetHashCode 在多个应用程序运行时保持稳定。许多 .NET 类型不保证其哈希代码在重启后保持不变，因此应仅将 GetHashCode 的值用于内存数据结构。

浮点数和小数的哈希问题

在使用浮点数和小数时，可能会遇到哈希代码相同的问题。可以通过不使用 GetHashCode 方法，而是直接转换为整数来解决。

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

大元组的哈希问题

在 .NET 中，元组包含超过 8 个元素时可能会产生相同的哈希代码。可以通过组合不同的方法来解决：

public override int GetHashCode()
{
    int hashCode = HashCode.Combine(obj_1, obj_2, obj_3, obj_4, obj_5, obj_6, obj_7, obj_8);
    hashCode = hashCode * 23 + HashCode.Combine(obj_9, obj_10);
    return hashCode;
}