为什么没有Dictionary.TrimExcess()？

Question

在.NET中,有一个构造函数Dictionary<TKey, TValue>需要一个参数,int capacity.这是一样的许多其他收藏品,如List<T>,Queue<T>和Stack<T>; 此外,根据MSDN文档:

Dictionary的容量是在需要调整大小之前可以添加到Dictionary的元素数.当元素添加到Dictionary时,通过重新分配内部数组,容量会根据需要自动增加.

这听起来和其他集合一样List<T>,等等.由于这些集合在必要时具有自动调整大小的行为,因此可能具有比所需更大的容量,因此大多数集合都具有一种TrimExcess方法.如果您一次向集合添加未知数量的项目,那么这将非常方便,之后您将不会添加任何其他项目.

为什么没有Dictionary<TKey, TValue>这个相同的TrimExcess方法？

(免责声明:我非常熟悉"默认情况下不存在的功能"的响应;我想我大多只是想知道是否有一个特殊的原因,为什么TrimExcess一个Dictionary没有意义,或为什么它会更加困难到实现比简单的集合,如List.)

Answer 1

到 2019 年，.Net Standard 2.1+ 和 .Net Core 2.1+ 实现Dictionary<TKey, TValue>.TrimExcess()：

请参阅：https : //docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.trimexcess?view=netstandard-2.1

.Net Framework 没有在任何版本中实现它。

Answer 2

我想在这种情况下,capacity参数有助于定义散列函数以及桶的数量; 调整稀疏的数据集的大小/修整将需要重新计算剩余的所有存储项的哈希值.

Answer 3

这部分是猜测:字典被"排序"为哈希表.保留的容量不仅仅是字典顶部的一堆空闲内存地址.相反,它包含整个字典中的空房间.这样做是为了使添加/移动/移除等非常有效.如果您有一个TrimExcessDictionary 的方法,整个Dictionary必须将所有内容复制到一个新位置,而元素之间没有任何间隙.

实际上:差距应该保留,否则哈希表的好处变得无效,修剪(TrimExcess),如果实现,应该只修剪内部ValueCollection.

更新:扩展并更改了我选择不当的单词
更新: BCL团队表示TrimExcess for Dictionaries"可能很有用".
更新:功能请求已解决为无法修复:"不幸的是,我们无法在下一版本的.NET中使用此功能,因此我将解决此问题,因为无法修复."

Answer 4

每个 MSDN 词典都是作为哈希表实现的。如果你修剪了多余的部分，你将不得不想出一个算法，该算法仍然提供接近 O(1) 的查找时间，而这实际上是一个随机排序的列表。