這是收集或列表是最快的太多的添加和刪除？

Question

我有一個列表，其中添加大量元素&刪除每秒
我還需要在列表中同時查找元素。

此外，我需要鍵/值對比較搜索。

添加率高於刪除。

在此先感謝。

Answer 1

嘗試Dictionary。

添加，缺失和查找是非常O（1）。我不確定「搜索的鍵/值比較」是什麼意思，但Dictionary將鍵映射到值並具有快速搜索。

如果你真的需要一個列表（也就是在元素的順序），然​​後是SortedDictionary將更好地爲您服務。

Answer 2

Dictionary<TKey, TValue>通常是非常快的 - 攤銷O（1）插入和刪除。基本上它是O（1），除非它需要重構自己，在這一點上它是O（n）。

爲元素的「大量」的真正重要的插入和刪除？

鑑於Dictionary<TKey, TValue>是在某些方面的標準：「我需要一個鍵/值映射」使用.NET數據結構，我至少基準它，看它是否在看之前執行不夠好爲您的需求更深奧的東西。

不過，從你的問題「清單」引用意味着你可能需要訂購，以及 - 是實際情況或沒有？即您是否需要能夠按照添加的順序迭代條目？如果是這樣，你可能需要創建自己的(Linked)List<T>/Dictionary<TKey, TValue>組成（適當謹慎）。

雖然SortedList<TKey, TValue>和SortedDictionary<TKey, TValue>做提供有保證的排序，它不是插入排序 - 這是關鍵排序。換句話說，如果你寫：

sortedDictionary["c"] = ...; 
sortedDictionary["a"] = ...; 
sortedDictionary["b"] = ...; 

然後遍歷它，你會得到條目「a」，「b」，「c」的順序。

與你可能從他們的名字中想到的相反，這兩種類型都是真正的字典（因爲它們是鍵/值映射） - 它們只是以不同的性能特點實現。有關詳細信息，請參閱MSDN文檔。