泛型字典類比較

Dictionary<TKey,TValue>, SortedDictionary<TKey,TValue>, SortedList<TKey,TValue>橫向評測

Dictionary<TKey,TValue>、SortedDictionary<TKey,TValue>與 SortedList<TKey,TValue>是.NET Framework的三個泛型的關鍵字查找的類，都屬于System.Collections.Generic命名空間。它們無論是名字還是功能都十分相似，以至于實際運用的時候我們會經常混淆。因此有必要比較一下它們。

1. 實現

查閱 MSDN 得到如下資料:

Dictionary<TKey, TValue>泛型類提供了從一組鍵到一組值的映射。字典中的每個添加項都由一個值及其相關聯的鍵組成。通過鍵來檢索值的速度是非常快的，接近于O(1)，這是因為Dictionary<TKey, TValue>類是作為一個哈希表來實現的。

檢索速度取決于為TKey指定的類型的哈希算法的質量。

可見，Dictionary<TKey, TValue>基本上就是一個Hashtable。不過它比Hashtable類快，因為它支持泛型~(稍后我們會用實驗證明，即使使用Object類型的Dictionary也比 Hashtable稍快)。

SortedDictionary<TKey, TValue>泛型類是檢索運算復雜度為O(log n)的二叉搜索樹，其中n是字典中的元素數。就這一點而言，它與SortedList<TKey, TValue>泛型類相似。這兩個類具有相似的對象模型，并且都具有O(log n)的檢索運算復雜度。這兩個類的區別在于內存的使用以及插入和移除元素的速度。

SortedList<TKey, TValue>使用的內存比SortedDictionary<TKey, TValue>少。

SortedDictionary<TKey, TValue>可對未排序的數據執行更快的插入和移除操作：它的時間復雜度為O(log n)，而SortedList<TKey, TValue>為O(n)。

如果使用排序數據一次性填充列表，則SortedList<TKey, TValue>比 SortedDictionary<TKey, TValue>快。

每個鍵/值對都可以作為KeyValuePair<TKey, TValue>結構進行檢索，或作為 DictionaryEntry通過非泛型IDictionary接口進行檢索。

只要鍵用作SortedDictionary<TKey, TValue>中的鍵，它們就必須是不可變的。SortedDictionary<TKey, TValue>中的每個鍵必須是唯一的。鍵不能為null引用），但是如果值類型TValue為引用類型，該值則可以為空。

SortedDictionary<TKey, TValue>需要比較器實現來執行鍵比較。可以使用一個接受 comparer參數的構造函數來指定IComparer<T>泛型接口的實現；如果不指定實現，則使用默認的泛型比較器Comparer<T>。如果類型TKey實現IComparable<T>泛型接口，則默認比較器使用該實現。

C#語言的foreach語句需要集合中每個元素的類型。由于SortedDictionary<TKey, TValue>的每個元素都是一個鍵/值對，因此元素類型既不是鍵的類型，也不是值的類型。而是KeyValuePair<TKey, TValue>類型。

可見，SortedDictionary<TKey, TValue>類似一個平衡二叉查找樹(AVL)。既然是 BST，我們當然可以對其進行中序遍歷。有兩種方法:

1. foreach

2. Object.GetEnumerator

小實驗:

CODE:

SortedDictionary<int, int> TestObject = new SortedDictionary<int, int>();

TestObject.Add(7, 2);

TestObject.Add(0, 1);

TestObject.Add(5, 3);

TestObject.Add(1, 1);

TestObject.Add(4, 4);

foreach (KeyValuePair<int, int> kvp in TestObject)

{

Console.WriteLine(kvp.Key);

}

得到的順序是0,1,4,5,7(SortedList<TKey, TValue>同樣)

但是如果把SortedDictionary<TKey, TValue>換成Dictionary<TKey, TValue>, 結果就是7,0,5,1,4。

另一種遍歷方法:

CODE:

SortedDictionary<int, int>.Enumerator sde = TestObject.GetEnumerator();

while (sde.MoveNext())

{

Console.WriteLine(sde.Current.Key);

}

SortedDictionary<TKey, TValue>類和SortedList<TKey, TValue>類之間的另一個區別是：SortedList<TKey, TValue>支持通過由Keys和Values屬性返回的集合對鍵和值執行高效的索引檢索。訪問此屬性時無需重新生成列表，因為列表只是鍵和值的內部數組的包裝。

QUOTE:

二叉樹的插入操作怎么是 O(n)?

網上有一種說法, 就是SortedList<TKey, TValue>內部就是兩個數組, 插入的時候類似O(n^2)的插入排序(每個動作為O(n))，不過插入有序數據特別快(每個動作變成O(1))。同樣的情況出現在刪除數據。

CODE:

Random ra = new Random();

SortedList<int, int> TestObject = new SortedList<int, int>();

for (int i = 1; i <= 1000000; i++)

{

TestObject.Add(i, ra.Next());

}

其中，ra.Next()用來生成隨機數。

上述代碼執行速度相當快，因為插入的數據的Key值是有序的。

如果把i換成1000000-i，則速度立刻慢得慘不忍睹。

同樣的情況出現在把i替換成隨機數。在一段時間的等待后出錯，因為Key值不能重復。

這樣說來，SortedList<TKey, TValue>不太像二叉樹結構.

SortedList<TKey, TValue>還有一個功能，就是直接訪問Key值大小排名為k的Key 和Value。

