C#集合：字典

字典是一种集合，其包含的元素均为键值对。字典通常用于查找或用作排序列表。
框架通过IDictionary和IDictionary<TKey, TValue>接口以及一系列通用的字典类定义了标准字典协议。

IDictionary<TKey, TValue>

IDictionary<TKey, TValue>定义了所有基于键值的集合的标准协议。它扩展了ICollection<T>接口，并增加了方法和属性以便使用任意类型的键进行元素访问：

public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>, 
    IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
    TValue this[TKey key] { get; set; }
    ICollection<TKey> Keys { get; }
    ICollection<TValue> Values { get; }

    void Add(TKey key, TValue value);
    bool ContainsKey(TKey key);
    bool Remove(TKey key);
    bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value);
}

如需向字典增加一个元素，则可以调用Add方法或者直接使用索引访问器。后者将在键并不存在于字典时创建相应键值，而在键存在的情况下则直接更新值。字典的实现不允许重复键，因此对同一个字典用同一个键调用两次Add方法将抛出异常。
我们可以使用索引器或者TryGetValue方法从字典中检索元素。如果键不存在，那么索引器会抛出异常，而TryGetValue则返回false。还可以用属性ContainsKey来确定键是否存在，但这样做意味着需要进行两次查找才能最终检索元素。
直接对IDictionary<TKey, TValue>进行枚举会返回一个KeyValuePair结构体序列：

public struct keyValuePair <TKey,TValue>
{
    public TKey Key {get;}
    public TValue Value {get;}
}

还可以通过字典的Keys和Values属性单独枚举键或者值。

IDictionary

非泛型的IDictionary接口在原理上与IDictionary<TKey, TValue>相同，但是存在以下两个重要的功能区别。我们需要注意这种区别，因为一些遗留代码（包括.NET Framework本身）仍然在使用IDictionary。

• 若试图通过索引器检索一个不存在的键，则会返回null（而不是抛出一个异常）。
• 使用Contains而非ContainsKey来检测成员是否存在。

枚举非泛型的IDictionary会返回一个DictionaryEntry结构体序列：

public struct DictionaryEntry
{
    public object Key { get;set; }
    public object Value { get;set; }
}

Dictionary<TKey, TValue>和Hashtable

泛型的Dictionary类（和List<T>集合一样）是使用最广泛的集合之一。它使用一个散列表数据结构来存储键和值，而且快速、高效。

Hashtable是非泛型的Dictionary<TKey, TValue>（没有非泛型的Dictionary类）。因此当提到Dictionary的时候，指的是泛型的Dictionary<TKey, TValue>类。

Dictionary同时实现了泛型和非泛型的IDictionary接口，其中泛型的IDictionary是公开接口。事实上，Dictionary是泛型IDictionary接口的一个标准实现。
下面的程序演示了它的用法：

var d = new Dictionary<string, int>();

d.Add("One", 1);
d["Two"] = 2;
d["Two"] = 22;
d["Three"] = 3;

Console.WriteLine (d["Two"]);                // 输出 "22"
Console.WriteLine (d.ContainsKey ("One"));   // true (操作快)
Console.WriteLine (d.ContainsValue (3));     // true (操作慢)
int val = 0;
if (!d.TryGetValue ("onE", out val))
    Console.WriteLine ("No val");            // "No val" (区分大小写)

// 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

非泛型版本的字典称为Hashtable。它们在功能上类似，其区别在于其提供的是非泛型的IDictionary接口。
Dictionary和Hashtable的缺点是其中的元素是无序的。而且在添加元素的时候并不保存原始顺序。此外，所有的字典类型都不允许出现重复的键。

OrderedDictionary

OrderedDictionary是一种非泛型字典，它能够保存添加元素时的原始顺序。使用OrderedDictionary既可以根据索引访问元素，也可以根据键来访问元素。
OrderedDictionary是Hashtable和ArrayList的组合。因为它具有Hashtable的所有功能，也有诸如RemoveAt以及整数索引器等功能。它的Keys和Values属性可以按照原始添加的顺序返回键或值。它并非排序字典也没有泛型版本。

ListDictionary和HybridDictionary

ListDictionary使用一个独立链表来存储实际的数据。虽然它能够保存添加元素时的原始顺序，但是它不支持排序。ListDictionary在处理大型列表时非常缓慢。它存在的真正意义是高效处理非常小的列表（小于10个元素）。
HybridDictionary是一个在达到一定大小后能够自动转换为Hashtable的ListDictionary。其目的是为了解决ListDictionary的性能问题。它的原理在于在字典很小时降低内存开销，而在字典变大时保持良好性能。然而，考虑到中间存在转换的开销，而且Dictionary在这两种情况下都不会太严重或太慢，因此即使直接使用Dictionary也是非常合理的。
这两种类都只有非泛型形式。

排序字典

框架支持两种在内部将内容根据键进行排序的字典类：
SortedDictionary<TKey, TValue>和SortedList<TKey, TValue>。

SortedDictionary<TKey, TValue>内部为红黑树：一种在插入和检索中表现都相当不错的数据结构。
SortedList<TKey, TValue>的内部实现是排序的数组对。它的检索速度很快（通过二分搜索），但插入性能很差（因为必须移动现有值才能够留出空间存储新的元素）。

SortedDictionary<TKey, TValue>在随机序列（尤其是大型列表）中插入元素的速度比SortedList<TKey, TValue>快得多，然而SortedList<TKey, TValue>也有突出的功能，即可以按照索引也可通过键对元素进行访问。
SortedList<TKey, TValue>可以（通过Keys、Values属性的索引器）直接访问排序列表中的第n个元素。而在SortedDictionary<TKey, TValue>中只能够通过枚举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

以上的例子也适用于SortedDictionary<TKey, TValue>。然而，下面两行代码将分别检索最后一个键和最后一个值，且仅仅适用于排序列表：

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