程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> C#集合--Dictionary

C#集合--Dictionary

編輯:C#入門知識

字典(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); 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved