首页 / 软件开发 / .NET编程技术 / 谈谈Dictionary<T1,T2>和List<T>的问题

谈谈Dictionary<T1,T2>和List<T>的问题2011-01-03 博客园飞林沙引子：

事情的起因我已经记不清了，但是事情的根本原因在于，我们要遍历一个集合，是用字典来存储还是用数组链表来存储。

1.把基本概念说清

对List<T>的阐述，我在http://www.cnblogs.com/kym/archive/2009/03/09/1406657.html一文中已经有过相应的解释，再此不再赘述。

Dictionary<T1,T2>，我们俗称其为字典，他包含一个Key和与之对应的Value，其目的是能够根据Key迅速地找到Value，算法复杂度为O（1）。

2.Dictionary<T1,T2>和Hashtable的异同

首先很多人都认同一个观点，说Dictionary<T1,T2>是HashTable的泛型版本，这一点在大致上是正确的，可是当我们运行这样一段代码时，便可看出他们的不同：

代码

1             Dictionary<int, int> dic = new Dictionary<int, int>（）;
2             dic.Add（1, 5）;
3             dic.Add（10, 3）;
4             dic.Add（2, 5）;
5             foreach （int key in dic.Keys）
6             {
7                 Console.WriteLine（key）;
8             }
9
10             Hashtable hashtable = new Hashtable（）;
11             hashtable.Add（1, 5）;
12             hashtable.Add（10, 3）;
13             hashtable.Add（2, 5）;
14             foreach （object key in hashtable.Keys）
15             {
16                 Console.WriteLine（key.ToString（））;
17             }

Dictionary<T1,T2>是根据插入的顺序来遍历，但是Hashtable在插入时会打乱其位置。

并且我们在用Reflector看源码的时候也会发现

代码

1 if （（this.buckets[num6].key == null） || （（this.buckets[num6].key == this.buckets） && （（this.buckets[num6].hash_coll & 0x80000000L） == 0L）））
2     {
3         if （index ！= -1）
4         {
5             num6 = index;
6         }
7         Thread.BeginCriticalRegion（）;
8         this.isWriterInProgress = true;
9         this.buckets[num6].val = nvalue;
10         this.buckets[num6].key = key;
11         this.buckets[num6].hash_coll |= （int） num3;
12         this.count++;
13         this.UpdateVersion（）;
14         this.isWriterInProgress = false;
15         Thread.EndCriticalRegion（）;
16     }
17