字典(dictionary)是一个集合，其中每个元素都是一个键/值对。字典(Dictionaries)是常用于查找和排序的列表。
.NET Framework通过IDictionary接口和IDictionary<TKey,TValue>接口，以及一些常用的子典了定义了子典协议。每个类在以下方面各有不同：
- 元素是否已经排序
- 元素是否能通过索引或键来获取
- 字典类是generic的还是非generic的
- 当字段较大时，根据键值获取元素速度的快慢
下表总结了每个字典类，以及它们在上述这几个方面的差异。它们都是在一个1.5G的PC上执行5000次操作得到的一个平均值。
| Type | 内部结构 | 支持索引 | 内存占用 | 随机插入的速度(毫秒) | 顺序插入的速度(毫秒) | 根据键获取元素的速度(毫秒) |
| 未排序字典 | ||||||
| Dictionary<T,V> | 哈希表 | 否 | 22 | 30 | 30 | 20 |
| Hashtable | 哈希表 | 否 | 38 | 50 | 50 | 30 |
| ListDictionary | 链表 | 否 | 36 | 50000 | 50000 | 50000 |
| OrderedDictionary | 哈希表 +数组 |
是 | 59 | 70 | 70 | 40 |
| 排序字典 | ||||||
| SortedDictionary<K,V> | 红黑树 | 否 | 20 | 130 | 100 | 120 |
| SortedList<K,V> | 2xArray | 是 | 20 | 3300 | 30 | 40 |
| SortList | 2xArray | 是 | 27 | 4500 | 100 | 180 |
从时间复杂度来讲，从字典中通过键获取值所耗费的时间分别如下：
- Hashtable, Dictionary和OrderedDictionary的时间复杂度为O(1)
- SortedDictionary和SortList的时间复杂度为O(logN)
- ListDictinary的时间复杂度为O(n)
n是集合元素的数量。
摘自： http://www.cnblogs.com/yang_sy/p/3678905.html