C#中Type[]的完美/最小哈希实现及高效映射方案咨询

问题根源 #

默认的Dictionary<Type[], object>性能低下的核心原因是：.NET中数组的默认相等性比较是引用比较，Type[]的GetHashCode()返回的是基于对象引用的哈希值，而非数组内容的哈希。这意味着即使两个Type[]包含完全相同的类型序列，也会被Dictionary视为不同的键，导致无法命中缓存、重复存储条目，最终拖慢查找性能。

1. 自定义Type[]的相等比较器（修复Dictionary性能） #

如果想继续使用Dictionary，可以实现一个自定义的IEqualityComparer<Type[]>，基于数组内容计算哈希和判断相等性：

纯且最小的哈希实现 #

针对Type[]的哈希可以通过累加每个Type的哈希值实现，引入质数乘数减少碰撞概率：

public class TypeArrayEqualityComparer : IEqualityComparer<Type[]>
{
    public static readonly TypeArrayEqualityComparer Instance = new TypeArrayEqualityComparer();
    private const int PrimeMultiplier = 17;

    public bool Equals(Type[] x, Type[] y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (x == null || y == null) return false;
        if (x.Length != y.Length) return false;
        for (int i = 0; i < x.Length; i++)
        {
            if (!ReferenceEquals(x[i], y[i])) // Type是单例，引用比较足够高效
                return false;
        }
        return true;
    }

    public int GetHashCode(Type[] obj)
    {
        if (obj == null) return 0;
        int hash = 19;
        foreach (Type type in obj)
        {
            hash = hash * PrimeMultiplier + (type?.GetHashCode() ?? 0);
        }
        return hash;
    }
}

使用方式：

var dict = new Dictionary<Type[], object>(TypeArrayEqualityComparer.Instance);

这个实现轻量高效，仅基于数组内容计算哈希，适合热点路径使用。

2. 更高效的映射方案：将Type[]转换为唯一键对象 #

如果Dictionary的性能仍不满足需求，可将Type[]转换为不可变的内容型键对象，利用值类型或自定义不可变类型的特性优化：

方案A：固定长度Type[]用ValueTuple #

若你的Type[]长度固定，直接用ValueTuple<Type, Type, ...>作为键，比如长度为3时用ValueTuple<Type, Type, Type>。ValueTuple默认的相等性和哈希均基于内容，且作为值类型，避免了额外对象分配，性能极高。

方案B：自定义不可变键类型 #

针对任意长度的Type[]，封装一个不可变的TypeArrayKey类型，构造时一次性计算哈希值，避免重复计算：

public readonly struct TypeArrayKey : IEquatable<TypeArrayKey>
{
    private readonly Type[] _types;
    private readonly int _hashCode;

    public TypeArrayKey(Type[] types)
    {
        _types = types ?? Array.Empty<Type>();
        // 构造时一次性计算哈希
        int hash = 19;
        foreach (Type type in _types)
        {
            hash = hash * 17 + (type?.GetHashCode() ?? 0);
        }
        _hashCode = hash;
    }

    public bool Equals(TypeArrayKey other)
    {
        if (_hashCode != other._hashCode) return false; // 哈希快速排除不相等项
        if (_types.Length != other._types.Length) return false;
        for (int i = 0; i < _types.Length; i++)
        {
            if (!ReferenceEquals(_types[i], other._types[i]))
                return false;
        }
        return true;
    }

    public override bool Equals(object obj) => obj is TypeArrayKey other && Equals(other);
    public override int GetHashCode() => _hashCode;
}

使用示例：

var dict = new Dictionary<TypeArrayKey, object>();
dict[new TypeArrayKey(new[] { typeof(int), typeof(string) })] = someObject;

3. 完美哈希方案（条目较少场景） #

因你提到条目较少，可实现完美哈希进一步优化：

• 维护一个Dictionary<TypeArrayKey, int>映射键到唯一整数ID（从1开始递增）
• 用List<object>作为索引表，通过ID直接取值，实现O(1)的极致查找性能：

private int _nextId = 1;
private readonly Dictionary<TypeArrayKey, int> _keyToId = new Dictionary<TypeArrayKey, int>();
private readonly List<object> _valueLookup = new List<object>();

public object GetOrAdd(Type[] types, Func<object> valueFactory)
{
    var key = new TypeArrayKey(types);
    if (_keyToId.TryGetValue(key, out int id))
    {
        return _valueLookup[id - 1]; // ID从1开始，列表索引从0开始
    }
    var value = valueFactory();
    _keyToId[key] = _nextId;
    _valueLookup.Add(value);
    _nextId++;
    return value;
}

条目极少时（如少于10个），直接遍历列表比较内容的开销甚至比哈希查找更低。

总结 #

• 针对Type[]的纯内容哈希可通过累加每个Type的哈希值并乘以质数实现，轻量高效。
• 最快的映射方案取决于条目数量：
  • 条目极少：直接遍历列表比较内容。
  • 条目中等：使用自定义相等比较器的Dictionary或不可变键类型的Dictionary。
  • 极致性能需求：将Type[]映射为整数ID，用列表作为索引表。

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