19

I understand that a dictionary is not an ordered collection and one should not depend on the order of insertion and retrieval in a dictionary.

However, this is what I noticed:

  • Added 20 key value pairs to a Dictionary
  • Retrieved them by doing a foreach(KeyValuePair...)

The order of retrieval was same as the order in which they were added. Tested for around 16 key value pairs.

Is this by design?

101100
  • 2,666
  • 23
  • 28
SharePoint Newbie
  • 5,974
  • 12
  • 62
  • 103

7 Answers7

33

It's by coincidence, although predictably so. You absolutely shouldn't rely on it. Usually it will happen for simple situations, but if you start deleting elements and replacing them with anything either with the same hash code or just getting in the same bucket, that element will take the position of the original, despite having been added later than others.

It's relatively fiddly to reproduce this, but I managed to do it a while ago for another question:

using System;
using System.Collections.Generic;

class Test
{
    static void Main(string[] args)
    {
        var dict = new Dictionary<int, int>();        
        dict.Add(0, 0);
        dict.Add(1, 1);
        dict.Add(2, 2);
        dict.Remove(0);
        dict.Add(10, 10);

        foreach (var entry in dict)
        {
            Console.WriteLine(entry.Key);
        }
    }
}

The results show 10, 1, 2 rather than 1, 2, 10.

Note that even though it looks like the current behaviour will always yield elements in insertion order if you don't perform any deletions, there's no guarantee that future implementations will do the same... so even in the restricted case where you know you won't delete anything, please don't rely on this.

Community
  • 1
  • 1
Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • 4
    +1 - this example helped me to reproduce the behaviour in my scenario so I could "see" it in action, helping me to avoid potential pitfalls. – AdaTheDev Apr 13 '10 at 12:28
  • I asked a somewhat related question [here](https://stackoverflow.com/questions/62928377/immutabledictionary-enumeration-order) with a snippet of code which exhibits the non-deterministic nature of enumeration for `ImmutableDictionary` when using `String` as a key in .NET Core 3.1. This provides an example where the now _current_ behaviour does not yield elements in insertion order (albeit for `ImmutableDictionary`). – anthls Jul 17 '20 at 02:10
22

From MSDN:

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.

[Emphasis added]

Richard
  • 106,783
  • 21
  • 203
  • 265
heijp06
  • 11,558
  • 1
  • 40
  • 60
4

If you want to iterate through a Dictionary in a fixed order you could try OrderedDictionary

Yannick Motton
  • 34,761
  • 4
  • 39
  • 55
3

It is by design that the Dictionary<TKey,TValue> is not an ordered structure as it is intended to be used primarily more for key-based access.

If you have the need to retrieve items in a specific order, you should take a look at the Sorted Dictionary<TKey, TValue>, which takes a Comparer<T> that will be used to sort the keys in the Sorted Dictionary<TKey, TValue>.

Cristian Ciupitu
  • 20,270
  • 7
  • 50
  • 76
Russ Cam
  • 124,184
  • 33
  • 204
  • 266
  • I think you may have misread the question. He's asking whether the fact that he *is* seeing the results in order is by design. – Jon Skeet Sep 21 '09 at 08:03
  • thanks Jon, I meant the fact that the dictionary is not an ordered structure is by design. I'll better clarify my answer (it can be tricky answering on an iPhone on the train :) ) – Russ Cam Sep 21 '09 at 08:17
  • @Russ: Yes - I realised what you were saying, but it's not answering the "is it by design" question which was asked :) – Jon Skeet Sep 21 '09 at 08:34
2

Is this by design? It probably wasn't in the original .Net Framework 2.0, but now there is an implicit contract that they will be ordered in the same order as added, because to change this would break so much code that relies on the behaviour of the original generic dictionary. Compare with the Go language, where their map deliberately returns a random ordering to prevent users of maps from relying on any ordering [1].

Any improvements or changes the framework writers make to Dictionary<T,V> would have to keep that implicit contract.

[1] "Since the release of Go 1.0, the runtime has randomized map iteration order. ", https://blog.golang.org/go-maps-in-action .

kristianp
  • 5,496
  • 37
  • 56
  • Could you share some documentation or article where I may read more about the default contract preserving the insert order, please? I couldn't find anything. – David Ferenczy Rogožan Nov 25 '19 at 20:29
  • There's no contract that says it preserves order. In fact ordering breaks down when there are deletions, as per Jon Skeet's answer. I'm just opining that the current behaviour is unlikely to change. – kristianp Nov 26 '19 at 21:33
0

I don't think so, the dictionary does not grantee the internal ordering of items inside it. If you need to keep the order as well, use additional data structure (array or list) along with the dictionary.

Dror Helper
  • 30,292
  • 15
  • 80
  • 129
0

I believe enumerating a Dictionary<K,V> will return the keys in the same order they were inserted if all the keys hash to the same value. This is because the Dictionary<K,V> implementation uses the hash code of the key object to insert key/value pairs into buckets, and the values are (usually) stored in the buckets in the order they are inserted. If you are consistently seeing this behavior with your user-defined objects, then perhaps you have not (correctly) overridden the GetHashCode() method?

Daniel Pryden
  • 59,486
  • 16
  • 97
  • 135