Dictionary<TKey,TValue>、SortedDictionary<TKey,TValue>與 SortedList<TKey,TValue>是.NET Framework的三個(gè)泛型的關(guān)鍵字查找的類(lèi)，都屬于System.Collections.Generic命名空間。它們無(wú)論是名字還是功能都十分相似，以至于實(shí)際運用的時(shí)候我們會(huì )經(jīng)?；煜?。因此有必要比較一下它們。
1. 實(shí)現
查閱 MSDN 得到如下資料:
Dictionary<TKey, TValue>泛型類(lèi)提供了從一組鍵到一組值的映射。字典中的每個(gè)添加項都由一個(gè)值及其相關(guān)聯(lián)的鍵組成。通過(guò)鍵來(lái)檢索值的速度是非?？斓?，接近于O(1)，這是因為Dictionary<TKey, TValue>類(lèi)是作為一個(gè)哈希表來(lái)實(shí)現的。
檢索速度取決于為TKey指定的類(lèi)型的哈希算法的質(zhì)量。
可見(jiàn)，Dictionary<TKey, TValue>基本上就是一個(gè)Hashtable。不過(guò)它比Hashtable類(lèi)快，因為它支持泛型~(稍后我們會(huì )用實(shí)驗證明，即使使用Object類(lèi)型的Dictionary也比 Hashtable稍快)。
SortedDictionary<TKey, TValue>泛型類(lèi)是檢索運算復雜度為O(log n)的二叉搜索樹(shù)，其中n是字典中的元素數。就這一點(diǎn)而言，它與SortedList<TKey, TValue>泛型類(lèi)相似。這兩個(gè)類(lèi)具有相似的對象模型，并且都具有O(log n)的檢索運算復雜度。這兩個(gè)類(lèi)的區別在于內存的使用以及插入和移除元素的速度。
SortedList<TKey, TValue>使用的內存比SortedDictionary<TKey, TValue>少。
SortedDictionary<TKey, TValue>可對未排序的數據執行更快的插入和移除操作：它的時(shí)間復雜度為O(log n)，而SortedList<TKey, TValue>為O(n)。
如果使用排序數據一次性填充列表，則SortedList<TKey, TValue>比 SortedDictionary<TKey, TValue>快。
每個(gè)鍵/值對都可以作為KeyValuePair<TKey, TValue>結構進(jìn)行檢索，或作為 DictionaryEntry通過(guò)非泛型IDictionary接口進(jìn)行檢索。
只要鍵用作SortedDictionary<TKey, TValue>中的鍵，它們就必須是不可變的。SortedDictionary<TKey, TValue>中的每個(gè)鍵必須是唯一的。鍵不能為 null引用），但是如果值類(lèi)型TValue為引用類(lèi)型，該值則可以為空。
SortedDictionary<TKey, TValue>需要比較器實(shí)現來(lái)執行鍵比較?？梢允褂靡粋€(gè)接受 comparer參數的構造函數來(lái)指定IComparer<T>泛型接口的實(shí)現；如果不指定實(shí)現，則使用默認的泛型比較器Comparer<T>。如果類(lèi)型TKey實(shí)現IComparable<T>泛型接口，則默認比較器使用該實(shí)現。
C#語(yǔ)言的foreach語(yǔ)句需要集合中每個(gè)元素的類(lèi)型。由于SortedDictionary<TKey, TValue>的每個(gè)元素都是一個(gè)鍵/值對，因此元素類(lèi)型既不是鍵的類(lèi)型，也不是值的類(lèi)型。而是KeyValuePair<TKey, TValue>類(lèi)型。
可見(jiàn)，SortedDictionary<TKey, TValue>類(lèi)似一個(gè)平衡二叉查找樹(shù)(AVL)。既然是 BST，我們當然可以對其進(jìn)行中序遍歷。有兩種方法:
1. foreach
2. Object.GetEnumerator
小實(shí)驗:
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>類(lèi)和SortedList<TKey, TValue>類(lèi)之間的另一個(gè)區別是：SortedList<TKey, TValue>支持通過(guò)由Keys和Values屬性返回的集合對鍵和值執行高效的索引檢索。訪(fǎng)問(wèn)此屬性時(shí)無(wú)需重新生成列表，因為列表只是鍵和值的內部數組的包裝。
QUOTE:
二叉樹(shù)的插入操作怎么是 O(n)?
網(wǎng)上有一種說(shuō)法, 就是SortedList<TKey, TValue>內部就是兩個(gè)數組, 插入的時(shí)候類(lèi)似O(n^2)的插入排序(每個(gè)動(dòng)作為O(n))，不過(guò)插入有序數據特別快(每個(gè)動(dòng)作變成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()用來(lái)生成隨機數。
上述代碼執行速度相當快，因為插入的數據的Key值是有序的。
如果把i換成1000000-i，則速度立刻慢得慘不忍睹。
同樣的情況出現在把i替換成隨機數。在一段時(shí)間的等待后出錯，因為Key值不能重復。
這樣說(shuō)來(lái)，SortedList<TKey, TValue>不太像二叉樹(shù)結構.
SortedList<TKey, TValue>還有一個(gè)功能，就是直接訪(fǎng)問(wèn)Key值大小排名為k的Key 和Value。
方法(使用屬性)是object.Key[k]和object.Value[k)。
這更加印證了網(wǎng)上的說(shuō)法.
我認為SortedList沒(méi)什么用 - 除非是對基本有序的數據，或者對內存非常吝嗇。如果僅僅需要在BST上加上查找排名為k的節點(diǎn)的功能，可以使用一個(gè)經(jīng)典算法：在每個(gè)節點(diǎn)上加上一個(gè)leftsize，儲存它左子樹(shù)的大小。
2. 功能
這三個(gè)類(lèi)的功能上面都講得差不多了。因為實(shí)現就決定了功能。這里小結一下。
Dictionary<TKey, TValue>的功能:
Add，Clear，ContainsKey，ContainsValue，Count（屬性），Enumerator(無(wú)序)，Item(屬性)， Remove
SortedDictionary<TKey, TValue>新增的功能：
Enumerator為有序 - 對應BST的中序遍歷。
SortedList<TKey, TValue>新增的功能:
Capacity(屬性) - 畢竟人家是數組
IndexOfKey，IndexOfValue(返回Value對應Key的排名而不是 Value 的排名)
Keys[k]，Values[k] - 返回按照Key排序的數組的第k個(gè)元素
3. 速度
實(shí)踐出真知 - 某名人。
理論和實(shí)踐不符就是錯的 - 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();
}
}
通過(guò)更改TestObject的類(lèi)型，我們可以很方便地比較這三個(gè)類(lèi)的速度。測試結果：
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)還要快。這樣說(shuō)來(lái)，SortedList<TKey,TValue>似乎又不是簡(jiǎn)單的數組了。(不過(guò)我仍然覺(jué)得它沒(méi)什么用)
4. 小結
如果只是當作索引使用，請用Dictionary<TKey,TValue>。
如果需要查找最小的幾個(gè)元素，或者需要按順序遍歷元素，就用SortedDictionary<TKey,TValue>。
如果輸入/刪除的元素是基本增序的，或者訪(fǎng)問(wèn)次數遠多于修改次數，或者需要訪(fǎng)問(wèn)第k大的元素，或者對內存吝嗇得BT的情況，用SortedList<TKey,TValue>吧。(它居然成使用情況最多的了... orz)
PS: 微軟似乎也很吝嗇，SortedDictionary<TKey,TValue>居然只支持增序(默認的比較器)，如果要降序的話(huà)，我們得自己寫(xiě)一個(gè)比較器。
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());
現在我們可以來(lái)進(jìn)行一下剛開(kāi)始的時(shí)候提到的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。
聯(lián)系客服
