.net - 为什么 Dictionary.First() 这么慢？

Question

这不是一个真正的问题，因为我已经找到了答案，但仍然很有趣。

我一直认为，如果哈希得当，哈希表是最快的关联容器。

但是，下面的代码非常慢。它仅执行大约 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().

Answer 1

Dictionary<TKey, TValue>维护一个哈希表。

它的枚举器会循环遍历哈希表中的桶，直到找到一个非空的桶，然后返回那个桶中的值。
一旦字典变大，这个操作就会变得昂贵。
此外，从字典中删除一个项目不会缩小 buckets 数组，所以 First()当您删除项目时，调用会变得变慢。 (因为它必须进一步循环才能找到一个非空的桶)

因此，反复调用First()删除是 O(n²)。

---

顺便说一句，你可以避免这样的值查找:(这不会使它明显更快)

var kvp = todo.First();

//Use kvp.Key and kcp.Value