11月6日总结

无论是实际的项目中，还是在我们学习的过程中，都会重点的应用到Dictionary<TKey, TValue>这个存储类型。每次对Dictionary<TKey, TValue>的添加都包含一个值和与其关联的键， 使用键检索值的速度非常快，接近 O (1) ，因为 Dictionary<TKey, TValue> 类是作为哈希表实现的。首先我们来从一个简单的例子开始，以下是对一个字典的创建和赋值。

1 Dictionary<int, string> openWith = new Dictionary<int, string>();
2 openWith.Add(1000, "key值为1000");
3 openWith.Add(1001, "key值为1001");

相信绝大部分的开发人员对以上示例不是会陌生，那么Dictionary<TKey, TValue>的实现原理是什么样的呢？在字典的初始化、赋值、取值、扩容的实现原理是什么样的呢？很多时候我们需要知其然，更需要知其所以然。接下来我们将从其内存的存储的数据结构、取值的逻辑、扩容原则等几个视角进行仔细的了解 。那我们就沿着CoreFX中Dictionary<TKey, TValue>的实现源码来做一个简单的学习和思考，这里需要特别注意一下：
　　学习和分析源码时，不要先入为主，要按照框架和源码的逻辑进行解读，记录下不懂的地方重点分析，最后将整个逻辑串联起来。如果我们一开始就设定了逻辑为A-B-C，但是读到一个阶段的时候发现变成了C-B-A，这个时候就无法再继续进行下去，因为具体的实现过程中会有很多因素造成局部调整，我们可以在解读完毕之后，将实际的逻辑与个人前期理解的逻辑的差异进行比较，找出原因并做分析。
一、Dictionary<TKey, TValue>初始化
  Dictionary<TKey, TValue>的构造方法较多，我们来看一下其中的基础实现方法，首先看一下对应的源码（源码中不必要的部分已经做了部分删减，保留了核心的实现逻辑）。

1 public Dictionary(int capacity, IEqualityComparer? comparer)
2 {
3 if (capacity > 0) Initialize(capacity);
4 if (!typeof(TKey).IsValueType)
5 {
6 _comparer = comparer ?? EqualityComparer.Default;
7 if (typeof(TKey) == typeof(string) && NonRandomizedStringEqualityComparer.GetStringComparer(_comparer!) is IEqualityComparer stringComparer)
9 {
10 _comparer = (IEqualityComparer)stringComparer;
11 }
12 }
13 else if (comparer is not null && comparer != EqualityComparer.Default)
14 {
15 _comparer = comparer;
16 }
17 }

以上的实现逻辑重点包含了两个部分，第一部分：对Dictionary<TKey, TValue>的容量初始化；第二部分是Dictionary<TKey, TValue>的IEqualityComparer? comparer的初始化，本文重点是对Dictionary<TKey, TValue>的存储结构进行分析，涉及到比较器的实现逻辑，将放在后续的章节中进行重点介绍。
  我们接下来看一下Initialize()的实现逻辑进行一个简单的介绍，首先一起来看一下对应的源码实现(非必要部分已做删减，方便大家可以直观的查看)。

1 private int Initialize(int capacity)
2 {
3 int size = HashHelpers.GetPrime(capacity);
4 int[] buckets = new int[size];
5 Entry[] entries = new Entry[size];
6 _freeList = -1;
7 #if TARGET_64BIT
8 _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)size);
9 #endif
10 _buckets = buckets;
11 _entries = entries;
12 return size;