对集合性能优化的原理分析

集合性能原理

最近做了个性能优化的事，发现其中有一项非常滥用性能消耗点。
那就是对List集合的查询，我们都喜欢用Linq语句。 如 var item = lisAllUser.First(p=>p.Name = “ZhangSan”);
通过性能分析，发现这里消耗非常大。经过大神指导，对List进行改造。
改造方式是，先new一个Dictionary 集合， 循环List 把p.Name做为key，把List中的Item做为Value 添加到Dictionary 集合， 这时候, 原来的var item = lisAllUser.First(p=>p.Name = “ZhangSan”);
改造为用var item =dic[“ZhangSan”] ;

改造后发现，性能达到百倍提升。为什么会这样的？原理是什么呢？
为了更好了使用集合，我对集合原理做了个研究。
我们常用的集合有 hashtable，dictionary，list,于是了解了一下他们的原理

一、为什么dictionary根据key来取值会比list快呢？它是如何取值的？

Dictionary的存储是使用Hash算法分析产生的内存地址，将值存储于对应的内存地址中。
取值时，直接去对应的内存地址取出对象，因此，没有产生遍历数组的过程。
List的存储,是顺序的存储到内存地址中，其中没有记录Name对应的地址，查询是，是通过遍历所有元素，比较Name是否是需要取出的，因此List元素数量越大，查询的速度越慢。

二、hashtable，dictionary 哪个快？

Hashtable也是使用Hash算法，将值存于对应的内存地址中。网上说dictionary是Hashtable的一个泛型实现。那么hashtable，dictionary 哪个快呢？
区别如下：
Hashtable存储的是object对象，dictionary存储的是泛型对象。
由于dictionary存储的是泛型对象于是节省了类型转换时消耗的性能。性能上更快。

三、既然如此，是否所有的List集合都该改造成dictionary呢?

Hashtable，Dictionary都是根据hash内存地址存储，没有严格的保证它的顺序，因此在foreach时有可能不会按照集合项添加顺序来取。而且这个顺序是无法估计的。
List的存储，是顺序存储，foreach下按顺序取出，由于存储的位置都在一起，所以遍历的性能比Dictionary更快。是否要将List改造成dictionary关键要看，取值是遍历取值，还是目标取值。同时是否有严格的取值顺序。

四、Hashtable 有什么用？

这么比较，发现Hashtable一无是处，既没有顺序，也没有泛型。它到底在什么时候用呢？
默认的 Hashtable 只允许单线程写入，支持多线程读取, 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型。
Dictionary是非线程安全的集合，在多线程下，需要先lock然后才能保证单线程写入。因此，多线程下，Hashtable节省了Lock开销，优势明显。

五、SortedList集合

为了应对Hashtable，Dictionary的顺序无法估计的情况，同时保留对Key的查询方式
出现了SortedList集合，保留了Key / Values的存储方式，并且对Key进行排序，提供了按key顺序遍历集合的方式。 当然按key取值性能上略比Dictionary慢。
需要注意的是SortedList 的扩容方式，当添加的元素数量大于集合的容量时，它将开辟一个更大的内存空间，然后把原来集合中的元素复制到新的地址。因此增加了非常多的性能消耗。而Dictionary是散列的，添加元素都是在新的地址添加，因此不需要扩容。正因为如此，SortedList 集合的元素都集中在一块内存空间，遍历的性能远超Dictionary。
SortedList节省性能开销的做法是，添加元素前就设置容量大小（Capacity属性），或者是先构造Dictionary，然后通过new SortedList(dic)来创建。

值得百度的相关术语：
Hashtable，Dictionary算法复杂度为O(1)；
散列计算，分离链接法，分离链接散列法
二叉搜索树，2-3-4树是红黑树在“理论”上的数据结构
SortedDictionary
SortedList