C#集合--Dictionary

字典(dictionary)是一個集合，其中每個元素都是一個鍵/值對。字典(Dictionaries)是常用于查找和排序的列表。

.NET Framework通過IDictionary接口和IDictionary<TKey,TValue>接口，以及一些常用的子典了定義了子典協議。每個類在以下方面各有不同：

• 元素是否已經排序
• 元素是否能通過索引或鍵來獲取
• 字典類是generic的還是非generic的
• 當字段較大時，根據鍵值獲取元素速度的快慢

下表總結了每個字典類，以及它們在上述這幾個方面的差異。它們都是在一個1.5G的PC上執行5000次操作得到的一個平均值。

從時間復雜度來講，從字典中通過鍵獲取值所耗費的時間分別如下：

• Hashtable, Dictionary和OrderedDictionary的時間復雜度為O(1)
• SortedDictionary和SortList的時間復雜度為O(logN)
• ListDictinary的時間復雜度為O(n)

n是集合元素的數量。

IDictionary<TKey, TValue>

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

public interface IDictionary <TKey, TValue> :ICollection <KeyValuePair <TKey, TValue>>, IEnumerable{bool ContainsKey (TKey key);bool TryGetValue (TKey key, out TValue value);void Add (TKey key, TValue value);bool Remove (TKey key);TValue this [TKey key] { get; set; } // Main indexer - by keyICollection <TKey> Keys { get; } // Returns just keysICollection <TValue> Values { get; } // Returns just values}

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

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

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

[Serializable]public struct KeyValuePair<TKey, TValue> {    PRivate TKey key;    private TValue value;    public KeyValuePair(TKey key, TValue value) {        this.key = key;        this.value = value;    }    public TKey Key {        get { return key; }    }    public TValue Value {        get { return value; }    }    public override string ToString() {        StringBuilder s = StringBuilderCache.Acquire();        s.Append('[');        if( Key != null) {            s.Append(Key.ToString());        }        s.Append(", ");        if( Value != null) {           s.Append(Value.ToString());        }        s.Append(']');        return StringBuilderCache.GetStringAndRelease(s);    }}

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

IDictionary

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

1. 如果獲取的對象不存在，返回null，不會拋出異常
2. 使用Contains方法以測試一個成員是否在字典中存在，而不是ContainsKey方法

public interface IDictionary : ICollection{    // Interfaces are not serializable        // The Item property provides methods to read and edit entries         // in the Dictionary.    Object this[Object key] {            get;            set;        }    // Returns a collections of the keys in this dictionary.    ICollection Keys {            get;        }    // Returns a collections of the values in this dictionary.    ICollection Values {            get;        }    // Returns whether this dictionary contains a particular key.        //    bool Contains(Object key);    // Adds a key-value pair to the dictionary.        //     void Add(Object key, Object value);    // Removes all pairs from the dictionary.    void Clear();    bool IsReadOnly         { get; }    bool IsFixedSize        { get; }    // Returns an IDictionaryEnumerator for this dictionary.    new IDictionaryEnumerator GetEnumerator();    // Removes a particular key from the dictionary.        //    void Remove(Object key);}

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

[Serializable]public struct DictionaryEntry{    private Object _key;    private Object _value;    // Constructs a new DictionaryEnumerator by setting the Key        // and Value fields appropriately.    public DictionaryEntry(Object key, Object value) {            _key = key;            _value = value;        }    public Object Key {            get {                return _key;            }                        set {                _key = value;            }        }    public Object Value {            get {                return _value;            }            set {                _value = value;            }        }}

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>類：

var d = new Dictionary<string, int>();d.Add("One", 1);d["Two"] = 2; // adds to dictionary because "two" is not already presentd["Two"] = 22; // updates dictionary because "two" is now presentd["Three"] = 3;Console.WriteLine (d["Two"]); // Prints "22"Console.WriteLine (d.ContainsKey ("One")); // true (fast Operation)Console.WriteLine (d.ContainsValue (3)); // true (slow operation)int val = 0;if (!d.TryGetValue ("onE", out