2.3 Dictionary底层源码剖析
前面剖析了List的源码，明白了List是基于数组构建而成的，增加、减少、插入的操作都在数组中进行。我们还分析了大部分List的接口，包括Add、Remove、Insert、IndexOf、Find、Sort、ToArray等，并得出了一个结论：List是一个兼容性比较好的组件，但List在效率方面没有做优化，线程也不安全，需要加锁机制来保证线程的安全性。
下面对另一个常用Dictionary组件进行底层源码的分析，看看常用的字典容器是如何构造的，它的优缺点如何。
1. Dictionary底层代码剖析
我们知道，Dictionary字典型数据结构是以关键字Key值和Value值进行一一映射的。Key的类型并没有做任何的限制，可以是整数，也可以是字符串，甚至可以是实例对象。关键字Key是如何映射到实例的呢？
其实没有什么神秘的，这种映射关系可以用一个Hash函数来建立，Dictionary也确实是这样做的。这个Hash函数并非神秘，我们可以简单地认为它只是做了一个模（Mod）的操作，Dictionary会针对每个Key加入容器的元素都进行一次Hash（哈希）运算操作，从而找到自己的位置。
Hash函数可以有很多种算法，最简单的可以认为是余操作，比如当Key为整数93时，其源码如下：
hash_key = Key % 30 = 3
对于实例对象和字符串来说，它们没有直接的数字作为Hash标准，因此它们需要通过内存地址计算一个Hash值，计算这个内存对象的函数就叫HashCode，它是基于内存地址计算得到的结果，编写类时可重载HashCode()来设计一个我们自己的Hash值计算方式，也可以使用原始的计算方式。实际算法没有我举的例子这么简单，我们将在下面的源码剖析中详细讲解。
对于不同的关键字Key，在Hash计算时可能得到同一Hash地址，即当key1 !=key2不相等，但HashCode(key1)与HashCode(fey2)相等时，这种现象称为Hash冲突，一般情况下，冲突只能尽可能地少，而不能完全避免。因为Hash函数是从关键字范围到索引范围的映射，通常关键字范围要远大于索引范围，它的元素包括多个可能的关键字。既然如此，如何处理冲突，则是构造Hash表不可不解决的一个问题。
在处理Hash冲突的方法中，通常有开放定址法、再Hash法、链地址法、建立一个公共溢出区等。Dictionary使用的解决冲突方法是拉链法，又称链地址法。
拉链法的原理如下：
将所有关键字为同义词的节点链接在同一个单链表中。若选定的Hash表长度为n，则可将Hash表定义为一个由n个头指针组成的指针数组T[0...n-1]。凡是Hash地址为i的节点，均插入以T[i]为头指针的单链表中。T中各分量的初值均为空指针。
在Hash表上进行查找的过程与Hash表构建的过程基本一致。
给定Key值，根据造表时设定的Hash函数求得Hash地址，若表中此位置没有记录，则表示查找不成功；否则比较关键字，若给定值相等，则表示查找成功；否则，根据处理冲突的方法寻找“下一地址”，直到Hash表中某个位置为空或者表中所填记录的关键字等于给定值为止。
我们来看看更形象的结构图，如图2-1所示。
图2-1 Hash冲突拉链法
在图2-1的Hash冲突拉链法结构中，主要的宿主为数组指针，每个数组元素里存放着指向下一个节点的指针，如果没有元素在单元上，则为空指针。当多个元素都指向同一个单元格时，则以链表的形式依次存放并列的元素。
2. Dictionary的接口
Dictionary究竟是如何实现的呢？我们来剖析一下源码。
首先看看源码中Dictionary的变量定义部分，如下：
public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary,
IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback
{
private struct Entry {
public int hashCode; // 低31位为Hash值，如果未使用则为-1
public int next; // 下一个实例索引，如果是最后一个则为-1
public TKey key; // 实例的键值
public TValue value; // 实例的值
}
private int[] buckets;
private Entry[] entries;
private int count;
private int version;
private int freeList;
private int freeCount;
private IEqualityComparer<TKey>comparer;
private KeyCollection keys;
private ValueCollection values;
private Object _syncRoot;
}
从继承的类和接口看，Dictionary主要继承了IDictionary接口和ISerializable接口。IDictionary和ISerializable在使用过程中，主要的接口为Add、Remove、ContainsKey、Clear、TryGetValue、Keys、Values，以及以[]数组符号形式作为返回值的接口。也包括常用库Collection中的接口Count、Contains等。
从Dictionary的定义变量中可以看出，Dictionary是以数组为底层数据结构的类。当实例化new Dictionary()后，内部的数组是0个数组的状态。与List组件一样，Dictionary也是需要扩容的，会随着元素数量的增加而不断扩容。具体来看看接口源码剖析。
下面将围绕上述接口解析Dictionary底层运作机制。
了解Add接口是最直接了解底层数据结构如何运作的途径。我们来看Add接口的实现，其源代码如下：
public void Add(TKey key, TValue value)
{
Insert(key, value, true);
}
private void Initialize(int capacity)
{
int size = HashHelpers.GetPrime(capacity);
buckets = new int[size];
for (int i = 0; i<buckets.Length; i++) buckets[i] = -1;
entries = new Entry[size];
freeList = -1;
}
private void Insert(TKey key, TValue value, bool add)
{
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets == null) Initialize(0);
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int targetBucket = hashCode % buckets.Length;
#if FEATURE_RANDOMIZED_STRING_HASHING
int collisionCount = 0;
#endif
for (int i = buckets[targetBucket]; i>= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
if (add) {
ThrowHelper.ThrowArgumentException(
ExceptionResource.Argument_AddingDuplicate);
}
entries[i].value = value;
version++;
return;
}
#if FEATURE_RANDOMIZED_STRING_HASHING
collisionCount++;
#endif
}
int index;
if (freeCount>0) {
index = freeList;
freeList = entries[index].next;
freeCount--;
}
else {
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;
version++;
#if FEATURE_RANDOMIZED_STRING_HASHING
#if FEATURE_CORECLR
// 如果我们触碰到阈值，则需要切换到使用随机字符串Hash的比较器上
// 在这种情况下，将是EqualityComparer<string>.Default
// 注意，默认情况下，coreclr上的随机字符串Hash是打开的，所以EqualityComparer<string>.
Default将使用随机字符串Hash
if (collisionCount>HashHelpers.HashCollisionThreshold && comparer ==
NonRandomizedStringEqualityComparer.Default)
{
comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
Resize(entries.Length, true);
}
#else
if(collisionCount>HashHelpers.HashCollisionThreshold &&
HashHelpers.IsWellKnownEqualityComparer(comparer))
{
comparer = (IEqualityComparer<TKey>)
HashHelpers.GetRandomizedEqualityComparer(comparer);
Resize(entries.Length, true);
}
#endif // FEATURE_CORECLR
#endif
}
以上展示的代码稍稍多了点，我们摘出其中的要点，通过要点来了解重点，再通过重点了解全局。
其实Add接口就是Insert()的代理，它只有Insert()这一个函数调用，那么Insert()函数做了什么呢？
在加入数据前，首先需要对数据结构进行构造，其代码如下：
if (buckets == null) Initialize(0);
在构建Dictionary时，如果没有指定任何数量，buckets就是一个空的数组，所以需要对buckets进行初始化，即Initialize(0)，说明构建的数量级最少。
不过奥妙就在Initialize()函数里，如果传入的参数不是0，而是5、10、25或其他更大的数，那么构造多大的数据结构才合适呢？
在Initialize()函数中给了我们答案，看下面代码：
int size = HashHelpers.GetPrime(capacity);
它们有专门的方法来计算到底该使用多大的数组，从GetPrime字面意思可以猜测到应该跟质数有关，我们找出源码HashHelpers，primes数值的定义如下：
public static readonly int[] primes = {
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239,
293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013,
8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523,
108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827,
807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471,
7199369};
public static int GetPrime(int min)
{
if (min<0)
throw new ArgumentException(
Environment.GetResourceString("Arg_HTCapacityOverflow"));
Contract.EndContractBlock();
for (int i = 0; i<primes.Length; i++)
{
int prime = primes[i];
if (prime>= min) return prime;
}
// 如果在我们的预定义表之外，则做硬计算
for (int i = (min | 1); i<Int32.MaxValue;i+=2)
{
if (IsPrime(i) && ((i - 1) % Hashtable.HashPrime != 0))
return i;
}
return min;
}
// 返回要增长到的Hash表的大小
public static int ExpandPrime(int oldSize)
{
int newSize = 2 * oldSize;
// 在遇到容量溢出之前，允许Hash表增长到最大可能的大小（约2G个元素）
// 请注意，即使（item.Length）由于（uint）强制转换而溢出，此检查仍然有效
if ((uint)newSize>MaxPrimeArrayLength && MaxPrimeArrayLength>oldSize)
{
Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength),
"Invalid MaxPrimeArrayLength");
return MaxPrimeArrayLength;
}
return GetPrime(newSize);
}
上述代码为HashHelpers部分的源码，其中GetPrime()会返回一个需要的size最小的质数值，从GetPrime()函数的代码中可以知道这个size是数组primes里的值，与当前需要的数量大小有关，当需要的数量小于primes某个单元格的数字时返回该数字，而ExpandPrime()则更加简单粗暴，直接返回原来size的2倍作为扩展数量。
从Prime的定义看得出，首次定义size为3，每次扩大2倍，也就是3→7→17→37→…底层数据结构的大小是按照这个数值顺序来扩展的，而且每次都是质数。如果你在创建Dictionary时先定义了它的初始大小，指定的初始大小也会被GetPrime()计算为应该分配的质数数量，最终得到应该分配的数组大小。这与List组件的分配方式一模一样。
我们继续看初始化后的内容，对关键字Key做Hash操作，从而获得地址索引，其源码如下：
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; int targetBucket = hashCode % buckets.Length;
当调用函数获得Hash值后，还需要对Hash地址执行余操作，以确保索引地址落在Dictionary数组长度范围内，而不会溢出。
接着对指定数组单元格内的链表元素执行遍历操作，找出空出来的位置将值填入，其源代码如下：
for (int i = buckets[targetBucket]; i>= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
if (add) {
ThrowHelper.ThrowArgumentException(
ExceptionResource.Argument_AddingDuplicate);
}
entries[i].value = value;
version++;
return;
}
#if FEATURE_RANDOMIZED_STRING_HASHING
collisionCount++;
#endif
}
这一步就是前面所说的拉链法的链表推入操作。在获得Hash值的数组索引后，我们知道了应该将数据存放在哪个数组位置上，如果该位置已经有元素被推入，则需要将其推入链表的尾部。从for循环开始，检查是否到达链表的末尾，最后将数据放入尾部，并结束函数。
如果数组的空间不够怎么办？源码中体现了这一点：
int index;
if (freeCount>0) {
index = freeList;
freeList = entries[index].next;
freeCount--;
}
else {
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;
当被用来记录剩余单元格数量的变量freeCount等于0时，则进行扩容，扩容后的大小就是前面提到的调用ExpandPrime后的数量，即通常情况下为原来的2倍，再根据这个空间大小数字调用GetPrime()来得到真正的新数组的大小。
了解了Add接口，再来看看Remove部分。
删除的过程和插入的过程类似，因为要查找Key元素所在的位置，所以再次将Key值执行Hash操作也是难免的，然后类似沿着拉链法的模式寻找与关键字匹配的元素。
Remove()使用关键字删除元素的接口源码如下：
public bool Remove(TKey key)
{
if(key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int bucket = hashCode % buckets.Length;
int last = -1;
for (int i = buckets[bucket]; i>= 0; last = i, i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].
key, key)) {
if (last<0) {
buckets[bucket] = entries[i].next;
}
else {
entries[last].next = entries[i].next;
}
entries[i].hashCode = -1;
entries[i].next = freeList;
entries[i].key = default(TKey);
entries[i].value = default(TValue);
freeList = i;
freeCount++;
version++;
return true;
}
}
}
return false;
}
我们注意到，Remove接口相对于Add接口简单得多，同样使用Hash函数comparer.GetHashCode()获得Hash值，再执行余操作，确定索引值落在数组范围内，从Hash索引地址开始查找链表中的值，查找冲突链表中元素的Key值是否与需要移除的Key值相同，若相同，则进行移除操作并退出。
注意源码中Remove()函数的移除操作并没有对内存进行删减，而只是将其单元格置空，这是为了减少内存的频繁操作。
继续剖析另一个重要的接口ContainsKey，即检测是否包含关键字的接口。其源码如下：
public bool ContainsKey(TKey key)
{
return FindEntry(key)>= 0;
}
private int FindEntry(TKey key)
{
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
for (int i = buckets[hashCode % buckets.Length]; i>= 0; i =
entries[i].next) {
if (entries[i].hashCode ==
hashCode && comparer.Equals(entries[i].key,key)) return i;
}
}
return -1;
}
从以上源码可以看到，ContainsKey()函数的运行是一个查找Key位置的过程。它调用了FindEntry()函数，FindEntry()查找Key值位置的方法与前面提到的相同。从使用Key值得到的Hash值地址开始查找，查看所有冲突链表中是否有与Key值相同的值，若找到，即刻返回该索引地址。
有了对几个核心接口理解的基础，理解其他接口相对就简单多了，我们可快速地学习一下。
TryGetValue接口是尝试获取值的接口，其源码如下：
public bool TryGetValue(TKey key, out TValue value)
{
int i = FindEntry(key);
if (i>= 0) {
value = entries[i].value;
return true;
}
value = default(TValue);
return false;
}
与ContainsKey()函数类似，它调用的也是FindEntry()函数的接口，以此来获取Key对应的Value值，并对[]操作符重定义，其源码如下：
public TValue this[TKey key] {
get {
int i = FindEntry(key);
if (i>= 0) return entries[i].value;
ThrowHelper.ThrowKeyNotFoundException();
return default(TValue);
}
set {
Insert(key, value, false);
}
}
在重新定义[]符号的代码中，获取元素时同样也会使用FindEntry()函数，而Set设置元素时，则会使用与Add调用相同的Insert()函数，它们都是同一套方法，即Hash拉链冲突解决方案。
从源码剖析来看，Hash冲突的拉链法贯穿了整个底层数据结构。因此Hash函数是关键，Hash函数的好坏直接决定了效率的高低。
既然这么重要，我们来看看Hash函数的创建过程，函数创建的源码如下：
private static EqualityComparer<T>CreateComparer()
{
Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null);
RuntimeType t = (RuntimeType)typeof(T);
// 出于性能原因专门用字节类型
if (t == typeof(byte)) {
return (EqualityComparer<T>)(object)(new ByteEqualityComparer());
}
// 如果T implements IEquatable<T>返回一个GenericEqualityComparer<T>
if (typeof(IEquatable<T>).IsAssignableFrom(t)) {
return (EqualityComparer<T>)
RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter(
(RuntimeType)typeof(GenericEqualityComparer<int>), t);
}
// 如果T是一个Nullable<U>从U implements IEquatable<U>返回的NullableEquality
Comparer<U>
if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) {
return (EqualityComparer<T>)
RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
RuntimeType)typeof(NullableEqualityComparer<int>), u);
}
}
// 看这个METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST和METHOD__JIT_HELPERS__UNSAFE_
ENUM_CAST_LONG在getILIntrinsicImplementation中的例子
if (t.IsEnum) {
TypeCode underlyingTypeCode = Type.GetTypeCode(
Enum.GetUnderlyingType(t));
// 根据枚举类型，我们需要对比较器进行特殊区分，以免装箱
// 注意，我们要对Short和SByte使用不同的比较器，因为对于这些类型，
// 我们需要确保在实际的基础类型上调用GetHashCode，其中，GetHashCode的实现比其他类型更复杂
switch (underlyingTypeCode) {
case TypeCode.Int16:
return (EqualityComparer<T>)
RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
RuntimeType)typeof(ShortEnumEqualityComparer<short>), t);
case TypeCode.SByte:
return (EqualityComparer<T>)
RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), t);
case TypeCode.Int32:
case TypeCode.UInt32:
case TypeCode.Byte:
case TypeCode.UInt16:
return (EqualityComparer<T>)
RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
RuntimeType)typeof(EnumEqualityComparer<int>), t);
case TypeCode.Int64:
case TypeCode.UInt64:
return (EqualityComparer<T>)
RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
RuntimeType)typeof(LongEnumEqualityComparer<long>), t);
}
}
// 否则，返回一个ObjectEqualityComparer<T>
return new ObjectEqualityComparer<T>();
}
我们看到，以上源码对数字、byte、有“比较”接口（IEquatable<T>）和没有“比较”接口（IEquatable）这四种方式进行了区分。前面说的实例对象的Hash值是通过HashCode()函数来计算获得的，它以内存地址为标准计算得到一个Hash值，我们也可以重写这个方法来计算自己的Hash值。
对于数字和byte类，比较容易对比，所以它们是一类。而有“比较”接口（IEquatable<T>）的实体，则直接使用GenericEqualityComparer<T>来获得Hash函数。最后那些没有“比较”接口（IEquatable）的实体，如果继承了Nullable<U>接口，则使用一个叫NullableEquality-Comparer()的比较函数来代替。如果什么都不是，就只能使用ObjectEqualityComparer<T>默认的对象比较方式来做比较了。
在C#里，所有类都继承了Object类，因此，即使没有特别的重写Equals()函数，都会使用Object类的Equals()函数，其源码如下：
public virtual bool Equals(Object obj)
{
return RuntimeHelpers.Equals(this, obj);
}
[System.Security.SecuritySafeCritical]
[ResourceExposure(ResourceScope.None)]
[MethodImplAttribute(MethodImplOptions.InternalCall)]
public new static extern bool Equals(Object o1, Object o2);
这个Equals()函数对两个对象进行比较，是以内存地址为基准的。
Dictionary同List一样，并不是线程安全的组件，官方源码中进行了这样的解释：
** Hashtable has multiple reader/single writer (MR/SW) thread safety built into ** certain methods and properties, whereas Dictionary doesn't. If you're ** converting framework code that formerly used Hashtable to Dictionary, it's ** important to consider whether callers may have taken a dependence on MR/SW ** thread safety. If a reader writer lock is available, then that may be used ** with a Dictionary to get the same thread safety guarantee.
Hashtable在多线程读/写中是线程安全的，而Dictionary不是。如果要在多个线程中共享Dictionary的读/写操作，就要自己写lock，以保证线程安全。
到这里我们已经全面了解了Dictionary的内部构造和运作机制。它是由数组构成，并且由Hash函数完成地址构建，由拉链法冲突解决方式来解决冲突的。
从效率上看，同List一样，最好在实例化对象，即新建时，确定大致数量，这样会使得内存分配次数减少，另外，使用数值方式作为键值比使用类实例的方式更高效，因为类对象实例的Hash值通常都由内存地址再计算得到。
从内存操作上看，其大小以3→7→17→37→…的速度（每次增加2倍多）增长，删除时，并不缩减内存。
如果想在多线程中共享Dictionary，则需要我们自己进行lock操作。
Dictionary源码网址为https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs。