CODEWITHSUNDEEP
.netdictionaryhashtable
Tedd Hansen
Tedd Hansen

Reputation: 12326

Predicting Dictionary<> size and speed

I need to accurately calculate the size of a Dictionary for different sizes. I've tried doing some memory monitoring while running my application, but I am doing a lot of other stuff at the same time that affects the result.

How can I calculate (aprox) expected size of a Dictionary with n items? I need to know how much RAM I need in different scenarious.
By what factor does lookup time increase? O(1) ALWAYS?

I'm planning to use dictionaries for 10M+ entries, probably more.

Already consideret question for Size of a dictionary

Upvotes: 1

Views: 465

Answers (1)

Tedd Hansen
Tedd Hansen

Reputation: 12326

To answer my own question I created a small test program.

Here are the results:

  • 100 000 random lookups in a table consisting of 10 000 000 random entries takes 0,02 seconds, the table uses 200MB of RAM.

  • Memory used by a dictionary seems to be around 20-22 times for Int32 index once you get above 100 items. The ratio goes down as the dictionary gets larger.

  • Pre-allocating memory seems to cut down noticeable on insert time.

Results from Dictionary memory and speed test

Details of the test and results at http://blog.tedd.no/2011/09/26/net-dictionary-speed-and-memory/

Upvotes: 3

Related Questions