Is the dictionary order the same if it has exactly the same content?

Question

I know the dictionary order is undefined, MSDN says this:

For enumeration purposes, each element in the dictionary is considered as a KeyValuePair structure representing the value and its key. The return order of the elements is undefined.

Thats fine, but if I have two copies of the dictionary, each with the same content, will the order be the same?

I assume that since, as I understand it, the order is determined by the hash of the keys, and if two dictionaries have the same keys, they have the same hashes and, therefore, the same order ...

... Right?

Thanks!

Andy.

Answer 1

No, this does not guarantee that the order will be the same. Imagine a scenario where you had several elements in a Dictionary<TKey, TValue> with the same hash code. If they are added to two dictionaries in different orders, this will lead to different orders in the enumeration.

Consider, for example, the following code (corresponding to equality)

 class Example { public char Value; public override int GetHashCode() { return 1; } public override bool Equals(object obj) { return obj is Example && ((Example)obj).Value == Value; } public override string ToString() { return Value.ToString(); } } class Program { static void Main(string[] args) { var e1 = new Example() { Value = 'a' }; var e2 = new Example() { Value = 'b' }; var map1 = new Dictionary<Example, string>(); map1.Add(e1, "1"); map1.Add(e2, "2"); var map2 = new Dictionary<Example, string>(); map2.Add(e2, "2"); map2.Add(e1, "1"); Console.WriteLine(map1.Values.Aggregate((x, y) => x + y)); Console.WriteLine(map2.Values.Aggregate((x, y) => x + y)); } } 

The result of starting this program is

 12 21 

Answer 2

Short version: None.

Long version:

  [TestMethod] public void TestDictionary() { Dictionary<String, Int32> d1 = new Dictionary<string, int>(); Dictionary<String, Int32> d2 = new Dictionary<string, int>(); d1.Add("555", 1); d1.Add("abc2", 2); d1.Add("abc3", 3); d1.Remove("abc2"); d1.Add("abc2", 2); d1.Add("556", 1); d2.Add("555", 1); d2.Add("556", 1); d2.Add("abc2", 2); d2.Add("abc3", 3); foreach (var i in d1) { Console.WriteLine(i); } Console.WriteLine(); foreach (var i in d2) { Console.WriteLine(i); } } 

Output:

 [555, 1] [abc2, 2] [abc3, 3] [556, 1] [555, 1] [556, 1] [abc2, 2] [abc3, 3] 

Answer 3

If MSDN talks about its undefined, you should rely on it. The thing with undefined is that the implementation of the dictionary allows you to store it in any order. This means that the programmer should never make any assumptions about the order. I would suggest that personally, without looking that the order of the elements in the dictionary would depend on the order in which they entered, but I could be wrong. Whatever the answer, if you want some kind of behavior, when the order is the same for both, you are doing it wrong.

Answer 4

"if two dictionaries have the same keys, they have the same hashes and therefore the same order ..."

I do not think so. Even if this may be true, I would not rely on it. If true, this is an implementation detail that can change or be different with different CLR or BCL implementations (Mono comes to mind).

Implementing the Microsoft Dictionary is a bit complicated, but looking at the code for 5 minutes, I’m ready to guess that the sequence of enumerations will be based on how the dictionary received its current state, including the number of changes and the insertion order.

Answer 5

If the specification says that the order is "undefined", you cannot depend on the order without explicitly ordering it. The main implementation can be changed at any time with the new version or service pack, only for starters. Your dictionary can be taken from any number of specific implementations.

And the underlying implementation may be sensitive to the order of operations applied. Adding the keys "a", "b" and "c" in this order may lead to a different data structure than adding the same set of keys in a different order (for example, "b", "c" and "a",) . Deletions can also affect the data structure.

A direct binary tree, for example, if it is used as a data structure behind a dictionary, if keys are added in order, the result is a very unbalanced tree, which is essentially a linked list. The tree will be more balanced if the nodes are inserted at random.

And some morphological data structures are implemented. If, for example, a dictionary is implemented with a basic data structure that is a red / black tree, the tree nodes will be split / rotated to save the tree as insert and delete. Thus, the actual data structure is highly dependent on the order of operations, even if the final content is the same.

Answer 6

I do not know the specifics of the Microsoft implementation, but in general, your assumption is satisfied only if the dictionary does not have two elements whose hash has the same value or if those entries that collide with each other are added in the same order.