views:

990

answers:

11

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?

+8  A: 

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.

Brad Wilson
well, not a *total* coincidence. With a small sample I've found they usually do come out in the same order as you added them. Still, good answer!
Danimal
I don't think it was a coincidence. I did change the order of addition of the same elements to see if it'd change. So that's not what happenes. It may be that .Net will do it differently if I get a big enough amount of data.
Daniel Magliola
It's still a coincidence you shouldn't count on, if you read the documentation. Even if you dove into the code to understand why it's doing that for small numbers of keys, the # may change, and or it may never be true at all in older/newer framework versions.
Brad Wilson
It isn't a coincidence in this case, it is an implementation detail that is specifically not exposed.
Dolphin
A: 

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.

rslite
I obviously did that :-)I get them in the same order I add them, it wasn't a coincidence
Daniel Magliola
+1  A: 

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.

korchev
+1  A: 

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

Lasse V. Karlsen
+5  A: 

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.

Eric
+2  A: 

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

dguaraglia
+1  A: 

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.

Laplie
A: 

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.

Zan Lynx
The 3.5 implementation will enumerate them in order for any number of elements (Check my answer for more details).
Dolphin
A: 

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.

Yep, I agree, which is why I made the question in the first place... Given that the internal implementation doesn't care about enumeration, and given how I understand a hashtable works internally, then why is it still ordered?I understand I *shouldn't* care... I'm just very curious on what kind of implementation would give these results. (I'm just trying to learn here)
Daniel Magliola
+10  A: 

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.

Dolphin
Ding Ding Ding Ding Ding Ding Ding !!!!And the price goes to Dolphin! Yes!!Thank you, this is actually the answer I was looking for (rather than what I was getting: "You don't understand Dictionaries).Thank you for taking the time to research that.
Daniel Magliola
And as you said, in fact, removing 2 and adding 5 does give you 1 5 3 4 as the result (i tested with random strings, not just numbers). Thank you very much.
Daniel Magliola
A: 

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.

AareP