为什么 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()。

- Rotsor

---

@polygenelubricants：它被标记为Java和.NET，而在他的最后一句话中，OP说：“在Java中也会发生同样的情况”。 - Amadan

真正的问题是，First返回什么？由于字典使用哈希值，First是什么的第一个？ - David Brunelle

First() 返回字典中枚举时返回的第一项。这个顺序没有定义，所以你只会得到“一个项目”。 - Rotsor

Answer 1

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

它的枚举器会遍历哈希表中的桶(bucket)，直到找到一个非空的桶(bucket)，然后返回该桶(bucket)中的值。
一旦字典变得很大，这个操作就变得昂贵了。
此外，从字典中删除一个项目并不会缩小桶(bucket)数组，因此每次调用First()都会变得更慢，因为它必须循环更远才能找到一个非空的桶(bucket)。

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

---

顺便说一下，你可以像这样避免值查找：（这不会使它明显更快）

var kvp = todo.First();

//Use kvp.Key and kcp.Value

- SLaks

---

是的，您的解释是正确而完整的。 顺便说一下，Microsoft文档表示Dictionary的GetEnumerator()操作为O(1)。然而它并没有提到枚举器的MoveNext()性能。 ;) - Rotsor

Answer 2

字典不会保持键列表的记录，因此迭代器需要遍历存储桶。对于大型字典，其中许多存储桶可能没有任何内容，这需要注意。

可以比较OpenJDK的HashIterator.nextEntry和PrivateEntryIterator.nextEntry（使用TreeMap.successor）。哈希版本会遍历未知数量的条目，寻找非空条目。如果哈希表已删除许多元素（在您的情况下确实如此），则可能特别慢。在TreeMap中，我们唯一要做的是进行有序遍历。途中没有空值（只有在叶子节点处有）。

- Matthew Flaschen

---

每个返回项的摊销时间应该大致相同，无论字典的大小如何。 - Nick Johnson

@Nick：不，它不是。请看我的回答。 - SLaks

除了删除元素的边缘情况——这听起来像是.NET实现的一种弱点——填充桶的比例应该与大小无关。 - Nick Johnson

@Nick，不只是.NET的实现。Java也有此问题。C++ STL没有此问题。 - Rotsor

Answer 3

反射显示Dictionary<TKey, TValue>维护一个Entry<TKey, TValue>数组，它的KeyCollection<TKey, TValue>.Enumerator<TKey, TValue>使用。通常情况下，查找应该相对较快，因为它可以直接索引到数组中（假设您不想要排序的First）：

// Dictionary<TKey. TValue>
private Entry<TKey, TValue>[] entries;

然而，如果你要删除该数组的第一个元素，那么你需要遍历整个数组直到找到非空元素：

// Dictionary<TKey, TValue>.KeyCollection<TKey, TValue>.Enumerator<TKey, TValue>
while (this.index < this.dictionary.count) {
    if (this.dictionary.entries[this.index].hashCode >= 0) {
        this.currentKey = this.dictionary.entries[this.index].key;
        this.index++;
        return true;
    }
    this.index++;
}

当你删除记录时，位于数组 entries 前端的空白会越来越多，导致下一次检索 First 时速度变慢。

- Mark Brackett

Answer 4

哈希表并不是有序的，我猜测它在进行迭代之前需要进行某种排序，或者某种扫描，如果已经排序，它只需循环遍历即可。

- Meiscooldude

---

虽然我相信字典在后端是一棵树。 - Meiscooldude

.Net 的 Dictionary<TKey, TValue> 使用哈希表。 - SLaks

另外，对树进行删除可能会比较昂贵。 - Meiscooldude

Answer 5

不看的话，最简单的有序字典实现是将键作为排序列表（如TreeSet）和哈希组合；列表提供了顺序，字典提供了值。因此，键已经可用。哈希表没有键方便获取，因此罪魁祸首不是first，而是keys（没有任何证据，随时可测试假说 ;D）。

- Amadan

---

.Net 的 Dictionary<TKey, TValue> 使用哈希表。 - SLaks

可能吧。我是在一般情况下说话（将哈希表和字典互换使用），这适用于任何范式。在 .net 中，它们特别区分这两者的类型强制执行，但对于手头的问题并没有任何影响 - 数据结构是相同的。 - Amadan