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

如果我有100个项目存储在字典中,我应该如此初始化它吗？

var myDictionary = new Dictionary(100);

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

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

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

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

1> 小智..：

---

您应该将字典容量初始化的内容取决于两个因素:(1)gethashcode函数的分布,以及(2)您必须插入多少项.

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

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

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

2> Kent Boogaar..：

---

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

3> jhunter..：

---

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

这是我的测试代码,也许有人可以做更严格的测试,但我怀疑它是否重要.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary(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();

            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();
        }

---

有趣.为了将来参考,您应该在测量这些时间时使用System.Diagnostics.Stopwatch类.DateTime.Now只能提供15ms的分辨率,但秒表的分辨率为0.01ms.