c#/.net 3.5 字典是如何实现的？

Question

我正在使用一个应用程序，该应用程序使用许多大型字典（最多 10^6 个元素），其大小事先未知（尽管在某些情况下我可以猜测）。我想知道字典是如何实现的，即如果我不给出字典大小的初始估计，效果会有多糟糕。它在内部是否像 List 那样使用（自增长）数组？在这种情况下，让字典增长可能会在 LOH 上留下大量未引用的大型数组。

Answer 1

使用Reflector，我发现了以下内容：字典将数据保存在结构体数组中。它会记录该数组中剩余多少个空白位置。当您添加一个项目并且没有剩余空位时，它会增加内部数组的大小（见下文）并将数据从旧数组复制到新数组。

因此，如果您知道会有很多条目，我建议您应该使用设置初始大小的构造函数。

编辑：逻辑实际上非常有趣：有一个名为

HashHelpers

的内部类来查找素数。为了加快速度，它还在静态数组中存储了一些从 3 到 7199369 的素数（有些素数丢失了；原因见下文）。当您提供容量时，它会从数组中查找下一个素数（相同值或更大），并将其用作初始容量。如果你给它的数字比数组中的数字大，它就会开始手动检查。

因此，如果没有任何内容作为容量传递给字典，则起始容量为 3。

一旦超出容量，它将当前容量乘以二，然后使用辅助类找到下一个更大的素数。这就是为什么在数组中不需要每个素数，因为“太靠近”的素数并不是真正需要的。

因此，如果我们不传递初始值，我们会得到（我检查了内部数组）：

1. 3
2. 7
3. 17
4. 37
5. 71
6. 163
7. 353
8. 761
9. 1597
10. 3371
11. 7013
12. 14591
13. 30293
14. 62851
15. 130363
16. 270371
17. 560689
18. 1162687
19. 2411033
20. 4999559

一旦我们超过了这个大小，下一步就会落在内部数组之外，它将手动搜索更大的素数。这会很慢。您可以使用 7199369（数组中的最大值）进行初始化，或者考虑字典中的条目是否超过 500 万个可能意味着您应该重新考虑您的设计。

Answer 2

MSDN 说：“使用键检索值非常快，接近 O(1)，因为 Dictionary 类是作为哈希表实现的。”并进一步说明“通过重新分配内部阵列，容量会根据需要自动增加。”

但是如果您给出初步估计，您获得的重新分配就会减少。如果您从一开始就拥有所有项目，那么 LINQ 方法 ToDictionary 可能会很方便。

Answer 3

哈希表通常有一个称为负载因子的东西，如果达到此阈值，它将增加后备存储桶存储。 IIRC 默认值约为 0.72。如果您有完美的散列，可以将其增加到 1.0。

此外，当哈希表需要更多存储桶时，整个集合必须重新哈希。

Answer 4

对我来说最好的方法是使用 .NET Reflector。

http://www.red-gate.com/products/reflector/

使用反汇编代码查看实现。

Answer 5

我问自己同样的事情，发现了这个非常好的链接：

C# 中的字典实现 - Dotnetos - 有关 .NET 的课程和会议

Answer 6

• JSON 作为字典

{
 "Details": 
    { 
    "ApiKey": 50125
    }
}

• 模型应包含字典类型的属性。

public Dictionary<string, string> Details{ get; set; }

• 实现数据类型为“KeyValue”的 foreach() 块

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