随着.Net版本的不断迭代，文中涉及到的代码也会发生变动。但无论如何变动，算法的本质是不会变的，代码的思路也是基本保持稳定的，所以下文以.Net Core 2.1为例进行说明。后续的.Net版本中对应的代码希望看官们自行寻找，相信看完本文你会发现逻辑的本质依旧是一以贯之的。
从哈希算法着手
在C#的通用容器中，使用哈希算法的Dictionary与HashSet通过传入指定的Key返回我们所期望的数据。窥探其内部核心，可以看到其内部哈希算法的具体实现。
对我们今天要讨论的问题，我提取下列代码以供说明：
// 通过_keyCompare获取Key的哈希值
int hash = _keyCompare.GetHashCode(key);
// 通过计算后的哈希值获取对应key所在桶内的index，此处代码省略...
// 针对hash冲突，需要通过_keyCompare对已存在Key进行比较
while (link.hash != hash || !_keyCompare.Equals(items[wantId].key, key))
{
// 数据实际存放index计算，此处省略...
}
上述代码中，_keyCompare是一个实现了IEqualityComparer<T>接口的实例，其中T为Key的类型。
PS：我们的直觉，往往让我们认为比较仅仅通过一个==就可以实现，而在Dictionary这样的通用模板容器中，通过IEqualityComparer<T>接口实现比较运算，而并非直接调用==。
IEqualityComparer接口
之所以谈Dictionary的Key使用值类型的优化，核心就是在讨论这里面继承IEqualityComparer<T>接口的实例究竟是谁。
先来看看IEqualityComparer<T>接口的源代码：
public interface IEqualityComparer<in T>
{
bool Equals(T x, T y);
int GetHashCode(T obj);
}
IEqualityComparer<T>接口仅仅定义了比较函数与获取哈希值的函数，而这两样在默认容器的哈希算法中均有广泛使用到。
Dictionary中，是存在构造函数用以指定IEqualityComparer<T>的，但如果没有指定，则会调用EqualityComparer<T>.Default进行赋值。该方法源码就在EqualityComparer<T>.CreateComparer()方法之中，这里我们简要梳理这段代码的核心逻辑流程：
- 获取
T的RuntimeType，并在后续通过判断类型返回对应实例 - 判断为
byte类型返回ByteEqualityComparer实例 - 当
T继承IEquatable<T>接口，或T也为泛型且该泛型的指定类型继承继承IEquatable<>接口，则返回运行时创建的GenericEqualityComparer实例 - 当
T为枚举类型，则针对该枚举实际对应的数值类型，返回运行时创建的SByteEnumEqualityComparer、EnumEqualityComparer、ShortEnumEqualityComparer或LongEnumEqualityComparer实例 - 若以上条件都不满足，则返回
ObjectEqualityComparer实例
根据上述流程我们可以得知，当我们使用自定义值类型（struct）作为Dictionary的Key时，会因前置判断条件都不满足而使用ObjectEqualityComparer实例。
IEqualityComparer与GC的产生
ObjectEqualityComparer实例内部的Equals运算，调用的是C#中每一个object的Equals运算，所以当我们的类型是值类型时，就会因其转换为object而发生装箱的行为，从而产生GC。代码如下：
public override bool Equals(T x, T y)
{
return (object) x != null ? (object) y != null && x.Equals((object) y) : (object) y == null;
}
根据这段代码可以看出，无论是对参数x或y的判空，还是调用值类型原生的Equals方法，都是产生装箱的地方，这也就难怪此处会产生GC。
此外，在Dictionary中也用到了求取哈希值的运算，这一部分也会产生装箱过程：
public override int GetHashCode(T obj)
{
return (object) obj == null ? 0 : obj.GetHashCode();
}
代码中判空的装箱自不必说，即便我们单纯调用obj.GetHashCode()，若在结构体内没有重载GetHashCode，一样也会因装箱而产生额外GC。
曾经Enum的比较也是存在GC的
还记得一段时间之前，当我们在Dictionary中使用枚举作为Key时，一样会带来因装箱而导致的GC问题。不过最新的测试当中却是没有了这个问题。翻看.Net的代码，现在在获取默认IEqualityComparer实例时，已专门加入了枚举的判断，而内部则是针对枚举取值的优化，这当算做是.Net不断完善的小例证吧。
不过此处依旧需要提醒：稳妥起见，Enum类型的Key转为使用int等基础值类型或许更为稳妥，以避免因底层.Net版本不同而导致的在某些低版本上运行产生额外GC的风险。
写在最后：这就是所有内容了，我以此作为总结，希望看到这篇文章的你能有所收获。
网友评论