data structures - Why are entries in addition order in a .Net Dictionary?

Question

I just saw this behaviour and I'm a bit surprised by it...

If I add 3 or 4 elements to a Dictionary, and then do a "For Each" to get all the keys, they appear in the same order I added them.

The reason this surprises me is that a Dictionary is supposed to be a HashTable internally, so I expected things to come out in ANY order (ordered by the hash of the key, right?)

What am I missing here? Is this a behaviour I can count on?

EDIT: OK, I thought already of many of the reasons why this might happen (like the separate list to entries, whether this is a coincidence, etc). My question is, does anyone know how this really works?

Answer 1

If you use .NET Reflector on the 3.5 class libraries you can see that the implementation of Dictionary actually stores the items in an array (which is resized as needed), and hashes indexes into that array. When getting the keys, it completely ignores the hashtable and iterates over the array of items. For this reason, you will see the behavior you have described since new items are added at the end of the array. It looks like if you do the following:

add 1
add 2
add 3
add 4
remove 2
add 5

you will get back 1 5 3 4 because it reuses empty slots.

It is important to note, like many others have, you cannot count on this behavior in future (or past) releases. If you want your dictionary to be sorted then there is a SortedDictionary class for this purpose.