首页 > 代码库 > 从内部剖析C# 集合之--Dictionary
从内部剖析C# 集合之--Dictionary
Dictionary和hashtable用法有点相似，他们都是基于键值对的数据集合，但实际上他们内部的实现原理有很大的差异，
先简要概述一下他们主要的区别，稍后在分析Dictionary内部实现的大概原理。
区别：1，Dictionary支持泛型，而Hashtable不支持。
2，Dictionary没有装填因子（Load Facto）概念，当容量不够时才扩容（扩容跟Hashtable一样，也是两倍于当前容量最小素数），Hashtable是“已装载元素”与”bucket数组长度“大于装载因子时扩容。
3，Dictionary内部的存储value的数组按先后插入的顺序排序，Hashtable不是。
4，当不发生碰撞时，查找Dictionary需要进行两次索引定位，Hashtable需一次，。
Dictionary采用除法散列法来计算存储地址，想详细了解的可以百度一下，简单来说就是其内部有两个数组：buckets数组和entries数组(entries是一个Entry结构数组)，entries有一个next用来模拟链表，该字段存储一个int值，指向下一个存储地址（实际就是bukets数组的索引），当没有发生碰撞时，该字段为-1，发生了碰撞则存储一个int值，该值指向bukets数组.
下面跟上次一样，按正常使用Dictionary时，看内部是如何实现的。
一，实例化一个Dictionary, Dictionary<string,string> dic=new Dictionary<string,string>();
a,调用Dictionary默认无参构造函数。
b,初始化Dictionary内部数组容器：buckets int[]和entries<T,V>[]，分别分配长度3。（内部有一个素数数组:3,7,11,17....如图：
）；
二，向dic添加一个值,dic.add("a","abc");
a,将bucket数组和entries数组扩容3个长度。
b,计算"a"的哈希值,
c,然后与bucket数组长度（3）进行取模计算，假如结果为：2
d,因为a是第一次写入，则自动将a的值赋值到entriys[0]的key,同理将"abc"赋值给entriys[0].value,将上面b步骤的哈希值赋值给entriys[0].hashCode,
entriys[0].next 赋值为-1,hashCode赋值b步骤计算出来的哈希值。
e,在bucket[2]存储0。
三，通过key获取对应的value, var v=dic["a"];
a, 先计算"a"的哈希值，假如结果为2，
b,根据上一步骤结果，找到buckets数组索引为2上的值，假如该值为0.
c, 找到到entriys数组上索引为0的key,
1），如果该key值和输入的的“a”字符相同，则对应的value值就是需要查找的值。
2) ，如果该key值和输入的"a"字符不相同，说明发生了碰撞，这时获取对应的next值，根据next值定位buckets数组（buckets[next]），然后获取对应buckets上存储的值在定位到entriys数组上,......,一直到找到为止。
3），如果该key值和输入的"a"字符不相同并且对应的next值为-1,则说明Dictionary不包含字符“a”。
Dictionary里的其他方法就不说了，各位可以自己去看源码，下面来通过实验来对比Hashtable和Dictionary的添加和查找性能，
1，添加元素速度测评。
循环5次，每次内部在循环10次取平均值，PS：代码中如有不公平的地方望各位指出，本人知错就改。
代码：
static void Main(string[] args) { for (int i = 0; i < 5; i++) { Console.WriteLine(string.Format("第{0}次执行:", i + 1)); Add(); Console.WriteLine("-------华丽的分分隔线---------"); } Console.ReadKey(); } public static void Add() { Hashtable ht = new Hashtable(); Stopwatch st = new Stopwatch(); long ticks1 = 0; for (int j = 0; j < 10; j++) { st.Reset(); st.Start(); for (int i = 0; i < 1000000; i++) { ht.Add(i, i); } st.Stop(); ticks1 += st.ElapsedTicks; ht.Clear(); } Console.WriteLine(string.Format("Hashtable添加:{0}个元素，消耗:{1}", 1000000, ticks1 / 10)); Dictionary<int, int> dic = new Dictionary<int, int>(); ticks1 = 0; for (int j = 0; j < 10; j++) { st.Reset(); st.Start(); for (int i = 0; i < 1000000; i++) { dic.Add(i, i); } st.Stop(); ticks1 += st.ElapsedTicks; dic.Clear(); } Console.WriteLine(string.Format("Dictionary添加:{0}个元素，消耗:{1}", 1000000, st.ElapsedTicks)); }
结果：
通过运行结果来看，HashTable 速度明显慢于Dictionary,相差一个数量级。我个人分析原因可能为：
a，Hashtable不支持泛型，我向你添加的int类型会发生装箱操作，而Dictionary支持泛型。
b，Hashtable在扩容时会先new一个更大的数组，然后将原来的数据复制到新的数组里，还需对新数组里的key重新哈希计算（这可能是最性能影响最大的因素）。而Dictionary不会这样。
2，查找速度测评(两种情况：值类型和引用类型)
1 值类型
static void Main(string[] args) { // GetByString(); GetByInt(); Console.ReadKey(); } public static void GetByInt() { //Hashtable Hashtable hs = new Hashtable(); Dictionary<int, int> dic = new Dictionary<int, int>(); for (int i = 0; i < 10000000; i++) { hs.Add(i, i); dic.Add(i, i); } long ticks = 0; Stopwatch st = new Stopwatch(); st.Reset(); for (int i = 0; i < 10; i++) { st.Start(); var result = hs[99999+i]; st.Stop(); ticks += st.ElapsedTicks; st.Reset(); } Console.WriteLine(string.Format("Hashtable查找10次，平均消耗：{0}", (float)ticks / 10)); //Dictionary ticks = 0; st.Reset(); for (int i = 0; i < 10; i++) { st.Start(); var result = dic[i]; st.Stop(); ticks += st.ElapsedTicks; st.Reset(); } Console.WriteLine(string.Format("Dictionary查找10次，平均消耗：{0}", (float)ticks / 10)); }
运行结果
2，引用类型
1 static void Main(string[] args) 2 { 3 GetByString(); 4 5 Console.ReadKey(); 6 } 7 8 public static void GetByString() 9 { 10 //Hashtable 11 Hashtable hs = new Hashtable(); 12 Dictionary<string, string> dic = new Dictionary<string, string>(); 13 14 for (int i = 0; i < 1000000; i++) 15 { 16 hs.Add(i.ToString(), i.ToString()); 17 dic.Add(i.ToString(), i.ToString()); 18 } 19 long ticks = 0; 20 Stopwatch st = new Stopwatch(); 21 st.Reset(); 22 string key = "9999"; 23 for (int i = 0; i < 10; i++) 24 { 25 st.Start(); 26 var result = hs[key]; 27 st.Stop(); 28 ticks += st.ElapsedTicks; 29 st.Reset(); 30 } 31 Console.WriteLine(string.Format("Hashtable查找10次，平均消耗：{0}", (float)ticks / 10)); 32 33 //Dictionary 34 ticks = 0; 35 st.Reset(); 36 for (int i = 0; i < 10; i++) 37 { 38 st.Start(); 39 var result = dic[key]; 40 st.Stop(); 41 ticks += st.ElapsedTicks; 42 st.Reset(); 43 } 44 Console.WriteLine(string.Format("Dictionary查找10次，平均消耗：{0}", (float)ticks / 10)); 45 }
运行结果
根据上面实验结果可以得出：
a,值类型,Hashtable和Dictionary性能相差不大,Hashtable稍微快于Dictionary.
b,引用类型：Hashtable速度明显快于Dictionary。
PS：以上是个人不成熟观点，如果错误请各位指出，谢谢,下篇介绍 SortedList 集合。
另：公司最近招聘.net和java程序员若干，如各位有找工作打算的，请发简历到wangjun@tonglukuaijian.com。
公司在上海闵行浦江智谷。