When I iterate through a Dictionary (.NET generic data structure) will it be in the same order that I added them?

Question

I have a dictionary that I normally access with a key, so I need fast random access reads. However for one function I need to process every item in the dictionary where the order is important. It seems to be working OK in tests. Is it OK to depend on the order of items in a dictionary?

Answer 1

No. You're better off using a SortedDictionary if you want to keep your keys in an order.

Edit: Either that, or add your keys to a linked list if you want to keep track of the order you added the items.

Answer 2

No. If you need to keep an order, you should have a list of items as well. You could encapsulate all the operations you need in your own collection class, which would update both the dictionary and the list at the same time.

It's unfortunate that .NET doesn't have a dictionary which supports this itself - it's a reasonably common request - Java does, as LinkedHashMap.

Answer 3

tpower, Dictionary and SortedDictionary are very similar in that they both hold a collection of objects, accessible by a key. Where they differ is in the way they are internally built.

Dictionary is faster for insertion as far as I know, whereas SortedDictionary is built on top of a binary tree search algorithm and is faster for reading back.

In both situations though, the internal order is maintained by the key order. There is nothing to guarantee that the order you iterate through the entire collection will be the same as you inserted your items.

In this case, you may need to store both a list and a dictionary for your different requirements.

Answer 4

The documentation clearly states that "For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<(Of <(TKey, TValue>)>) structure representing a value and its key. The order in which the items are returned is undefined." but I'm not convinced.

In all the tests I performed, the items are always ordered by insertion.

I found this strange because I also tested HashMap and LinkedHashMap (in Java) and the order in the HashMap is not correct as expected but, like Jon Skeet said, the order in LinkedHashMap is.

Can anyone point a fail test with Dictionary?

Here is the code I use to test:

        IDictionary<string, int> dic = new Dictionary<string, int>(10);

        Console.WriteLine("Adding ...");
        for (int i = 0; i < 1000000; i++)
        {
            Guid guid = Guid.NewGuid();
            dic.Add(guid.ToString(), i);
        }
        Console.WriteLine("Testing ...");

        bool first = true;
        int lastItem = 0;
        foreach (var item in dic.Values)
        {
            if (first)
            {
                first = false;
            }
            else
            {
                if (lastItem != item - 1)
                {
                    Console.WriteLine("Test Failed !");
                    break;
                }

            }
            lastItem = item;
        }
        Console.WriteLine("Done.");