Some Creativity

Problem:

What is the output of the following piece of code going to be?

            Dictionary dict = new Dictionary();

            dict.Add("ddd", "ddd");
            dict.Add("bbb", "bbb");
            dict.Add("ccc", "ccc");
            dict.Add("aaa", "aaa");

            StringBuilder output = new StringBuilder();

            foreach (string key in dict.Keys)
            {
                output.Append(key);
                output.Append(" ");
            }

            MessageBox.Show(output.ToString());

Solution:

There are 24 ways of arranging 4 items (4! – four factorial). However the output in this case is going to be “ddd bbb ccc aaa”. Try adding a different set of keys and the keys will still be available in the Keys collection of Dictionary in the same order as the one in which you added the keys and values.

So can we rely on the order of keys in our code, and why is that happening to begin with?

According to 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 Values property.

So the short answer to the previous question is “Nope”.

To get an understanding of how hash-tables and dictionaries work in general, you can read the Wikipedia article about hash-tables. However to give a brief description, Dictionary class is implemented in .NET 2.0 by using an array of buckets. Each key is mapped to a unique bucket in this array. A separate array of entries is maintained. Each bucket merely contains the index of the corresponding slot in the entries array that contains the key that was mapped. That slot in the entries array also contains the value associated with that key (and the hashcode too, but we don’t need to worry about it for now). The enumerator that is returned to allow enumeration of keys traverses the entries array and returns keys in the order in which they are encountered. Since items in the entries array are added in the order in which you call Add in your code, keys encountered in the “foreach” are in the same order as the one in which you added them.

Since the ordering of keys is being determined by the specific way in which Dictionary was implemented in .NET 2.0, it wouldn’t be wise to rely on it in our code. That’s what MSDN said to begin with

By the way, the stuff about entries also explains why the values are returned in the same order as keys – mentioned in the MSDN documentation. It’s because the same slot in the entries array contains the value part in addition to the key.

The description of Dictionary implementation in .NET 2.0 was based on my reading of Dictionary.cs released along with the rest of .NET framework 2.0 code to everyone by Microsoft.