C# -- Dictionary，SortedDictionary与OrderedDictionary

Dictionary

属于 System.Collections.Generic命名空间下。

提供了键到值的映射，每次添加元素都包含一个值及其关联的键，使用键查找值很快接近O(1)。因为 Dictionary<TKey,TValue> 类是作为哈希表实现的。键不能为空，如果值为引用类型则可以为空。

SortedDictionary

属于 System.Collections.Generic命名空间下。

表示按键排序的键/值对的集合。

SortedDictionary<TKey,TValue> 泛类是一种二进制搜索树，检索速度为 O(log n)，其中 n 是字典中元素的个数。

在这方面，它与 SortedList<TKey,TValue> 泛型类相似。这两个类的对象模型相似，检索速度都是 O(log n)。这两个类的不同之处在于内存使用以及插入和删除的速度：

SortedDictionary<int, string> sd = new SortedDictionary<int, string>();
sd.Add(9, "九");
sd.Add(8, "八");
sd.Add(7, "七");
sd.Add(6, "六");
sd.Add(1, "一");
sd.Add(5, "五");
sd.Add(3, "三");
sd.Add(2, "二");

foreach (var item in sd)
{
	Console.WriteLine("key:" + item.Key.ToString() + " ; value:" + item.Value);
}
/*
key:1 ; value:一
key:2 ; value:二
key:3 ; value:三
key:5 ; value:五
key:6 ; value:六
key:7 ; value:七
key:8 ; value:八
key:9 ; value:九
*/

只要在 SortedDictionary<TKey,TValue> 中作为键使用，键就必须是不可变的。SortedDictionary<TKey,TValue> 中的每个键都必须是唯一的。键不能为空，但如果值类型 TValue 是引用类型，则值可以为空。

SortedDictionary<TKey,TValue> 需要一个比较器实现来执行键比较。通过使用接受比较器参数的构造函数，可以指定 IComparer 泛型接口的实现；如果没有指定实现，则使用默认的泛型比较器 Comparer.Default。

如果 TKey 类型实现了 System.IComparable 泛型接口，则默认比较器使用TKey实现的比较器。

OrderedDictionary

属于 System.Collections.Specialized命名空间下。

表示可通过键或索引访问的键/值对的集合。

**每个元素都是存储在 DictionaryEntry 对象中的键/值对。**键不能为空，但值可以为空。

与 SortedDictionary<TKey,TValue> 类的元素不同，OrderedDictionary 的元素不会按键排序。可以通过键或索引访问元素。

foreach (DictionaryEntry de in myOrderedDictionary)
{//...}

可以在添加数据时保持数据的顺序

OrderedDictionary od = new OrderedDictionary();
Dictionary<String, String> d = new Dictionary<String, String>();
Random r = new Random();

for (int i = 0; i < 10; i++)
{
    od.Add("key" + i, "value" + i);
    d.Add("key" + i, "value" + i);
    if (i % 3 == 0)
    {
		var key = r.Next(d.Count);
        od.Remove("key" + key);
        d.Remove("key" + key);
    }
}

Console.WriteLine("OrderedDictionary");
foreach (DictionaryEntry de in od)
{
    Console.WriteLine(de.Key + ", " + de.Value);
}

Console.WriteLine("Dictionary");
foreach (var tmp in d)
{
    Console.WriteLine(tmp.Key + ", " + tmp.Value);
}
/*
OrderedDictionary
key2, value2
key4, value4
key6, value6
key7, value7
key8, value8
key9, value9
Dictionary
key4, value4
key2, value2
key7, value7
key6, value6
key8, value8
key9, value9   
*/

在添加新条目后，Dictionary 通过将容量增加 2倍来调整内部数据结构的大小。这将导致在数组 Dictionary<TKey, TValue>.Entry[] entries 中再次插入带有新键的元素。这可能会导致更改项的顺序。链接