5

This StackOverflow answer completely describes that a HashSet is unordered and its item enumeration order is undefined and should not be relied upon.

However,

This brings up another question: should I or should I not rely upon the enumeration order between two or more sebsequent enumerations? Given there are no insertions or removals.

For example, lets say I have added some items to a HashSet:

HashSet<int> set = new HashSet<int>();
set.Add(1);
set.Add(2);
set.Add(3);
set.Add(4);
set.Add(5);

Now, when I enumerate this set via foreach, let us say I receive this sequence:

// Result: 1, 3, 4, 5, 2.

The question is: will the order preserve if I enumerate the set times and times again given I do no modifications? Will it always be the same?

AgentFire
  • 8,944
  • 8
  • 43
  • 90
  • 5
    Even if this was true, that should have been documented. Since it isn't, I wouldn't rely on it. It could break in your face anytime with a future update of the framework. Why on Earth would you use a hash if you need a guaranteed enumeration order. That's absolutely the wrong data structure you have chosen to model your data given your requirements. – Darin Dimitrov Apr 10 '16 at 13:35
  • 1
    Since a hash set is basically a hash table which has a fixed slot order, yes, iteration order is constant if you do not modify the set at all. Should you rely on that though? No, I don’t think so, you should avoid having to rely on that. – poke Apr 10 '16 at 13:35
  • Well, I'm trying to rely only on the order of two subsequental enumerations of a set, that's all. The data structure I need is O(1) add/remove plus the positive answer to the question above. Is there any? – AgentFire Apr 10 '16 at 13:39
  • *Will it always be the same* Of course not, the documentation explicitly states it is unordered. It's an implementation detail which is subject to change. – Yuval Itzchakov Apr 10 '16 at 13:39
  • @YuvalItzchakov the docs it dont state **when** it is unordered. That's why I'm asking. – AgentFire Apr 10 '16 at 13:41
  • @DarinDimitrov many things aren't just well documented on MSDN. – AgentFire Apr 10 '16 at 13:42
  • If the documentation don't say anything about ordering, you cannot assume anything about ordering. This means you can't rely on it, it's that simple. Perhaps you should open an issue to CoreFX on github, and ask them to improve the documentation around ordering of `HashSet`. – Yuval Itzchakov Apr 10 '16 at 13:42
  • 1
    Pull the implementation of GetEnumerator() and make a judgement for yourself. – paparazzo Apr 10 '16 at 13:49
  • There is no tooth fairy that is going to reorder the HashSet when you don't look at it. There might be one twenty years from now, "always" is an unpractical long time to be handing out warranties. – Hans Passant Apr 10 '16 at 13:49
  • 1
    The current implementation will produce the same order every time, as long as no updates are done to the hashset. This, I believe, is the answer to your question. No guarantees can be made about what the hashset will do after the next hotfix to .NET, this is what it means to be undocumented behavior, it can change for no apparent reason. – Lasse V. Karlsen Apr 10 '16 at 13:49

1 Answers1

4

Practically speaking, it might always be the same between enumerations, but that assumption is not provided for in the description of IEnumerable and the implementor could decide to return then in whichever order it wants.

Who knows what it is doing under the hood, and whether it will keep doing it the same way in the future. For example, a future implementation of HashSet might be optimized to detect low memory conditions and rearrange its contents in memory, thereby affecting the order in which they are returned. So 99.9% of the time they would come back the same order, but if you started exhausting memory resources, it would suddenly return things in a different order.

Bottom line is I would not rely on the order of enumeration to be consistent over time. If the order is important to you then do your foreach over set.OrderBy(x => x) so that you can make sure it is in the order you want.

Brian Pursley
  • 1,098
  • 7
  • 18