为什么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.

迭代次数减少2倍,速度提高300倍.

在java中也是如此.用来HashMap代替Dictionary和keySet().iterator().next()代替Keys.First().

Answer 1

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

它的枚举器将循环遍历哈希表中的桶,直到找到非空桶,然后返回该桶中的值.
一旦字典变大,这个操作变得昂贵.
此外,从字典中删除项目不会缩小存储桶数组,因此在删除项目时First()调用会变慢.(因为它必须进一步循环以找到非空桶)

因此,重复调用First()和删除是O(n ²).

顺便说一句,您可以避免像这样的值查找:(这不会使它显着更快)

var kvp = todo.First();

//Use kvp.Key and kcp.Value