我正在使用一个应用程序,该应用程序使用许多大型字典(最多 10^6 个元素),其大小事先未知(尽管在某些情况下我可以猜测)。我想知道字典是如何实现的,即如果我不给出字典大小的初始估计,效果会有多糟糕。它在内部是否像 List 那样使用(自增长)数组?在这种情况下,让字典增长可能会在 LOH 上留下大量未引用的大型数组。
使用Reflector,我发现了以下内容:字典将数据保存在结构体数组中。它会记录该数组中剩余多少个空白位置。当您添加一个项目并且没有剩余空位时,它会增加内部数组的大小(见下文)并将数据从旧数组复制到新数组。
因此,如果您知道会有很多条目,我建议您应该使用设置初始大小的构造函数。
编辑:逻辑实际上非常有趣:有一个名为
HashHelpers
的内部类来查找素数。为了加快速度,它还在静态数组中存储了一些从 3 到 7199369 的素数(有些素数丢失了;原因见下文)。当您提供容量时,它会从数组中查找下一个素数(相同值或更大),并将其用作初始容量。如果你给它的数字比数组中的数字大,它就会开始手动检查。
因此,如果没有任何内容作为容量传递给字典,则起始容量为 3。
一旦超出容量,它将当前容量乘以二,然后使用辅助类找到下一个更大的素数。这就是为什么在数组中不需要每个素数,因为“太靠近”的素数并不是真正需要的。
因此,如果我们不传递初始值,我们会得到(我检查了内部数组):
一旦我们超过了这个大小,下一步就会落在内部数组之外,它将手动搜索更大的素数。这会很慢。您可以使用 7199369(数组中的最大值)进行初始化,或者考虑字典中的条目是否超过 500 万个可能意味着您应该重新考虑您的设计。
MSDN 说:“使用键检索值非常快,接近 O(1),因为 Dictionary 类是作为哈希表实现的。”并进一步说明“通过重新分配内部阵列,容量会根据需要自动增加。”
但是如果您给出初步估计,您获得的重新分配就会减少。如果您从一开始就拥有所有项目,那么 LINQ 方法 ToDictionary 可能会很方便。
哈希表通常有一个称为负载因子的东西,如果达到此阈值,它将增加后备存储桶存储。 IIRC 默认值约为 0.72。如果您有完美的散列,可以将其增加到 1.0。
此外,当哈希表需要更多存储桶时,整个集合必须重新哈希。
我问自己同样的事情,发现了这个非常好的链接:
{
"Details":
{
"ApiKey": 50125
}
}
public Dictionary<string, string> Details{ get; set; }
foreach (KeyValuePair<string, string> dict in Details)
{
switch (dict.Key)
{
case nameof(settings.ApiKey):
int.TryParse(kv.Value, out int ApiKey);
settings.ApiKey=ApiKey;
break;
default:
break;
}
}