C＃：使用〜O（1）查找密鑰的字典排序

未找到對此的答案。C＃：使用〜O（1）查找密鑰的字典排序

我喜歡KeyedCollection，因爲它保留了插入順序並具有〜O（1）鍵查找時間。

現在我正在尋找一種類似的類型，它將按鍵而不是插入順序排序。

SortedDictionary確實如此，但是實現與我想要的完全相反。插入是O（1），查找O（log n）。但是，我想查找〜O（1）（例如哈希表），並且插入可以是O（log n）（二叉樹？）。

這是存在嗎？應該不難實現明智...

感謝

來源

2011-04-08 Cookie

至於第三方，C5通用集合庫有一個散列鏈表，它接近，但我不得不重新實現插入以維持順序。而tbh，一棵散亂的樹會更好。將繼續尋找，但這有點令人沮喪。 – Cookie 2011-04-11 08:13:49

有位於提供什麼.NET BCL沒有數據結構您正在尋找。也許有第三方解決方案。

在大多數情況下，O（log n）就足夠了。如果您嘗試實現自己的數據結構，則可能會進行微優化。

但是，最快捷的方法可能是簡單地聲明一個既有Dictionary又有SortedDictionary爲私有成員的新類。對於所有讀取方法，您可以選擇更高效的字典來返回值。對於所有的寫入方法，你會處理兩個內部字典，並小心他們會保持同步。儘管這可能不是最有效的方法。但是如果你想在這裏優化，你必須重新實現散列表的大部分功能。

來源

2011-04-08 11:22:21 herzmeister

如果它沒有實現，我不想從頭開始做，最後的方法似乎是一個很好的性能改進。但是，刪除仍然是log（n）。理想情況下，您希望Dictionary能夠指向SortedDictionary的樹成員以進行快速刪除。然而，這將會以更長的查找爲代價，因爲您必須遵循兩個引用。至於這是否是微型優化，當然這取決於手頭的問題？我認爲很多人不會考慮選擇合適的數據結構來解決微觀優化問題。 – Cookie 2011-04-11 07:27:24

我想OrderedBag可能是你想要什麼：

Frequent inserts into sorted collection

來源

2011-04-08 11:20:19 sehe

OrderedBag實際上具有類似於更差的性能和開銷，因爲它可以包含具有相同值的多個鍵。儘管如此，OrderedSet似乎是答案。從我目前可以看出的。謝謝！ – Cookie 2011-04-11 07:23:15

編輯 - OrderedSet沒有密鑰查找，所以不起作用。 – Cookie 2011-04-11 07:37:29

SortedList？我沒有進一步研究這個，但因爲你顯然已經閱讀了其餘的...... :) – sehe 2011-04-11 07:40:04

C＃：使用〜O（1）查找密鑰的字典排序

回答

相關問題