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