Does HashSet preserve insertion order?

Solution 1:

This HashSet MSDN page specifically says:

A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

Solution 2:

I think the article claiming it preserves ordering is just plain wrong. For simple tests the insertion order may well be preserved due to the internal structure, but it's not guaranteed and won't always work that way. I'll try to come up with a counterexample.

EDIT: Here's the counterexample:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        var set = new HashSet<int>();

        set.Add(1);
        set.Add(2);
        set.Add(3);
        set.Remove(2);
        set.Add(4);


        foreach (int x in set)
        {
            Console.WriteLine(x);
        }
    }
}

This prints 1, 4, 3 despite 3 having been inserted before 4.

It's possible that if you never remove any items, it will preserve insertion order. I'm not sure, but I wouldn't be entirely surprised. However, I think it would be a very bad idea to rely on that:

• It's not documented to work that way, and the documentation explicitly states that it's not sorted.
• I haven't looked at the internal structures or source code (which I don't have, obviously) - I'd have to study them carefully before making any such claim in a firm manner.
• The implementation could very easily change between versions of the framework. Relying on this would be like relying on the string.GetHashCode implementation not changing - which some people did back in the .NET 1.1 days, and then they got burned when the implementation did change in .NET 2.0...