4
HashSet<object> myHashSet = new HashSet<object>();

// Iteration 1
foreach (object myObject in myHashSet) { ... }

// Some instructions THAT DO NOT MODIFY myHashSet
...

// Iteration 2
foreach (object myObject in myHashSet) { ... }

Will the objects of myHashSet be enumerated in the same order in both iterations?

4
  • While there is no technical reason why order would change, since it would require special code that varies order based on something outside f source collection... But relying on it is not a good idea since the only official documentation about order in HashSet<T> is "If order or element duplication is more important than performance for your application, consider using the List<T> class together with the Sort method.". Nov 21, 2014 at 16:35
  • You can also check reference source referencesource.microsoft.com/#System.Core/System/Collections/… to see how it is implemented (again - relying on implementation details is generally not good idea). Nov 21, 2014 at 16:36
  • Maybe you can use a SortedSet object instead of a HashSet.
    – schglurps
    Nov 21, 2014 at 16:37
  • @AlexeiLevenkov: Since the question is tagged "mono", the Microsoft reference source may not be relevant. Although, obviously, the Mono team would be crazy to deviate, and any reasonable standalone implementation would still be deterministic. Nov 21, 2014 at 16:40

2 Answers 2

5

According to the reference source of HashSet (link), the iteration order is predictable in the absence of set modifications.

public bool MoveNext() {
    if (version != set.m_version) {
        throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
    }

    while (index < set.m_lastIndex) {
        if (set.m_slots[index].hashCode >= 0) {
            current = set.m_slots[index].value;
            index++;
            return true;
        }
        index++;
    }
    index = set.m_lastIndex + 1;
    current = default(T);
    return false;
}

However unlikely, this could change in future versions of the .NET platforms, or in other implementations. To ensure that the order stays the same, make a list from the set on the first iteration, and use the list for your second iteration:

var myList = myHashSet.ToList();
foreach( var obj myObject in myList) ...
// Some instructions (may or may not modify myHashSet, it no longer matters)
foreach( var obj myObject in myList) ...
1
5

There are two possible answers to this, really.

The first is "yes, because enumerating a HashSet is deterministic, and you can simply look in the source if you don't believe me".

The second is "no, because if you want to get technical, the documentation for HashSet<T>.GetEnumerator() does not say the order is deterministic, so tomorrow the implementation could change".

You would not be wrong going with the first answer to get work done. If you want to be absolutely, positively sure, you can of course use myHashSet.ToArray() and iterate only over that, but introducing a copy just for a technicality may very well be overkill. In this case, an implementation would have to go out of its way to implement an enumeration that is not deterministic.

One important caveat, though: you are not wrong to stress that the HashSet isn't modified in between enumerations, because it is reasonable for an implementation to change the order when the set changes (which would depend on how items are stored internally).

1
  • Thank you for your answer. dasblinkenlight's answer was roughly the same but I appreciated the snippets.
    – Numid
    Nov 21, 2014 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.