白话算法(6.5) 泛型 Dictionary 源码剖析（下）
学英语最苦恼的事情是每个单词都认识，连在一起却不知道是什么意思；读源代码最苦恼的事情是每一行代码都能看得懂，却不知道它们是如何一起完成工作的。这里的关键都是对整体的把握。人脑的特点是有很强的逻辑思维、抽象思维能力和丰富的想象力——以及很差的记忆力，无法同时记住并关注大量的对象，所以在阅读成千上万行代码的时候就难免看了后面忘了前面。正因为如此，我们在进行一项复杂的工作的时候，就必须扬长避短，把复杂的事物划分成不同级别的抽象层次。
对于泛型 Dictionary 的源代码，可以分成“原理和概念模型——实现模型——实现细节”这3个不同的抽象层次。
Dictionary 的原理和概念模型
Dictionary 是使用html" target=_blank>除法散列法计算存储地址，在存储地址重复时使用链接法处理碰撞。之所以使用数组+链表的搭配是为了服务于“查找、添加、删除操作都是 O(1) 复杂度”的目标。关于除法散列法和链接法在 6.1 有详细的描述，不再赘述。下图是一个实例：
Dictionary 的实现模型
上面的概念模型虽然简单明了，但是有点浪费空间，因为不管有没有碰撞，buckets 的每个槽都指向一个链表，相当多的链表里其实都只有一个项，比较浪费。另外，链表是一个一个地添加新节点而不是一次申请一大块空间，无论是申请内存还是垃圾回收效率都不高。
所以 Dictionary 的实现使用了一种更为高效的做法：将每一项添加到名为 entries 的数组里，entries 数组的每个槽含有一个名为 Next 的整形变量保存碰撞链的下一个槽的下标，此乃数组模拟单向链表易做图。与概念模型一样，数组 buckets 负责保存每个 Key 的散列值所对应的存储单元的地址，只不过在概念模型里 buckets 的每个槽保存的是一个链表的地址，在实现模型里 buckets 的每个槽保存的是 entries 数组的一个下标，如下图所示。
Dictionary 的实现细节
如果这时再向字典里添加一个 Key = 50，首先要把它存放到 entries[5] 里，即 entries[5].Key = 50。然后计算 50 的散列值，50 % 11 = 6，要执行 buckets[6] = 5，但是 buckets[6] 里面已经有值了，亦即发生了碰撞，这时要先把 buckets[6] 里的下标存放到 entries[5].Next 里，即 entries[5].Next = buckets[6]，然后才能把 buckets[6] 的值改成5，如下图所示。
如果想要查找 Key = 39 那一项，要先计算它的散列值为 39 % 11 = 6，然后由 buckets[6] 取得 entries 下标 5，然后判断 entries[5].Key 是不是 39，如果不是，由 entries[5].Next 取得碰撞链的下一个槽的地址 4，再判断 entries[4].Key 是不是 39，如果是的话就找到了这一项。
删除的时候有些麻烦。我们有两个选择：“物理”删除和“逻辑”删除。以删除 Key = 15 那一项为例。“物理”删除是指让 entries[1] = {17, -1}、entries[2] = {28, 1}、entries[3] = {39, 2}、entries[4] = {50, 3}、 entries[5] = {0, -1}，让 buckets[4] = -1、buckets[6] = 4。“逻辑”删除是指让 entries[1].hashCode = -1 表示已删除（hashCode 字段我没有在上图画出来），让 buckets[4] = -1。显然，只有“逻辑”删除才能保证 O(1) 的复杂度。但是“逻辑”删除会使得 entries 数组不连续，所以每次添加新项的时候，都应该优先添加到因被删除而空出来的槽里。但是怎么才能知道哪些槽是因被删除而空出来的槽呢？不能通过遍历 entries 数组的方法，那是 O(n) 复杂度的操作。所以要为 Dictionary 增加一个整型变量 freeList，用来保存最后一个因删除而空出来的槽的下标，然后，让最后一个因删除而空出来的槽的 Next 属性保存倒数第二个因删除而空出来的槽的下标，由此形成一个删除链，Next 属性是两用的！此外，还需要为 Dictionary 增加一个整型变量 freeCount，用来保存因被删除而空出来的槽的数量，每次添加新项的时候，如果发现 freeCount > 0 就应该把新项添加到因删除而空出来的槽里。下图演示删除 Key = 15 和 Key = 39 这两项之后的状态，蓝色箭头表示碰撞链，红色箭头表示删除链。
一点题外话：此前，我一直都以为 Dictionary 可以保持添加时的顺序，刚刚翻了下 MSDN，原来人家压根没这么保证过！如果只添加不删除的话，确实恰巧可以保持添加时的顺序不变。但是如果删除过，这个顺序就没有保证了！这一点和 List 是不同的，使用时应注意不要让程序依赖于 Dictionary 的顺序。
这时候，如果再要添加一项，就应该添加到删除链的第一个空槽也就是 entries[4] 里面。当然，在添加之前还要判断是否发生了碰撞，如果发生了碰撞，要把新项加入到碰撞链上。
Dictionary 还有一个整型变量 count，用来记录一共已经添加了多少项到 Dictionary 之中。一方面，用户可以通过它获取实际添加到 Dictionary 的项的数量。另一方面，当 freeCount = 0 也就是删除链已被填满时，entries[count] 正好就是下一个空槽。
说到这里，虽然还没有涵盖所有的实现细节，但是已经到了“做的人很爽，听的人未必”的地方了。再唠叨更多的细节，只会让人烦闷。如果您有那个闲情逸致的话，不妨立即动手自己实现一个 MyDictionary，然后把您的实现代码与微软的代码比较比较，看看无论从思维的严密程度和逻辑性，还是从程序的可读性（当然像基础算法这种几百年也不改一次的代码可读性往往要让位于榨取那几毫秒的性能）和编码风格，以及性能上到底有哪些不同。
最后，附上 .net framework4 源代码里的 Dictionary.cs，您可以先偷偷瞄上几眼，再做打算 : )
补充：综合编程 , 其他综合 ,
