Dictionary item order

Question

I use a Dictionary<string, Item> to store own items.
The reason for using a dictionary is that the keys are unique and accessing is fast.

In most cases, I use the dicionary only to access single items. But in one case I have to loop through the dictionary - here I need to have the items in order they was added.

I only know that the dictionary uses a hashtable internally, but I don't know how it is organized.

Question:
Are the items in a dictionary ordered as they are added?
What happens to the order when items are added or removed?

You can use `OrderedDictionary` in c# for ordered dictionary see MSDN: http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx — Kamil Budziewski, Aug 19 '13 at 09:04
Have a look at this great answer on the same topic. http://stackoverflow.com/questions/6384710/why-is-a-dictionary-not-ordered?rq=1 — Joseph Devlin, Aug 19 '13 at 09:07
@KingKing: `OrderedDictionary` is also implemented as HashTable(beside array) but it is ordered. However, even if i know that it's a HashTable implementation i don't necessarily have to know that it's unordered by nature. — Tim Schmelter, Aug 19 '13 at 09:24

score 4 · Accepted Answer · edited May 23 '17 at 12:28

4

They are not ordered at all. The order of elements in a dictionary is non-deterministic.

MSDN: "The order in which the items are returned is undefined."

You could use an OrderedDictionary instead to access an item via index. Or, if you want it to be ordered by the key you can use a SortedDictionary.

Update Why is a dictionary not ordered by nature?

edited May 23 '17 at 12:28

Community

1
1

answered Aug 19 '13 at 09:05

Tim Schmelter

450,073
74
686
939

Best answer because it includes information about `OrderedDictionary` from .NET 4.5 – Kamil Budziewski Aug 19 '13 at 09:07
A word of warning on the SortedDictionary class, retrieval is O(log n) and insertion is even worse. – flindeberg Aug 19 '13 at 09:13
@wudzik `OrderedDictionary` has been around since .Net 2 – Matthew Watson Aug 19 '13 at 09:49

flindeberg · Answer 2 · 2013-08-19T09:18:17.230

If you have a look at the msdn pages you find that (for your first question)

The order in which the items are returned is undefined.

And the answer to your second question is that it is implemented by a hash-table.

It is impossible for me to recommend a better course of action without knowing what your actual requirements are. But as soon as you start messing around with multiple keys and sort orders you will lose your O(1) retrieval.

score 0 · Answer 3 · edited May 23 '17 at 10:25

0

Dictionaries are not ordered at all, so you can't rely on the values there. You could try using OrderedDictionary. If you prefer a generic one, check the following link:

No generic implementation of OrderedDictionary?

edited May 23 '17 at 10:25

Community

1
1

answered Aug 19 '13 at 09:05

Artless

4,522
1
25
40

@wudzik It's been around since .NET 2, but it's not generic. The link I posted shows a generic implementation for it. – Artless Aug 19 '13 at 09:08

score 0 · Answer 4 · answered Aug 19 '13 at 09:05

No, they are not ordered, as you can read in Microsoft's library:

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.

Dictionary item order

4 Answers4