你知道Dictionary查找速度为什么快吗？

liucqa

http://www.cnblogs.com/zhili/p/DictionaryInDepth.html

当添加第一个元素时，此时会分配哈希表buckets数组和entries数组的空间和初始大小为3，分配完成之后，会计算添加元素key值的哈希值，哈希值的计算由具体的哈希算法来实现的，假设1的哈希值为9的话，此时targetBucket = 9%buckets.Length(3)的值为0，index的值为0，则第一个元素存放在entries列表中的第一个位置，最后对哈希表进行赋值，此时赋值的位置为第0个位置，其值为index的值，所以为0，插入第一个元素后Dictionary的内部结构如下所示：



　　后面添加元素的过程依次类推。其原理就是，buckets记录了元素的在元素列表的存储位置，也就相当于一个映射列表。在查找的时候，就可以通过key值的哈希值来与buckets数组长度求余来获得元素在元素列表中的索引，这样就可以快速定位元素的位置，从而获得元素的key对应的Value值。如上面的例子中，如果想找到key值为1对应的Value值时，此时计算1的哈希值为9，然后对buckets数组长度求余，此时获得的值正是0，这样就可以直接从entries[0].Value的方式来获取对应的Value的值，这也就是Dictionary能完成快速查找的实现原理。后面会通过Dictionary内部的查找源码来证实上面分析的过程。

　　2.2 解决冲突
　　在添加元素过程中，有一个很重要的问题，如果产生冲突怎么办？即如果我后面需要插入的一个元素(假设这个值为11吧)的key值的哈希值也为6，此时targetBucket的值也是为0，但元素列表中0的位置已经存放了元素了，这样就出现了冲突，那Dictionary是怎样处理这个冲突的呢？处理冲突的方法有很多种，Dictionary处理的方式是链接法。Dictionary会把发生冲突的元素链接之前元素的后面，通过next属性来指定冲突关系。