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

by

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.

More Related Contents:

  1. Collection was modified; enumeration operation may not execute
  2. Merging dictionaries in C#
  3. ASP.NET MVC Binding to a dictionary
  4. Why is a Dictionary “not ordered”?
  5. Gradient Circles for Map Generator
  6. Get dictionary key by value
  7. Dictionary returning a default value if the key does not exist [duplicate]
  8. Not ableTo Serialize Dictionary with Complex key using Json.net
  9. C# dictionary – one key, many values
  10. Static Generic Class as Dictionary
  11. Two-way / bidirectional Dictionary in C#?
  12. C# String replace with dictionary
  13. Random entry from dictionary
  14. Binding DataGrid to ObservableCollection
  15. Dictionary map to an object using Automapper
  16. OrderedDictionary and Dictionary
  17. Dictionary.ContainsKey return False, but a want True
  18. Case insensitive access for generic dictionary
  19. Get dictionary value by key
  20. Different ways of adding to Dictionary
  21. Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
  22. How can I convert a class into Dictionary?
  23. How to get around lack of covariance with IReadOnlyDictionary?
  24. Argument Exception “Item with Same Key has already been added”
  25. How do I get the list of keys in a Dictionary?
  26. Composite Key Dictionary
  27. Filtering out values from a C# Generic Dictionary
  28. What benefits does dictionary initializers add over collection initializers?
  29. Convert an array to dictionary with value as index of the item and key as the item itself
  30. Hashtable to Dictionary syncroot .

Leave a Comment