6

I was looking at some code my co-worker checked in, it looked like this:

return list.OrderBy(item => item.Order).ToDictionary(item => item.Id);

I immediately told my co-worker that his code is wrong, because the Dictionary is a hash table, a non-sorted collection. He should either use an order-preserving collection, or sort the items later as he reads them from the dictionary with foreach, I said.

But he replied "No, no, my code is correct! Look: now that I have added the OrderBy, the items appear in correct order."

Turns out, on the test case, he was right. I tried on some other data, but it still was perfectly sorted!

I told him that he should not rely on this behaviour, but he disagrees, and I'm having trouble explaining why. Besides, I'm interested in why the order so often seem to be preserved.

So my question is... Why does the Dictionary, a fundamentally unsorted collection, looks so much like it is sorted?

Eldritch Conundrum
  • 8,452
  • 6
  • 42
  • 50
  • 3
    Dictionary<> provides no guarantee that the collection is unordered. It doesn't use Random on purpose. Yes, the code is wrong. – Hans Passant Mar 22 '12 at 13:18
  • 1
    yes Justin, this is a duplicate. The answer of the question you linked is what I wanted. How can you find duplicates so quickly among so many questions about dictionaries? I searched and couldn't find it. Thank you! – Eldritch Conundrum Mar 22 '12 at 13:25
  • I don't know (which is why I'm posting this as a comment) but I imagine it's the same as in SQL: the rows returned by `SELECT` are returned in unspecified order unless an `ORDER BY` clause is included. Often, particularly in small data sets, the rows are returned in the same order they were inserted, which trips a lot of people up. (I always tell people to include an `ORDER BY` if they care at all about the ordering of the results. It *might* work without it, but it also might break horribly.) – user Mar 22 '12 at 13:27
  • 3
    @EldritchConundrum -- It was the first result on Google for `.net dictionary order`. I find that Google sometimes works better than the built in search. – Justin Mar 22 '12 at 13:28

2 Answers2

7

It is sorted, because of how Dictionary is implemented (and in your case items are added in order). But this is implementation details.

Tell your co-worker there is a SortedDictionary class that exists, this should convince him we can't rely on the items order with a simple Dictionary ;)

ken2k
  • 48,145
  • 10
  • 116
  • 176
  • 1
    It is an implementation detail, sure, but I don't think it is going to change. Maybe it is ok to say that Add()-only dictionaries do preserve order. – Eldritch Conundrum Mar 22 '12 at 13:30
  • @EldritchConundrum Really, you shouldn't assume that. Currently it is the case, but in a future version it might not be. And think about other implementations of the framework (Mono for instance), there is no guarantee they implemented Dictionary the same way. – ken2k Mar 22 '12 at 13:33
  • Yes. More importantly, now I know how to build a test case that my co-worker's code will fail on ;) I just have to remove and add before the foreach. – Eldritch Conundrum Mar 22 '12 at 13:41
3

When iterating over a dictionary you would get the items in it in the order they were inserted to the dictionary.

In the example, a list gets sorted, then each item gets added to the dictionary in turn.

The end result is that the items in the dictionary are in the sort order of the list.

However, this just happens to be the case with the current implementation of Dictionary - there is no guarantee that it will stay that way.

If you need to have the items in a Dictionary in a specific order, you should be using a SortedDictionary.

Community
  • 1
  • 1
Oded
  • 489,969
  • 99
  • 883
  • 1,009
  • Can you explain better why are they sorted. I'd say they are "ordered" by their hash which is the property "Id" – Luis Filipe Mar 22 '12 at 13:18
  • 1
    @LuisFilipe - I don't follow. The list got ordered (`list.OrderBy(item => item.Order)` then converted to a `Dictionary`. The conversion works by adding each item to the dictionary. The items in the dictionary are "ordered" in that they are in insertion order. Since they were _inserted_ in order, the dictionary is in order. – Oded Mar 22 '12 at 13:20
  • Is this guaranteed by specification/contract, or is it an artifact of how a specific implementation is written? If it is guaranteed behavior, a citation would be useful. – user Mar 22 '12 at 13:24
  • @MichaelKjörling - There is no guarantee, it is simply how the current version of `Dictionary` is implemented. – Oded Mar 22 '12 at 13:28
  • Yes, I saw your edit after I added that comment. :) – user Mar 22 '12 at 13:30
  • 1
    Luis, actually keys are stored in a hash-dependent order, but values are not, and the dictionary enumerator uses the value store. – Eldritch Conundrum Mar 22 '12 at 13:33