SortedDictionary <>或（Dictionary <> Manual Sort）

Question

當我使用SortedDictionary<>而不是Dictionary<>考慮到我需要一個有序的詞典時，性能是否受到影響，所以如果我使用了詞典，我將不得不手動排序它。哪個會更快？ SortedDictionary<>或（Dictionary<> +手動排序）。

Answer 1

插入到SortedDictionary是O（log（n）），所以插入n個項目是O（n log（n））。相反，插入到Dictionary中的是O（1），因此插入n個項目是O（n），但是您需要在使用之前對項目進行排序，即O（n log（n））。基於此，沒有太大的區別，但Dictionary具有散列的開銷，而SortedDictionary可能具有更差的內存局部性，因爲它可能實現爲鏈接結構。

SortedDictionary還對可以使用的鍵類型設置限制，因爲它需要按鍵排序，而Dictionary不使用散列。

真的，哪個更好取決於你的訪問模式，所以最好的做法是衡量你的用例的性能。

Answer 2

有一個性能問題。閱讀http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

基本上，SortedDictionary<T>是一個二叉搜索樹，而Dictionary<T>是一個哈希表。

對於插入，刪除和隨機查找，Dictionary<T>會更快。如果您按順序進行不經常修改和頻繁列表，則SortedDictionary會更快。如果您經常進行修改和隨機查找，那麼Dictionary會更快，並且很少需要對輸出進行排序。

Answer 3

這真的要取決於你如何使用字典。

• 你使用了很多物品還是不是很多物品。
• 與您需要排序時相比，您添加新項目的頻率如何。
• 你做更多的查找或插入

做的最好的事情就是做真實上下的數據有兩種方法一些性能測試，看看哪些適合你的情況更好。

Answer 4

這取決於您是否將數據添加到字典中，與獲取排序結果分開，還是一次完成。

如果您在較長時間內添加數據，您將使用SortedDictionary<>獲得每次添加的小性能打擊，但是當您最終希望得到排序結果時，您可以立即得到它。例如，如果您等待用戶輸入添加項目，這是理想的，因爲小的性能點擊並不明顯。

如果您創建一本詞典，向其中添加數據並立即獲取排序結果，則Dictionary<T>會更快，因爲它使用更快的排序算法（因爲它可以一次排序，而不是維護排序結果而物品被添加）。