Why are entries added to the .Net dictionary?

Question

I just saw this behavior, and I'm a little surprised by this ...

If I add 3 or 4 elements to the dictionary and then do “For Each” to get all the keys, they will appear in the same order as I do.

The reason that surprises me is that the dictionary should be HashTable internally, so I expected everything to come out in any order (ordered by key hash, right?)

What am I missing here? Is this behavior I can count on?

EDIT: Well, I already thought of many reasons why this could happen (for example, a separate list of entries, whether it is a coincidence, etc.). My question is: does anyone know how this works?

Answer 1

If you use .NET Reflector in 3.5 class libraries, you can see that the dictionary implementation actually stores the elements in an array (which changes as needed) and indexes the hashes into this array. When receiving keys, it completely ignores the hash table and iterates over the array of elements. For this reason, you will see the behavior you described, as new elements 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 return 1 5 3 4 because it reuses empty slots.

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

Answer 2

The dictionary retrieves items in a hashed order. The fact that they came out in the input order was a complete coincidence.

The MSDN documentation says:

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

Answer 3

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

Consider how to implement key iteration for a simple hash table. You will need to iterate over all the hash buckets, regardless of whether they have anything in them. Retrieving a small dataset from a large hash table can be inefficient.

Therefore, it can be a good optimization to maintain a separate duplicate key list. Using a double-linked list, you still get the insertion / deletion of a time constant. (You would save the pointer from the bucket of the hash table back to this list.) Thus, the repetition of the list of keys depends only on the number of records, and not on the number of buckets.

Answer 4

I think this comes from the old .NET 1.1 times, when you had two kinds of dictionaries "ListDictionary" and "HybridDictionary". ListDictionary is a dictionary implemented internally as an ordered list and recommended for "small record sets." Then you had a HybridDictionary , which was originally organized as a list, but if it became larger than a custom threshold, it became a hash table. This was done because historically correct hash-based dictionaries were considered expensive. Now are days that don't make much sense, but I suppose .NET was just basing the new Generic Dictionary class on the old HybridDictionary.

Note In any case, as someone else has already pointed out, you should never count on the order of the dictionary for anything

Answer 5

Quote from MSDN :

The order of the keys in the Dictionary <(Of <(TKey, TValue>)>). KeyCollection is indefinite, but it is the same order as the corresponding values ​​in Dictionary <(Of <(TKey, TValue>)>). ValueCollection returned by Dictionary <(Of <(TKey, TValue>)>). Property of values.

Answer 6

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

Answer 7

Your entries may be in the same hash bucket in the dictionary. Each bucket is probably a list of entries in the bucket. This explains that the records are returned in order.

Answer 8

From what I know, this should not be a behavior you can rely on. To quickly check it, use the same elements and change the order in which they are added to the dictionary. You will see if you return them in the order in which they were added, or is it just a coincidence.

Answer 9

Up to a certain list size, it’s cheaper to just check each entry instead of hashing. This is probably happening.

Add 100 or 1000 elements and see if they are all in the same order.

Answer 10

I hate such "design" functionality. I think that when you give your class a generic name such as Dictionary, it should also behave "as expected." For example, std :: map always saves the sorting of key values.

Edit: Obviously, the solution is to use a SortedDictionary, which behaves similarly to std :: map.

Answer 11

The question and many answers seem to misunderstand the purpose of the hash table or dictionary. These data structures do not have a specific behavior regarding the enumeration of the values ​​(or actually keys) of the elements contained in the data structure.

The purpose of a dictionary or hash table is to be able to efficiently search for a specific value given a known key. The internal implementation of any dictionary or hash table should provide this search efficiency, but should not provide any specific behavior regarding enumerations or iterations of the "for each" type on values ​​or keys.

In short, the internal data structure can store and list these values ​​in whatever way he wants, including the order in which they were inserted.