Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How is the c#/.net 3.5 dictionary implemented?

Tags:

c#

dictionary

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.

like image 985
willem Avatar asked Aug 19 '10 12:08

willem


1 Answers

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.

like image 63
Daniel Rose Avatar answered Sep 26 '22 04:09

Daniel Rose