HashSet that Preserves Insertion Order or .NET Implementation of LinkedHashSet

• Download OrderedSet C# project

Introduction

I was looking for a data structure (under .NET) which will do all tree basic operations (add, contains and remove) in constant-time O(1) and at the same time allow to retrieve elements exactly in the same order as they were added.

Some facts I’ve discovered after some Googling:

1. There is no such data structure natively available as of .NET 4.5
2. Many people naively assume an ordinary .NET HashSet preserves insertion order
3. Indeed HashSet accidentally preserves insertion order until you remove and re-add some elements
4. There is such a data structure in Java – LinkedHashSet
5. No, I did not find a (working) corresponding implementation in .NET

So I’ve implemented one. Some notes before you go ahead and copy & paste the code:

• The example below implements only ICollection<T> generic interface which should be good enough for most cases.
• Inside this project, you will find full ISet<T> generic implementation which is fully interchangeable with HashSet (after .NET 4.0, a HashSet had no dedicated interface before 4.0).
• The implementation uses linked list in combination with dictionary to define the iteration ordering and at the same time allow O(1) removal.
• The order is not affected if an element is re-inserted into the set, it retains its old position.

public class OrderedSet<T> : ICollection<T>
{
    private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
    private readonly LinkedList<T> m_LinkedList;

    public OrderedSet()
        : this(EqualityComparer<T>.Default)
    {
    }

    public OrderedSet(IEqualityComparer<T> comparer)
    {
        m_Dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
        m_LinkedList = new LinkedList<T>();
    }

    public int Count
    {
        get { return m_Dictionary.Count; }
    }

    public virtual bool IsReadOnly
    {
        get { return m_Dictionary.IsReadOnly; }
    }

    void ICollection<T>.Add(T item)
    {
        Add(item);
    }

    public void Clear()
    {
        m_LinkedList.Clear();
        m_Dictionary.Clear();
    }

    public bool Remove(T item)
    {
        LinkedListNode<T> node;
        bool found = m_Dictionary.TryGetValue(item, out node);
        if (!found) return false;
        m_Dictionary.Remove(item);
        m_LinkedList.Remove(node);
        return true;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return m_LinkedList.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public bool Contains(T item)
    {
        return m_Dictionary.ContainsKey(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        m_LinkedList.CopyTo(array, arrayIndex);
    }

    public bool Add(T item)
    {
        if (m_Dictionary.ContainsKey(item)) return false;
        LinkedListNode<T> node = m_LinkedList.AddLast(item);
        m_Dictionary.Add(item, node);
        return true;
    }
}