Does HashSet preserve insertion order?

Question

Does the HashSet collection introduced in .NET 3.5 preserve insertion order when iterated using foreach?

The documentation states, that the collection is not sorted, but it doesn't say anything about insertion order. A pre-release BCL blog entry states that it is unordered, but this article states that it is designed to preserve insertion order. My limited testing suggests, that order is preserved, but that could be a coincidence.

Answer 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.

Answer 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...

Answer 3

The documentation states:

A HashSet<(Of <(T>)>) collection is not sorted and cannot contain duplicate elements. If order or element duplication is more important than performance for your application, consider using the List<(Of <(T>)>) class together with the Sort method.

Therefore it doesn't matter whether it actually preserves the order of elements in the current implementation, because it is not documented as doing so, and even if it appears to now this may change at any point in the future (even in a hotfix to the framework).

You should be programming against documented contracts, not implementation details.

Answer 4

Reading the source code for HashSet.AddIfNotPresent you can see insertion order is preserved assuming there haven't been any deletions.

Thus new HashSet<string> { "Tom", "Dick", "Harry" } preserves order, but if you then remove Dick and add Rick, the order will be ["Tom", "Rick", "Harry"].

Answer 5

There is specifically a SortedSet<T> collection in .NET4.

This would give you sorting, but unlikely to be insertion order sorting. Since you can use a custom IComparer you could theoretically make this do anything.

Answer 6

No, a hash set won't preserve insertion order, at least not predictably. You could use a LinkedHashSet (Java), or an equivalent. A LinkedHashSet will preserve order.

If you want order, you shouldn't even be using a set in the first place... its not made for ordered elements, except in exceptional cases.

EDIT: sounds like I'm preaching :-/ Sorry.

Answer 7

You could use a HashSet that does not preserve order together in parallel with a List that does preserve insertion/deletion order to obtain a List where every item is both unique and in insertion/deletion order.

You would initialize the HashSet and List together or clear them together. When adding a value you would use the HashSet to optimally test for whether a value has previously been added to the HashSet. If it hasn't been added to the HashSet, then add the value to both the HashSet and the List.

If an item is to be removed you would use the HashSet to efficiently test whether that item exists in the HashSet first. If it does exist you would remove it from both the HashSet and the List.

From the first deletion on the HashSet will be unique, but if any more items are added or removed it will no longer be in insertion/deletion order. However, because the HashSet ensured that you only ever added or remomed any item once in the List in the order that each item was encountered, the List will be both unique and in insertion/deletion order.