為什麼 Dictionary.First() 這麼慢？

這不是一個真正的問題，因為我已經找到了答案，但仍然很有趣。

我一直認為，如果你正確地散列，散列表是最快的關聯容器。

但是，以下程式碼非常慢。它只執行了大約 100 萬次迭代，並且在 Core 2 CPU 上花費了 2 多分鐘的時間。

該程式碼執行以下操作：它維護todo需要處理的項目的集合。在每次迭代中，它從該集合中獲取一個項目（無論哪個項目），將其刪除，如果未處理則處理它（可能添加更多要處理的項目），然後重複此操作直到沒有要處理的項目。

罪魁禍首似乎是 Dictionary.Keys.First() 操作。

問題是為什麼慢？

Stopwatch watch = new Stopwatch();
watch.Start();

HashSet<int> processed = new HashSet<int>();
Dictionary<int, int> todo = new Dictionary<int, int>();

todo.Add(1, 1);
int iterations = 0;

int limit = 500000;
while (todo.Count > 0)
{
   iterations++;
   var key = todo.Keys.First();
   var value = todo[key];
   todo.Remove(key);
   if (!processed.Contains(key))
   {
       processed.Add(key);
       // process item here
       if (key < limit) { todo[key + 13] = value + 1; todo[key + 7] = value + 1; }
       // doesn't matter much how
   }
}
Console.WriteLine("Iterations: {0}; Time: {1}.", iterations, watch.Elapsed);

這導致：

Iterations: 923007; Time: 00:02:09.8414388.

只需將 Dictionary 更改為 SortedDictionary 即可：

Iterations: 499976; Time: 00:00:00.4451514.

速度提高 300 倍，而迭代次數減少了 2 倍。

在java中也會發生同樣的情況。用於HashMap代替Dictionary和keySet().iterator().next()代替Keys.First()。

Dictionary<TKey, TValue>維護一個雜湊表。

它的列舉器將遍歷雜湊表中的桶，直到找到一個非空桶，然後返回該桶中的值。

一旦字典變大，這個操作就會變得很昂貴。

此外，從字典中刪除項目不會縮小儲存桶數組，因此當您刪除項目時First()呼叫會變慢。（因為它必須進一步循環才能找到一個非空桶）

因此，重複呼叫First()和刪除是 O(n 2 )。

---

順便說一句，您可以避免這樣的值查找：（這不會使其明顯更快）

var kvp = todo.First();

//Use kvp.Key and kcp.Value

引用自：https://stackoverflow.com/questions/3046805