集合类型的初始容量,例如Dictionary,List

Question

.Net中的某些集合类型具有可选的"初始容量"构造函数参数.例如:

Dictionary<string, string> something = new Dictionary<string,string>(20);

List<string> anything = new List<string>(50);

我似乎无法找到MSDN上这些对象的默认初始容量.

如果我知道我只会在字典中存储12个左右的项目,那么将初始容量设置为20就没有意义吗？

我的理由是,假设容量增长的速度与StringBuilder一样,每次容量达到时都会增加一倍,并且每次重新分配都很昂贵,为什么不预先设置你知道会保存数据的大小,还有一些额外的房间以防万一？如果初始容量是100,并且我知道我只需要十几个,那么好像其余的内存都没有分配.

Answer 1

如果没有记录默认值,原因很可能是最佳初始容量是实现细节,并且可能在框架版本之间发生变化.也就是说,您不应该编写假定某个默认值的代码.

具有容量的构造函数重载适用于您比类更了解预期的项数.例如,如果您创建了50个值的集合并且知道此数字永远不会增加,则可以初始化容量为50的集合,因此如果默认容量较低,则不必调整大小.

也就是说,您可以使用Reflector确定默认值.例如,在.NET 4.0中(也可能是以前的版本),

素数计算可能会处理哈希冲突和探测输入位置.根据内部机制,如果它们仅在每个散列中存储一个值,则它们需要二级存储位置.如果您不使用素数,则可能会找到无法插入的哈希值. (7认同)
Dictionary <T>使用链接.素数表大小可以弥补差的哈希函数.好的哈希函数产生随机分布; 在现代哈希表中使用了两种表大小的功能(.net哈希表基于Java哈希表,它也使用了素数,因为在糟糕的哈希函数的时代,这是一种旧的方式).由于Microsoft没有提供内置的散列组合方法,因此许多自制的散列函数会产生较差的分布,因此素数选择有时会补偿 - 直到散列函数产生多个素数. (6认同)

Answer 2

检查源,缺省容量两者List<T>和Dictionary<TKey, TValue>为0.

在.Net 4.5中,附加容量实际上是3.是的,默认构造函数调用容量值为0的重载构造函数,但是当构造函数调用Initialize方法时,大小设置为3.字典的实际大小通过调用HashHelpers.GetPrime(capacity)来确定,该函数返回大于提供的容量的下一个素数.因此,在.Net 4.5中,词典的初始容量为3.列表的默认容量为0,但在将第一个项目添加到列表后容量将变为4. (5认同)

Answer 3

如果你知道尺寸,那就告诉它; 在大多数"小"案例中进行小规模优化,但对更大的集合有用.如果我投入"相当多"的数据,我会主要担心这一点,因为它可以避免分配,复制和收集多个数组.

大多数收藏确实使用倍增策略.