List 底层源码剖析

List 继承于IList，IReadOnlyList，IList是提供了主要的接口，IReadOnlyList提供了迭代接口。

看构造部分，我们明确了，List内部是用数组实现的，而不是链表，并且当没有给予指定容量时，初始的容量为0。

Add

上述List源代码中的Add函数，每次增加一个元素的数据，Add接口都会首先检查的是容量还够不，如果不够则用EnsureCapacity 来增加容量。每次容量不够的时候，整个数组的容量都会扩充一倍，_defaultCapacity 是容量的默认值为4。因此整个扩充的路线为4，8，16，32，64，128，256，512，1024…依次类推。

List使用数组形式作为底层数据结构，好处是使用索引方式提取元素很快，但在扩容的时候就会很糟糕，每次new数组都会造成内存垃圾，这给垃圾回收GC带来了很多负担。

Remove

Remove接口中包含了 IndexOf 和 RemoveAt，其中用 IndexOf 函数是位了找到元素的索引位置，用 RemoveAt 可以删除指定位置的元素。

从源码中我们可以看到，元素删除的原理其实就是用 Array.Copy 对数组进行覆盖。IndexOf 启用的是 Array.IndexOf 接口来查找元素的索引位置，这个接口本身内部实现是就是按索引顺序从0到n对每个位置的比较，复杂度为O(n)。

Insert

与Add接口一样，先检查容量是否足够，不足则扩容。从源码中获悉，Insert插入元素时，使用的用拷贝数组的形式，将数组里的指定元素后面的元素向后移动一个位置。

Clear

Clear接口在调用时并不会删除数组，而只是将数组中的元素清零，并设置 _size 为 0 而已，用于虚拟地表明当前容量为0。

Contains

从源代码中我们可以看到，Contains 接口使用的是线性查找方式比较元素，对数组进行迭代，比较每个元素与参数的实例是否一致，如果一致则返回true，全部比较结束还没有找到，则认为查找失败。

ToArray

ToArray接口中，重新new了一个指定大小的数组，再将本身数组上的内容考别到新数组上，再返回出来。

Find

Find接口使用的同样是线性查找，对每个元素都进行了比较，复杂度为O(n)。

Enumerator

其中我们需要注意 Enumerator 这个结构，每次获取迭代器时，Enumerator 每次都是被new出来，如果大量使用迭代器的话，比如foreach就会造成大量的垃圾对象，这也是为什么我们常常告诫程序员们，尽量不要用foreach，因为 List 的 foreach 会增加有新的 Enumerator 实例，最后由GC垃圾回收掉。

Sort

它使用了 Array.Sort接口进行排序。
Array.Sort 使用的是快速排序方式进行排序，从而我们明白了 List 的 Sort 排序的效率为O(nlogn)。

总结

我们把大部分的接口都列了出来，差不多把所有的源码都分析了一遍，我们可以看到 List 的效率并不高，只是通用性强而已，大部分的算法都使用的是线性复杂度的算法，这种线性算法当遇到规模比较大的计算量级时就会导致CPU的大量损耗。
我们可以自己改进它，比如不再使用有线性算法的接口，自己重写一套，但凡要优化List 中的线性算法的地方都使用，我们自己制作的工具类。
List的内存分配方式也极为不合理，当List里的元素不断增加时，会多次重新new数组，导致原来的数组被抛弃，最后当GC被调用时造成回收的压力。
我们可以提前告知 List 对象最多会有多少元素在里面，这样的话 List 就不会因为空间不够而抛弃原有的数组，去重新申请数组了。
List源码
另外我们也可以从源码上看得出，代码是线程不安全的，它并没有对多线程下做任何锁或其他同步操作。并发情况下，无法判断 _size++ 的执行顺序，因此当我们在多线程间使用 List 时加上安全机制。
最后List 并不是高效的组件，真实情况是，他比数组的效率还要差的多，他只是个兼容性比较强得组件而已，好用，但效率差。

Dictionary底层源码剖析

关键字Key是如何映射到内存

这种映射关系可以用一个Hash函数来建立，Dictionary 也确实是这样做的。这个Hash函数也并非神秘，我们可以简单的认为它只是做了一个模(Mod余)的操作，Dictionary 将每个Key加入容器的元素都要进行一次Hash哈希的运算操作，从而找到自己的位置。
Hash函数可以有很多种算法，最简单的可以认为是余操作。

处理Hash哈希冲突

在处理Hash哈希冲突的方法中通常有：开放定址法、再哈希法、链地址法、建立一个公共溢出区等。Dictionary使用的解决冲突方法是拉链法，又称链地址法。

拉链法的原理

将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为n，则可将散列表定义为一个由n个头指针组成的指针数组T[0..n-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。
在哈希表上进行查找的过程，和，在哈希表构建的过程是基本一致的。
给定Key值，根据造表时设定的哈希函数求得哈希地址，若表中此位置没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据处理冲突的方法寻找“下一地址”，直到哈希表中某个位置为空或者表中所填记录的关键字等于给定值时为止。

Dictionary

从继承的类和接口看，Dictionary 主要继承了 IDictionary 接口，和 ISerializable 接口。IDictionary 和 ISerializable 在使用过程中，其主要的接口为，Add, Remove, ContainsKey, Clear, TryGetValue, Keys, Values, 以及[]数组符号形式作为返回值的接口。也包括了常用库 Collection 中的接口，Count, Contains等。

从 Dictionary 的定义变量中可以看出，Dictionary 是以数组为底层数据结构的类。当我们实例化 new Dictionary() 后，内部的数组是0个数组的状态。与 List 组件一样，Dictionary 也是需要扩容的，会随着元素数量的增加而不断扩容。

Add

调用函数获得Hash哈希值后，还需要对哈希地址做余操作，以确定地址落在 Dictionary 数组长度范围内不会溢出。
紧接着对指定数组单元格内的链表元素做遍历操作，找出空出来的位置将值填入。

Remove

同样用哈希函数 comparer.GetHashCode 再除余后得到范围内的地址索引，再做余操作确定地址落在数组范围内，从哈希索引地址开始，查找冲突的元素的Key是否与需要移除的Key值相同，相同则进行移除操作并退出。
注意源码中，Remove 的移除操作并没有对内存进行删减，而只是将其单元格置空，这是位了减少了内存的频繁操作。

ContainsKey

它调用了 FindEntry 函数，FindEntry 查找Key值位置的方法跟我们前面提到的相同。从用Key值得到的哈希值地址开始查找，查看所有冲突链表中，是否有与Key值相同的值，找到即刻返回该索引地址。

Dictionary 同List一样并不是线程安全的组件

Hashtable在多线程读写中是线程安全的，而 Dictionary 不是。如果要在多个线程中共享Dictionaray的读写操作，就要自己写lock以保证线程安全。

总结

他是由数组构成，并且由哈希函数完成地址构建，由拉链法冲突解决方式来解决冲突。
从效率上看，同List一样最好在实例化对象时，即 new 时尽量确定大致数量会更加高效，另外用数值方式做Key比用类实例方式作为Key值更加高效率。
从内存操作上看，大小以3->7->17->37->….的速度，每次增加2倍多的顺序进行，删除时，并不缩减内存。
如果想在多线程中，共享 Dictionary 则需要进行我们自己进行lock操作。