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

A dictionary retrieves items in hashed order. The fact that they came out in insertion order was a total coincidence.

The MSDN documentation says:

The order of the keys in the KeyCollection is unspecified, but it is the same order as the associated values in the ValueCollection returned by the Values property.

Answer 2

From what I know this shouldn't be a behavior to rely on. To check it quickly use the same elements and change the order in which you add them to the dictionary. You'll see if you get them back in the order they were added, or it was just a coincidence.

Answer 3

A quote from MSDN :

The order of the keys in the Dictionary<(Of <(TKey, TValue>)>).KeyCollection is unspecified, but it is the same order as the associated values in the Dictionary<(Of <(TKey, TValue>)>).ValueCollection returned by the Dictionary<(Of <(TKey, TValue>)>).Values property.

Answer 4

What keys did you add with in your test, and in what order?

Answer 5

You cannot count on this behavior, but it's not surprising.

Consider how you would implement key iteration for a simple hash table. You would need to iterate over all the hash buckets, whether or not they had anything in them. Getting a small data set from a big hashtable could be inefficient.

Therefore it might be a good optimization to keep a separate, duplicate list of keys. Using a double-linked list you still get constant-time insert/delete. (You would keep a pointer from the hashtable bucket back to this list.) That way iterating through the list of keys depends only on the number of entries, not on the number of buckets.

Answer 6

I think this comes from the old .NET 1.1 times where you had two kinds of dictionaries "ListDictionary" and "HybridDictionary". ListDictionary was a dictionary implemented internally as an ordered list and was recommended for "small sets of entries". Then you had HybridDictionary, that was initially organized internally as a list, but if it grew bigger than a configurable threshold would become a hash table. This was done because historically proper hash-based dictionaries were considered expensive. Now a days that doesn't make much sense, but I suppose .NET just based it's new Dictionary generic class on the old HybridDictionary.

Note: Anyway, as someone else already pointed out, you should never count on the dictionary order for anything

Answer 7

Your entries might all be in the same hash bucket in the dictionary. Each bucket is probably a list of entries in the bucket. This would explain the entries coming back in order.

Answer 8

Up to a certain list size it is cheaper to just check every entry instead of hashing. That is probably what is happening.

Add 100 or 1000 items and see if they are still in the same order.

Answer 9

The question and many of the answers seem to misunderstand the purpose of a hashtable or dictionary. These data structures have no specified behaviors with respect to the enumeration of the values (or in fact the keys) of the items contained in the data structure.

The purpose of a dictionary or hashtable is to be able to efficiently lookup a specific value given a known key. The internal implementation of any dictionary or hashtable should provide for this efficiency in lookups but need not provide any specific behavior with respect to enumerations or "for each" type iterations on the values or keys.

In short, the internal data structure can store and enumerate these values in any manner that it wishes, including the order that they were inserted.

Answer 10

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.

Answer 11

I hate this kind of "by design" functionalities. I think when giving your class such a generic name as "Dictionary", it should also behave "as generally expected". For example std::map always keeps it's key-values sorted.

Edit: apparently solution is to use SortedDictionary, which behaves similarly to std::map.