Alex Rivera | Logout

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

Asked 2010-08-19T12:03:12.063
49

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.

c# dictionary
Edit
Report

1 Answer

7

MSDN says: "Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table." and further on "the capacity is automatically increased as required by reallocating the internal array."

But you get less reallocations if you give an initial estimate. If you have all items from the beginning the LINQ method ToDictionary might be handy.

answered 2010-08-19T12:09:54.623

Your Answer