方法(使用屬性)是object.Key[k]和object.Value[k)。

這更加印證了網上的說法.

我認為SortedList沒什么用 - 除非是對基本有序的數據，或者對內存非常吝嗇。如果僅僅需要在BST上加上查找排名為k的節點的功能，可以使用一個經典算法：在每個節點上加上一個leftsize，儲存它左子樹的大小。

2. 功能

這三個類的功能上面都講得差不多了。因為實現就決定了功能。這里小結一下。

Dictionary<TKey, TValue>的功能:

Add，Clear，ContainsKey，ContainsValue，Count（屬性），Enumerator(無序)，Item(屬性)， Remove

SortedDictionary<TKey, TValue>新增的功能：

Enumerator為有序 - 對應BST的中序遍歷。

SortedList<TKey, TValue>新增的功能:

Capacity(屬性) - 畢竟人家是數組

IndexOfKey，IndexOfValue(返回Value對應Key的排名而不是 Value 的排名)

Keys[k]，Values[k] - 返回按照Key排序的數組的第k個元素

3. 速度

實踐出真知 - 某名人。

理論和實踐不符就是錯的 - Thity。

我們的測試程序:

CODE:

static class DictionarySpeedTest

{

static Random RandomGenerator = new Random();

static List<Key_N_Data> ArrayListData = new List<Key_N_Data>();

static Dictionary<long, long> TestObject = new Dictionary<long, long>();

public struct Key_N_Data

{

public long Key;

public long Data;

}

const int ITEM_COUNT = 1000000;

const int TEST_COUNT = 500000;

static long LastTick;

public static void TimerStart(string Text)

{

Console.Write(Text);

LastTick = DateTime.Now.Ticks;

}

public static void TimerEnd()

{

long t = DateTime.Now.Ticks - LastTick;

Console.WriteLine(((t) / 10000).ToString() + " ms");

}

public static void Main()

{

Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;

Console.WriteLine(TestObject.GetType().ToString());

TimerStart("Generating data... ");

for (int i = 1; i <= ITEM_COUNT; i++)

{

Key_N_Data ThisKeyData = default(Key_N_Data);

ThisKeyData.Key = ((long)RandomGenerator.Next() << 31) | RandomGenerator.Next();

ThisKeyData.Data = ((long)RandomGenerator.Next() << 31) | RandomGenerator.Next();

ArrayListData.Add(ThisKeyData);

}

TimerEnd();

TimerStart("Test 1: add data test... ");

foreach (Key_N_Data Item in ArrayListData)

{

TestObject.Add(Item.Key, Item.Data);

}

TimerEnd();

TimerStart("Test 2: find data test... ");

for (int i = 1; i <= TEST_COUNT; i++)

{

{

if (TestObject[ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Key] != ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Data)

Console.WriteLine("Error!");

}

}

TimerEnd();

TimerStart("Test 3: remove data test...");

for (int i = 1; i <= TEST_COUNT; i++)

{

TestObject.Remove(ArrayListData[RandomGenerator.Next(0, ITEM_COUNT)].Key);

}

TimerEnd();

Console.Read();

}

}

通過更改TestObject的類型，我們可以很方便地比較這三個類的速度。測試結果：

                  ADD    FIND   REMOVE

Dictionary<TKey, TValue>       265ms  203ms  187ms

SortedDictionary<TKey, TValue> 1843ms 828ms  1234ms

SortedList<TKey, TValue>       N/A

我們把ITEM_COUNT和TEST_COUNT都減小10倍：

                  ADD    FIND   REMOVE

Dictionary<TKey,TValue>       15ms   31ms   15ms

SortedDictionary<TKey,TValue> 93ms   46ms   38ms

SortedList<TKey,TValue>       8031ms 15ms   6046ms

SortedList<TKey,TValue>的隨機查找居然比Dictionary<TKey,TValue>和SortedDictionary<TKey,TValue>(Hashtable和BST)還要快。這樣說來，SortedList<TKey,TValue>似乎又不是簡單的數組了。(不過我仍然覺得它沒什么用)

4. 小結

如果只是當作索引使用，請用Dictionary<TKey,TValue>。

如果需要查找最小的幾個元素，或者需要按順序遍歷元素，就用SortedDictionary<TKey,TValue>。

如果輸入/刪除的元素是基本增序的，或者訪問次數遠多于修改次數，或者需要訪問第k大的元素，或者對內存吝嗇得BT的情況，用SortedList<TKey,TValue>吧。(它居然成使用情況最多的了... orz)

PS: 微軟似乎也很吝嗇，SortedDictionary<TKey,TValue>居然只支持增序(默認的比較器)，如果要降序的話，我們得自己寫一個比較器。

CODE:

class MyComparer : Comparer<long>

{

public override int Compare(long x, long y)

{

return Comparer<long>.Default.Compare(y, x);

}

}

使用：

SortedList<long, long> TestObject = new SortedList<long, long>(new MyComparer());

現在我們可以來進行一下剛開始的時候提到的Dictionary<TKey,TValue>（泛型）vs Hashtable（非泛型）對決。

結果：

ADD   FIND  REMOVE

Dictionary(Of Long, Long)     271ms 203ms 187ms

Dictionary(Of Object, Object) 468ms 312ms 234ms

Hashtable                         859ms 390ms 218ms

結論: 最好用Dictionary代替Hashtable。