如何实现c＃/。net 3.5字典？ [英] How is the c#/.net 3.5 dictionary implemented?

问题描述

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

解决方案

使用反射器，我发现以下内容：The Dictionary将数据保存在一个struct数组中。它会保留该数组中剩余空白位置的数量。当您添加一个项目并且没有空的位置时，它会增加内部数组的大小（见下文），并将数据从旧数组复制到新数组。

所以我建议你应该使用你设置初始大小的构造函数，如果你知道将有很多条目。

编辑：逻辑实际上很有趣：有一个称为 HashHelpers 的内部类来找到素数。为了加快速度，它还将静态数组中存储了一些素数从3到7199369（有些缺少;原因如下）。当您提供容量时，它会从数组中找到下一个素数（相同或更大），并将其用作初始容量。如果你给它的数字大于其数组，它将开始手动检查。

所以如果没有任何东西作为字典的容量传递，起始容量是三。 / p>

一旦容量超过，它将当前容量乘以2，然后使用助手类查找下一个较大的素数。这就是为什么在数组中并不是每一个素材都是必需的，因为素材太靠近在一起并不是真的需要。

所以如果我们没有传递初始值， get（我检查了内部数组）：

1. 3


2. 7


3. 17


4. 37


5. 71


6. 163




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. 
    
21. 4999559

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

I'm using an application which uses a number of large dictionaries ( up to 10^6 elements), the size of which is unknown in advance, (though I can guess in some cases). I'm wondering how the dictionary is implemented, i.e. how bad the effect is if I don't give an initial estimate of the dictionary size. Does it internally use a (self-growing) array in the way List does? in which case letting the dictionaries grow might leave a lot of large un-referenced arrays on the LOH.

解决方案

Using Reflector, I found the following: The Dictionary keeps the data in a struct array. It keeps a count on how many empty places are left in that array. When you add an item and no empty place is left, it increases the size of the internal array (see below) and copies the data from the old array to the new array.

So I would suggest you should use the constructor in which you set the initial size if you know there will be many entries.

EDIT: The logic is actually quite interesting: There is an internal class called HashHelpers to find primes. To speed this up, it also has stored some primes in a static array from 3 up to 7199369 (some are missing; for the reason, see below). When you supply a capacity, it finds the next prime (same value or larger) from the array, and uses that as initial capacity. If you give it a larger number than in its array, it starts checking manually.

So if nothing is passed as capacity to the Dictionary, the starting capacity is three.

Once the capacity is exceeded, it multiplies the current capacity by two and then finds the next larger prime using the helper class. That is why in the array not every prime is needed, since primes "too close together" aren't really needed.

So if we pass no initial value, we would get (I checked the internal array):

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

Once we pass this size, the next step falls outside the internal array, and it will manually search for larger primes. This will be quite slow. You could initialize with 7199369 (the largest value in the array), or consider if having more than about 5 million entries in a Dictionary might mean that you should reconsider your design.

这篇关于如何实现c＃/。net 3.5字典？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！