About a dictionary, removing and adding items, and their order.

I had a weird problem today using a Dictionary. The process involved removing and adding data, and then printing the data. I assumed that it was ordered. I was wrong! Let me show you:

var dictionary = new Dictionary<int, string>();

dictionary.Add(5, "The");
dictionary.Add(7, "quick");
dictionary.Add(31, "brown");
dictionary.Add(145, "fox");

dictionary.Remove(7); // remove the "quick" entry

After a while I added another line to the dictionary:

dictionary.Add(423, "jumps");

While printing this data I discovered an oddity.

dictionary
    .ToList()
    .ForEach(e => Console.WriteLine("{0} => {1}", e.Key, e.Value));

What do you expect the output of this to be?

5 => The
31 => brown
145 => fox
423 => jumps

However the actual result was this:

5 => The
423 => jumps
31 => brown
145 => fox

The documentation tells us the following:

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey, TValue> structure representing a value and its key. The order in which the items are returned is undefined.

Interested in the actual behavior I looked at the source code of Dictionary here.

If you look closely, first at Remove and then to Add (and subsequently Insert) you can see that when you remove an item it holds a reference (in freelist) to the free ‘entry’.

What’s more weird is the behavior when you delete 2 entries, and then add 2 others:

var dictionary = new Dictionary<int, string>();

dictionary.Add(5, "The");
dictionary.Add(7, "quick");
dictionary.Add(31, "brown");
dictionary.Add(145, "fox");

dictionary.Remove(7); // remove the "quick" entry
dictionary.Remove(31); // also remove the "brown" entry

dictionary.Add(423, "jumps");
dictionary.Add(534, "high");

dictionary
    .ToList()
    .ForEach(e => Console.WriteLine("{0} => {1}", e.Key, e.Value));

Which yields:

5 => The
534 => high
423 => jumps
145 => fox

But for that you’ll need to look at line 340 and further!

So what have we learned? It’s not ordered until MSDN tells you!

Have a good one!