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>接口：

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 key
ICollection <TKey> Keys { get; } // Returns just keys
ICollection <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 present
d["Two"] = 22; // updates dictionary because "two" is now present
d["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 val))
Console.WriteLine ("No val"); // "No val" (case sensitive)
// Three different ways to enumerate the dictionary:
foreach (KeyValuePair<string, int> kv in d) // One ; 1
Console.WriteLine (kv.Key + "; " + kv.Value); // Two ; 22
// Three ; 3
foreach (string s in d.Keys) Console.Write (s); // OneTwoThree
Console.WriteLine();
foreach (int i in d.Values) Console.Write (i); // 1223

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

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

var d = new Dictionary<string, int> (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類的方法到一個排序後的列表，然後遍歷該列表的鍵和值

var sorted = new SortedList <string, MethodInfo>();
foreach (MethodInfo m in typeof (object).GetMethods())
sorted [m.Name] = m;
foreach (string name in sorted.Keys)
Console.WriteLine (name);
foreach (MethodInfo m in sorted.Values)
Console.WriteLine (m.Name + " returns a " + 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 ["GetHashCode"]);

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

Console.WriteLine (sorted.Keys [sorted.Count - 1]); // ToString
Console.WriteLine (sorted.Values[sorted.Count - 1].IsVirtual); // True