如何在C#中重写Hashtable的GetHashCode方法？键顺序不同需返回同哈希码

嘿，这个问题我太熟了！你现在用的异或写法确实有坑——虽然异或满足交换律（顺序不影响结果），但它的哈希冲突概率实在太高了，甚至可能出现完全不同的键集合算出相同哈希的情况，而且如果有重复的键值对，异或还会直接抵消掉，根本不靠谱。

要实现键顺序不同但内容相同时返回相同哈希码的需求，核心思路是：先把Hashtable里的键值对按固定规则排序，再用低冲突的方式组合哈希值。具体步骤如下：

1. 为什么原写法不行？ #

你的原代码：

Hashtable hkey; 
int i = 0; 
foreach (DictionaryEntry de in hkey) 
    i ^= de.GetHashCode(); 
return i;

• 异或的交换特性确实能保证顺序不影响结果，但哈希碰撞概率极高：比如(A^B^C)和(B^A^C)结果一样，但(A^B)和(C^D)也可能碰巧一样。
• 如果出现重复的键值对（比如同一个键值对出现两次），异或会直接抵消为0，导致完全不同的集合得到相同哈希。

2. 正确的实现方式 #

我们需要先对键值对排序，确保相同内容的集合排序后顺序一致，再用质数乘法的方式组合哈希（这是.NET中常用的低冲突哈希组合策略）：

public override int GetHashCode()
{
    // 处理Hashtable为null的情况
    if (hkey == null)
        return 0;

    // 提取所有键值对并按固定规则排序，确保顺序不影响最终哈希
    var sortedEntries = hkey.Cast<DictionaryEntry>()
                            // 先按键的哈希码排序，哈希相同则按字符串比较（避免哈希碰撞导致排序混乱）
                            .OrderBy(de => de.Key?.GetHashCode() ?? 0)
                            .ThenBy(de => de.Key?.ToString() ?? string.Empty)
                            // 再按值的哈希和字符串排序，确保键相同值不同的情况能区分开
                            .ThenBy(de => de.Value?.GetHashCode() ?? 0)
                            .ThenBy(de => de.Value?.ToString() ?? string.Empty)
                            .ToList();

    // 用质数初始化哈希值，减少冲突概率（17是常用的起始质数）
    int hash = 17;
    foreach (var entry in sortedEntries)
    {
        // 组合单个键值对的哈希：键哈希*31 + 值哈希（31是质数，计算高效且冲突少）
        int entryHash = (entry.Key?.GetHashCode() ?? 0) * 31 + (entry.Value?.GetHashCode() ?? 0);
        // 将当前键值对的哈希合并到总哈希中
        hash = hash * 31 + entryHash;
    }

    return hash;
}

3. 关键细节说明 #

• 排序规则：必须保证相同内容的键值对排序后顺序完全一致。如果你的键是自定义复杂对象，一定要确保该对象的GetHashCode和Equals方法正确实现，否则排序会出错。
• 质数的作用：用17作为初始值、31作为乘数，是因为质数的乘法能最大程度减少哈希碰撞，而且31可以用(hash << 5) - hash快速计算，性能很好。
• null处理：对键或值为null的情况做了兜底，避免空引用异常，同时保证null的哈希值固定为0。
• 可选优化：如果你的Hashtable是不可变的，可以提前缓存计算好的哈希值，避免每次调用GetHashCode都重新排序计算。

额外建议 #

如果你使用的是.NET Framework 2.0及以上版本，更推荐用Dictionary<TKey, TValue>代替Hashtable——泛型类型更安全，性能更好，而且处理键值对时不需要强制类型转换。

内容的提问来源于stack exchange，提问作者Amenis