前两篇文章分别介绍了几种容器。他们之间的差别与联系也做了简单的介绍，这篇文章主要在存储机制和工作效率上来扩展一下。
我们从数据的角度将它们分为两类一维集合和二维集合（这里不讨论数组），一维集合主要包含ArrayList、List，二维集合主要包含HashTable、Dictionary<K,v>。其他类型（使用较少）不做讨论。
首先说一维集合，来源于数组。他们在内存中的存储机制也是来源于数组，以顺序存储的方式存放在内存中，下面标为索引查找数据。效率较高。
再来谈谈二维表。HashTable和Dictionary<K,V>，俗称字典都是键值对的集合。能够说Dictionary<K,V>事实上就是哈希表的泛型版本号。字典与一维集合的差别就是字典通过key来查找value。他的算法复杂度为O(1)，而一维数组通过下标索引查找value，算法复杂度也为O(1)，因而他们的存储机制全然不同。
我们先来看一下Dictionary<K,V>,和HashTable的差异。看下面两段代码：
class Program
{
static void Main(string[] args)
{
Dictionary<int, string> dicTest1 = new Dictionary<int, string>();
dicTest1.Add(1, "a");
dicTest1.Add(2, "b");
dicTest1.Add(3, "c");
foreach (var item in dicTest1)
{
Console.WriteLine("Dictionary输出顺序 key: " + item.Key );
}
Hashtable tableTest = new Hashtable();
tableTest.Add(1, "a");
tableTest.Add(2, "b");
tableTest.Add(3, "c");
foreach (var item in tableTest.Keys)
{
Console.WriteLine("HashTable输出顺序 key:" + item.ToString());
}
Console.ReadKey();
}
}
能够看的出来，字典在输出是全然是依照数据插入的顺序输出的，而哈希表会在插入数据时打乱其存储顺序。
再来看看二维集合的存储机制，在存储二维集合时，计算机会依据二维集合的key通过哈希算法计算出一个虚拟地址，然后将数据存储在相应位置。
查找数据时也一样。须要依据key通过哈希算法找到相应的虚拟地址，然后获得数据。
它们的效率有多大的差距呢？下图是一个高手写的程序的执行结果：
他们在遍历整个集合时效率的差距是非常大的。
所以，顺序表存储结构在遍历查询数据时。有非常大优势。
下图是几种字典在存储结构和性能上的差异总结：
|
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 |