c＃/。net 3.5字典是如何实现的？
我正在使用一个应用程序，它使用了大量的大型字典（最多10 ^ 6个元素），其大小是事先未知的（尽pipe我可以猜到在某些情况下）。 我想知道字典是如何实现的，即如果我不给出字典大小的初始估计，效果会有多糟糕。 它是否以List的方式在内部使用（自增长）数组？ 在这种情况下，让字典增长可能会在LOH上留下很多大的未引用数组。
使用Reflector ，我发现以下内容：Dictionary保持数据在一个结构数组中。 它保留在该arrays中剩下多less空的位置。 当你添加一个项目，并没有空的地方，它增加了内部数组的大小（见下文），并将数据从旧数组复制到新的数组。
所以我build议你应该使用你设置的初始大小的构造函数，如果你知道会有很多条目。
编辑：逻辑其实很有趣：有一个名为HashHelpers的内部类来find素数。 为了加快速度，它也将一些素数存储在从3到7199369的静态数组中（有些缺失;因为这个原因，见下）。 当你提供一个容量时，它会从数组中find下一个素数（相同或更大的值），并将其用作初始容量。 如果给它一个比数组大的数字，它就会开始手动检查。
所以，如果没有任何东西能通过词典，起始能力是三。
一旦超过容量，它将当前容量乘以2，然后使用助手类find下一个更大的素数。 这就是为什么在arrays中不是每个素数都是需要的，因为素数“太靠近”并不是真的需要。
所以如果我们没有初始值，我们会得到（我检查了内部数组）：
- 3
- 7
- 17
- 37
- 71
- 163
- 353
- 761
- 1597
- 3371
- 7013
- 14591
- 30293
- 62851
- 130363
- 270371
- 560689
- 1162687
- 2411033
- 4999559
一旦我们超过这个尺寸，下一步就会落在内部数组之外，并且会手动search更大的素数。 这将是相当缓慢的。 您可以使用7199369（数组中的最大值）进行初始化，或者考虑在Dictionary中是否有超过500万个条目可能意味着您应该重新考虑您的devise。
MSDN说：“通过使用它的密钥检索一个值非常快，接近于O（1），因为Dictionary类是作为一个哈希表来实现的。 并进一步根据重新分配内部arrays的需要自动增加容量。
但是如果你给出初步的估计，你会减less重新分配。 如果你从头开始的所有项目，LINQ方法ToDictionary可能会很方便。
散列表通常有一个叫做加载因子的东西，如果达到这个阈值，将增加后备存储区存储。 IIRC的默认值是0.72。 如果你有完美的哈希，这可以增加到1.0。
另外，当哈希表需要更多的桶时，整个集合必须被重新组合。
