是否应该初始化.NET通用字典，其容量等于它将包含的项目数？

StackOverflow https://stackoverflow.com/questions/414109

题

如果我有100个项目存储在字典中，我应该将其初始化吗？

var myDictionary = new Dictionary<Key, Value>(100);

我的理解是.NET字典在达到给定加载时在内部自行调整大小，并且加载阈值被定义为容量的比率。

这表明如果在上面的字典中添加了100个项目，那么当添加其中一个项目时它会自行调整大小。调整字典大小是我想要避免的，因为它会影响性能并浪费内存。

散列碰撞的概率与字典中的加载成比例。因此，即使字典没有自己调整大小（并使用其所有插槽），性能也必须因这些冲突而降低。

如果您知道字典中有多少项，那么应该如何最好地决定将字典初始化的能力？

有帮助吗？

解决方案

您应该将字典容量初始化为什么取决于两个因素： （1）gethashcode函数的分布，和 （2）您需要插入多少项目。

您的哈希函数应该是随机分布的，或者应该根据您的输入集特别制定。让我们假设第一个，但如果你对第二个查找完美哈希函数感兴趣。

如果有100个要插入字典的项目，一个随机分布的哈希函数，并将容量设置为100，那么当您将第i个项目插入哈希表时，您有（i-1）/ 100个概率第i个项目在插入时会与另一个项目发生碰撞。如果要降低此碰撞概率，请增加容量。将预期容量增加一倍可以减少碰撞的几率。

此外，如果您知道要访问字典中每个项目的频率，您可能希望按照频率递减的顺序插入项目，因为您首先插入的项目平均访问速度更快。

其他提示

我做了一个快速测试，可能不科学，但如果我设置了大小，花了1.2207780秒加上一百万个项目，如果我没有给字典增加一个大小需要1.5024960秒...这似乎对我来说可以忽略不计。

这是我的测试代码，也许有人可以进行更严格的测试，但我怀疑它是否重要。

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

我认为你的问题太复杂了。如果您知道字典中有多少项，那么请务必在构造中指定。这将有助于字典在其内部数据结构中分配必要的空间，以避免重新分配和重新调整数据。

指定 Dictionary 构造函数的初始容量可提高性能，因为在ADD操作期间存储字典值的内部结构的调整大小会更少。

考虑到你为 Dictionary 构造函数指定了k的初始容量，那么：

  1. Dictionary 将保留存储k个元素所需的内存量;
  2. 对字典的QUERY性能不会受到影响，也不会更快或更慢;
  3. ADD操作不需要更多的内存分配（可能很昂贵），因此会更快。

    4. 来自 MSDN ：

      

    字典的容量（TKey，   TValue）是元素的数量   可以添加到词典中（TKey，   TValue）在调整大小之前是必要的。   随着元素被添加到   字典（TKey，TValue），容量   根据需要自动增加   通过重新分配内部数组。

         

    如果集合的大小可以   估计，指定初始   容量消除了需要   执行一些调整大小   添加元素时的操作   字典（TKey，TValue）。

是的，与使用rehashing作为解决冲突的方法的 HashTable 相反， Dictionary 将使用链接。所以，是的，使用计数是好的。对于 HashTable ，您可能希望使用 count *（1 / fillfactor）

初始尺寸只是一个建议。例如，大多数哈希表的大小都是素数或2的幂。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top