C# Dictionary - Does adding same set of keys in the same order every time guarantees to be kept in the same order(whatever the order is) every time?

Question

By same order, I don't mean the same order the keys were added!

Say,

1) I've a dictionary d

2) I add 2, 4, 6 as my keys like

d.Add(2, "")
d.Add(4, "")
d.Add(6, "")

3) Now I access it via d.Keys property

Say, it returns keys in order 4, 2, 6

Now by same order I mean, If I keep repeating steps 2 & 3.

Will d.Keys always return the keys in same order 4, 2, 6.

Given the fact that the same set of keys(2,4,6) are added every time and in the same order!

Basically is adding keys in dictionary a deterministic process ?

I've run a few sample random cases, and it appears that Dictionary.Keys property returns the same sequence every time for the same set of keys.

But is it guaranteed ?

Sample code I tried

public static void Main(string[] args)
        {
            var rand = new Random();
            var fixedKeys = Enumerable.Range(1, 100000).Select(x => rand.Next(10000000)).Distinct().ToList();

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

            foreach (var item in fixedKeys)
            {
                dic.Add(item, "");
            }

            var fixedSequence = dic.Keys;

            for (int j = 0; j < 10; j++)
            {
                dic = new Dictionary<int, string>();

                foreach (var item in fixedKeys)
                {
                    dic.Add(item, "");
                }

                if (!dic.Keys.SequenceEqual(fixedSequence))
                {
                    Console.WriteLine("Order changed");
                }
            }
        }

even if it was implemented that way now there is no guarantee it will be that way in the future since order is not part of the abstract data type — Hogan, Dec 06 '19 at 14:54
Does this answer your question? [Does the Enumerator of a Dictionary return key value pairs in the order they were added?](https://stackoverflow.com/questions/1453190/does-the-enumerator-of-a-dictionarytkey-tvalue-return-key-value-pairs-in-the) — FeRaaC, Dec 06 '19 at 14:54
Ah, misleading title - I've read "Adding the same key" and assumed it was the same key. Apologies. — Adrian, Dec 06 '19 at 14:56
@TaW I've updated the question to make it clear, what I mean by same order — Vishal, Dec 06 '19 at 15:14
@FeRaaC No, that is a different question. I understand that the order of insertion and read is not guaranteed to be same. — Vishal, Dec 06 '19 at 15:19
I agree, this isn't a duplicate of the indicated question. This question is asking, "if I get the keys, then get them again, will they be in the same order each time?" That question asks "are the keys in the same order they were inserted?" — , Dec 06 '19 at 15:30
@vish the answers to the linked question do still apply and answer your questions. Meaning, the process of adding KeyValuePairs is deterministic, but the process is neither defined nor guaranteed (for future implementations). — FeRaaC, Dec 06 '19 at 15:37
@Amy Yes, that's what I mean, the only additional step is that I re-initialize my dictionary every time with the same set of keys before accessing the keys again — Vishal, Dec 06 '19 at 15:37

score 8 · Answer 1 · edited Jun 20 '20 at 09:12

8

From the documentation:

Remarks

The order of the keys in the Dictionary<TKey,TValue>.KeyCollection is unspecified, but it is the same order as the associated values in the Dictionary<TKey,TValue>.ValueCollection returned by the Values property.

The order of the keys is not guaranteed to be in any order.

edited Jun 20 '20 at 09:12

Community

1
1

answered Dec 06 '19 at 14:54

I've updated my question to explain what I meant by order. – Vishal Dec 06 '19 at 15:21
1

My answer doesn't change. The order of the keys is unspecified. The *current implementation* might behave a certain way, but you *cannot* depend on that behavior continuing into the future. – Dec 06 '19 at 15:22
It may be unspecified in the documentation but if you only add to the dictionary the order will be the same 100% of the time. Its when you're adding and remove that order becomes inconsistent. Like the docs say, you shouldn't count on ordering when writing your code, but the order will be the same if you are only adding regardless. – Dec 06 '19 at 15:39
@Josh `if you only add to the dictionary the order will be the same 100% of the time` That is how it is currently implemented. No such guarantees exist going forward. You cannot rely on *unspecified* behavior as if it has some kind of guarantee behind it simply because that is how it *currently* works. – Dec 06 '19 at 15:51
@josh `as if the implementation for Dictionary is ever actually going to change.` That's the point of a *guarantee*. We have no such guarantee. The word "guarantee" is defined as "a formal promise or assurance (typically in writing) that certain conditions will be fulfilled,". Do we have such a guarantee in this case? – Dec 06 '19 at 16:26

score 1 · Answer 2 · answered Dec 06 '19 at 14:54

1

No, it is not guaranteed the keys will be returned in any order.

If you require this property, you may want to look into a SortedDictionary.

answered Dec 06 '19 at 14:54

Spencer Stream

616
2
6
22

score 1 · Answer 3 · answered Dec 06 '19 at 14:54

It is not guaranteed. The Dictionary is a hashtable and its concept does not enforce the reading to be in the same order as writing. The order of elements in a dictionary is non-deterministic.

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

See https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?redirectedfrom=MSDN&view=netframework-4.8

https://stackoverflow.com/a/4007787/194717

C# Dictionary - Does adding same set of keys in the same order every time guarantees to be kept in the same order(whatever the order is) every time?

3 Answers3

Remarks

Related