本文由一个在Dictionary中使用String作为key，且支持大小写不敏感匹配的例子来说明Dictionary的内部原理。由Key获取hash值是Dictionary实现的关键。在Dictionary声明的时候，可以通过构造函数传递IEqualityComparer参数来指定比较器，通过该对象来获取哈希值。如果不提供这个参数，则会在内部判断Key是否实现了IEquatable泛型接口，如果提供了，则使用该泛型接口中定义的GetHashCode来获取哈希值，否则会根据Key的类型生成一个通用的EqualityComparer，这个通过的EqualityComparer的参数是object类型，所以如果Key的类型为结构体，则必须为其实现IEquatable泛型接口，否则就会产生装箱从而严重影响性能。 …
Dictionary是一种存储键值对的数据结构，可以根据Key快速查找对应的Value，它的内部实现原理其实很简单，在浅谈算法和数据结构: 十一 哈希表这篇文章中有详细介绍，但实际的原理和工程实现可能有所不同，在.NET中有.NET Framework和.NET Core的两个版本，大体相同，但细节上有所区别。这里以.NET Core中的Dictionary源码为例，来说明Dictionary的实现细节。 …
在前面的系列文章中，依次介绍了基于无序列表的顺序查找，基于有序数组的二分查找，平衡查找树，以及红黑树，下图是他们在平均以及最差情况下的时间复杂度： 可以看到在时间复杂度上，红黑树在平均情况下插入，查找以及删除上都达到了lgN的时间复杂度。 那么有没有查找效率更高的数据结构呢，答案就是本文接下来要介绍了散列表，也叫哈希表(Hash Table) 什么是哈希表 哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。 哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。 使用哈希查找有两个步骤: 使用哈希函数将被查找的键转换为数组的索引。在理想的情况 …