C#集合--Dictionary

字典(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是集合元素的數量。

 

IDictionary<TKey, TValue>

IDictionary<TKey,Tvalue>指定了所有以key/value為基礎集合的標准協議。由於它添加了方法和屬性用以通過鍵讀取元素，從而擴展了ICollection<T>接口：

  IDictionary <TKey, TValue><KeyValuePair <TKey, TValue>> TryGetValue (TKey key,  [TKey key] { ; ; } 
ICollection <TKey> Keys { ; } 
ICollection <TValue> Values { ; } 
}

向字典中添加一個元素，你可以調用add方法，或者通過索引器的set方法；對於後者，如果添加元素的鍵在字段中不存在，那麼把該元素插入到字典中；否則更新字典中相同鍵對應的值。所有的字典實現類都不接受重復鍵，所以兩次調用add方法時使用相同鍵則會拋出異常。

從字段中獲取一個元素，可以使用索引器的get方法或者調用TryGetValue方法。如果鍵不存在，使用索引器方法會拋出異常，而TryGetValue返回false。你可通過ContainsKey方法來確認某一個鍵是否在字典中存在；但是這樣會導致額外的查詢開銷。

可以通過KeyValuePari結構來遍歷IDictionary<TKey,TValue>。

  KeyValuePair<TKey, TValue>.key =.value = {  {   =( Key != ( Value != 

當然，你也可以通過字典的Keys或Values屬性遍歷字典的所有鍵或值。在Dictionary類中，將演示該接口是如何使用的。

 

 

IDictionary

IDictionary是非generic的字典接口；與IDictionary<TKey, TValue>比較有兩處不同：

 
    Object 

     
    
    
        

通過DictionaryEntry接口來遍歷非generic的字典

 
    ====

 

Dictionary<TKey, TValue>和Hashtable

geneirc的Dictionary類是使用最多的集合類（此外，就是List<T>集合類）。Dictionary<TKey, TValue>使用哈希數據結構來存儲鍵和值，因此它既快速又高效。

非generic的Dictionary<TKey, TValue>就是Hashtable；因此不存在非generic的類Dictionary。當我們提及Dictionary時，我們一般是指Dictionary<TKey, TValue>。

Dictionary實現了generic和非generic的IDictionary接口，generic的IDictonary都暴露為public。實際上，Dictionary如果教科書一般地實現了generic的IDictionary接口。

下面的代碼演示了如何使用Ditionary<TKey, TValue>類：

 d =  Dictionary<, >, ] = ; 
d[] = ; 
d[] = ]); 
Console.WriteLine (d.ContainsKey ()); 
Console.WriteLine (d.ContainsValue ()); 
 val =  (!d.TryGetValue (, ); 
 (KeyValuePair<, > kv  d) 
Console.WriteLine (kv.Key +  + kv.Value); 
 ( s  d.Keys) Console.Write (s); 
 ( i  d.Values) Console.Write (i); 

該類背後的哈希表，把每個鍵都轉換成一個整數型的哈希碼，然後通過算法將其轉換成一個哈希鍵。在內部通過哈希鍵確定一個成員屬於哪一個“桶”；如果一個“桶”包含多個值，那麼對該“桶”執行線型搜索。一個好的哈希算法，不僅努力實現返回一個嚴格的哈希碼，而且還努力實現所返回的哈希碼在32位的整數中均勻地分布。

字典可以包含任何類型的鍵，只要這些鍵支持是否相等接口並能獲取哈希碼。在默認情況下，鍵的相等性取決於對象的Equals方法，而計算哈希鍵的算法也基於對象的GetHashCode方法。這些行為不是一成不變的，如果重載了Equals方法或GetHashCode方法，或在創建字典實例時提供了IEqualityComparer實例對象。一個常見的應用就是在使用字符串字段時，提供了區分大小寫的相等性比較器實例。

 d =  Dictionary<, > (StringComparer.OrdinalIgnoreCase);

與其它集合類型一樣，如果在構造字典實例時，指定字段的大小，那麼可以在一定程度上改善性能。指定字典的大小，可以避免或減少內部調正大小的操作。

Dictioanry和Hashtable的缺點是items並沒有排序。甚至，添加到字典中的成員也不會保留原有的順序。此外，字典還有一個缺點就是不接收重復的鍵。

 

OrderedDictionary

OrderedDictionary是非generic的字典類，它保存了成員原有的順序。使用OrderedDictioanry時，你可以通過索引或鍵獲取字段元素。

OrderedDictionary結合了Hashtable和ArrayList。這就意味著，它不僅有Hashtable的所有功能，還有RemoveAt，整數索引器方法。它還根據元素的原始順序對外暴露Keys和Values屬性。

該類在.NET 2.0中引入，而且沒有對應的非generic版本。

 

ListDictionary和HybirdDictionary

ListDictionary使用單鏈表存儲數據。它不提供排序，盡管它保留了元素的原始順序。當集合很大時，其性能相當低。它值得注意的地方僅僅在於當元素數量很小時有效率（元素少於10個）。

HybirdDictionary是一個ListDictionary，它會當元素數量達到一定數量後自動轉換成Hashtable，以解決ListDictionary的性能問題。這種想法可以使得字典元素很少時，占用較低的內存；而字典數量較大時擁有較好的性能。然而，在到了一定的數目後需要從一個數據類型轉換成另一個數據類型--而Dictionary在這兩種情況下都不會太慢或性能低--因此，你為何不在一開始就使用Dicontary類。

此外，這兩個類都是非generic的類。

 

可排序的Dictionary

Framework提供了兩個字典類，它們通過排序的鍵來構建。這兩個類就是SortedDictoanry<TKey, TValue>和 SortedList<Tkey,TValue>。

SortedDictoanry<TKey, TValue>，使用紅黑樹：一種數據結構，該數據結構保證了任何插入和獲取元素行為都是一致地。

SortedList<Tkey,TValue>，內部由一個排序後的數組對實現，可以實現快速讀取，但是插入性能較差。

 

SortedDictoanry<TKey, TValue>比SortedList快，按照隨機順序插入元素。 SortedList，有一個額外的功能，可以通過索引或鍵獲取元素。 使用排序後的列表，你可以直接找到第幾個元素。 而如果想在SortedDictionary中實現同樣的目的，那麼你需要手動的遍歷n個元素。

 

下面的例子演示了使用反射加載所有System.Object類的方法到一個排序後的列表，然後遍歷該列表的鍵和值

 sorted =  SortedList <, MethodInfo> (MethodInfo m   (= ( name  (MethodInfo m +  + m.ReturnType);

第一個列表的結果如下：

Equals
GetHashCode
GetType
ReferenceEquals
ToString

第二個的列表的結果如下：

Equals returns a System.Boolean
GetHashCode returns a System.Int32
GetType returns a System.Type
ReferenceEquals returns a System.Boolean
ToString returns a System.String

請注意，我們通過索引器填充字段類。如果我們使用add方法，那麼會拋出異常，這是因為我們所依賴的對象類重載了Equals方法，而你不能添加重復的鍵到一個字典中。而使用索引器，這會避免該問題。

如果擴展我們的示例，下面的代碼則會返回GetHashCode方法，其使用方法和一個普通的字典的使用方式一樣

Console.WriteLine (sorted []);

到現在，我們的代碼既適用於SortedDictionary也適用於SortedList。然而，下面兩行代碼僅僅適用於SortedList

Console.WriteLine (sorted.Keys [sorted.Count - ]); 
Console.WriteLine (sorted.Values[sorted.Count - ].IsVirtual);