C#/.NET 3.5 字典是如何实现的？

Question

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

- willem

---

使用C# 2.0进行数据结构的广泛研究 - 队列，栈和哈希表。 - mihai

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万条目是否意味着你应该重新考虑你的设计。

- Daniel Rose

---

那将是对100万个元素进行约20次重新散列。 - Albin Sunnanbo

@Dzmitry 这有点复杂。有一个桶列表，条目列表和自由条目列表。详情请参见http://www.simple-talk.com/community/blogs/simonc/archive/2011/09/16/103362.aspx。 - Daniel Rose

为什么在扩容时总是使用质数有什么意义或优势？ - mike01010

@mike 这是由于哈希表的使用方式造成的。请参考https://dev59.com/7nM_5IYBdhLWcg3w-4Zg - Daniel Rose

非常感谢，您的回答引导我检查构造函数的源代码，但有点吓人的是，当您提前提供容量时，它也会增加到质数。这意味着即使用于存储已知集合，也可能存在大量浪费的内存。 - greenoldman

Answer 2

MSDN说：“通过使用其键检索值非常快，接近O(1)，因为Dictionary类实现为哈希表。”并进一步解释说：“容量会随着需要重新分配内部数组而自动增加。”

但是如果您给出初始估计值，您将获得更少的重新分配。如果您从一开始就拥有所有项目，则可以使用LINQ方法ToDictionary。

- Albin Sunnanbo

---

ToDictionary 并不会预先分配字典的大小 - 它只是一个接一个地添加元素，直到完成。如果您事先知道（或可以猜测）字典的大小，最好自己创建一个字典并逐个添加元素。 - Zac Faragher

Answer 3

哈希表通常有一个称为负载因子的东西，如果达到该阈值，将增加后备桶存储。我记得默认值大约是0.72。如果您拥有完美的哈希，可以将其增加到1.0。

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

- leppie

Answer 4

对我来说最好的方法是使用.NET反编译器。

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

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

- Yves M.

Answer 5

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

- Dev-lop-er