我正在使用一个使用大量字典(最多10 ^ 6个元素)的应用程序,其大小事先未知(尽管我可以在某些情况下猜测).我想知道字典是如何实现的,即如果我不对字典大小进行初步估计,效果有多糟糕.它是否在内部以List的方式使用(自增长)数组？在这种情况下,让字典增长可能会在LOH上留下许多大的未引用数组.
Dan*_*ose 70
使用Reflector,我发现了以下内容:Dictionary将数据保存在struct数组中.它会计算该阵列中剩余的空位数.当您添加一个项目并且没有剩下空位时,它会增加内部数组的大小(见下文)并将数据从旧数组复制到新数组.
所以我建议你应该使用你设置初始大小的构造函数,如果你知道会有很多条目.
编辑:逻辑实际上非常有趣:有一个内部类叫做HashHelpers寻找素数.为了加快速度,它还在一个静态数组中存储了一些素数,从3到7199369(有些丢失;因为,见下文).当您提供容量时,它会从阵列中找到下一个素数(相同值或更大值),并将其用作初始容量.如果给它一个比它的数组更大的数字,它会开始手动检查.
因此,如果没有任何内容作为Dictionary的容量传递,则起始容量为3.
一旦超过容量,它将当前容量乘以2,然后使用辅助类找到下一个更大的素数.这就是为什么在阵列中不需要每个素数,因为素数"太靠近"并不是真正需要的.
因此,如果我们没有传递初始值,我们会得到(我检查了内部数组):
一旦我们通过这个大小,下一步就会落在内部数组之外,它将手动搜索更大的素数.这将是非常缓慢的.您可以使用7199369(数组中的最大值)进行初始化,或者考虑字典中是否包含超过500万条目可能意味着您应该重新考虑您的设计.
MSDN说:"使用其密钥检索值非常快,接近于O(1),因为Dictionary类是作为哈希表实现的." 进一步说:"根据需要重新分配内部阵列,容量会自动增加."
但是,如果您进行初步估算,则会减少重新分配.如果您从一开始就拥有所有项目,那么LINQ方法ToDictionary可能会很方便.
| 归档时间： |
|
| 查看次数： |
21833 次 |
| 最近记录： |