HashSet that preserves ordering

Question

I need a HashSet that preserves insertion ordering, are there any implementations of this in the framework?

I imagine you mean like Java's [LinkedHashSet](http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html) — thejoshwolfe, Dec 10 '11 at 18:31
yeah the simplest thing to do is to wrap a linked list and hashset together ... its what I ended up doing in the past. useful for an LRU implementation — Sam Saffron, Dec 11 '11 at 02:10
@vash In lieu of that remark, the question should then really be "I need a data structure that preserved insertion order and that has access characteristics of a hashset, ie. O(1) etc." — Lasse V. Karlsen, Jul 25 '13 at 15:05
So what you actually want is a List that prevents duplicates, right? Cause that's really the only reason to use a HashSet instead of a list or array. In which case you could easily implement a class that contained both a list and a HashSet and checked against/maintained the HashSet during add/remove. — Emperor Eto, May 25 '22 at 12:39

score 45 · Answer 1 · edited Oct 06 '21 at 14:53

Standard .NET HashSet do not preserve the insertion order. For simple tests the insertion order may be preserved due to an accident, but it's not guaranteed and would not always work that way. To prove that it is enough to do some removals in between.

See this question for more information on that: Does HashSet preserve insertion order?

I have briefly implemented a HashSet which guarantees insertion order. It uses the Dictionary to look up items and the LinkedList to preserve order. All three insertion, removal and lookup work still in O(1).

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 => m_Dictionary.Count;

    public virtual bool IsReadOnly => m_Dictionary.IsReadOnly;

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

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

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

    public bool Remove(T item)
    {
        if (item == null) return false;
        var found = m_Dictionary.TryGetValue(item, out var 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 item != null && m_Dictionary.ContainsKey(item);
    }

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

You should really provide an overload taking an `IEqualityComparer` to pass to the same overload of `IDictionary`. Out of the box, your example check equality through object references (for classes, at least) and offers no options to change that behaviour. I understand however that this is a simple example. — Simon Belanger, Jul 25 '13 at 16:57
@SimonBelanger Agree. I have just posted a version which implements all variants of common constructors and methods here: http://gmamaladze.wordpress.com/2013/07/25/hashset-that-preserves-insertion-order-or-net-implementation-of-linkedhashset/ — George Mamaladze, Jul 25 '13 at 22:29
@HimBromBeere - Good question. Well yes, but actually no. If you want to delete a specific element, because you have to find the element, the removal itself is O(1). If you take a look at my implementation we use a dictionary to find it which is O(1), instead of interesting the list. first.https://stackoverflow.com/questions/33987542/time-complexity-of-deletion-in-a-linked-list — George Mamaladze, Sep 13 '20 at 06:39
@HimBromBeere: It's `O(1)` in particular because @GeorgeMamaladze is storing the `LinkedListNode` reference, which makes removal in a doubly-linked list constant time. — AndreasHassing, Oct 01 '21 at 12:18
Why not just use a Dictionary and a list ? The dictionary essentially acts like a hash if you check for contains on insertion and list keeps the order, the dictionary keeps track of indices on insertion. — WDUK, May 02 '22 at 01:17

score 23 · Answer 2 · edited May 04 '16 at 23:45

23

You can get this functionality easily using KeyedCollection<TKey,TItem> specifying the same type argument for TKey and TItem:

public class OrderedHashSet<T> : KeyedCollection<T, T>
{
    protected override T GetKeyForItem(T item)
    {
        return item;
    }
}

edited May 04 '16 at 23:45

Peter Duniho

68,759
7
102
136

answered Feb 26 '14 at 21:27

kcnygaard

794
7
18

3

When you call `Remove` will it call [`Remove(T)`](http://msdn.microsoft.com/en-us/library/ms132413(v=vs.110).aspx) or [`Remove(TKey)`](http://msdn.microsoft.com/en-us/library/ms132459(v=vs.110).aspx)? The first is O(n) and the second is O(1). – Scott Chamberlain Feb 26 '14 at 22:11
2

It calls `Remove(TKey)` because it is the one on the most derived class. However, calling Remove() when the collection is cast as a Collection or ICollection will call the `Remove(T)` overload. – kcnygaard Feb 26 '14 at 22:53
7

Another clarification: Both `Remove(T)` and `Remove(TKey)` are O(n) because `KeyedCollection` uses a list to store the items. – kcnygaard Feb 27 '14 at 14:51
5

Note that unlike a regular `System.Collections.Generic.HashSet`, this will throw a `System.ArgumentException` on duplicate key instead of returning `false`. – MrLore Oct 05 '15 at 14:29
1

@kcnygaard - why do you believe that KeyedCollection maintains insertion ordering? Internally it is simply a Dictionary, which is [known to not maintain order under all conditions](https://stackoverflow.com/a/16694344/199364). – ToolmakerSteve Nov 20 '18 at 21:34
1

@ToolmakerSteve: `KeyedCollection` derives from `Collection`, which implements `IList`, i.e., indexed access. It is fundamentally a _list_ that _also_ provides key-based access (by default via an aux. internal dictionary). – mklement0 Jan 28 '19 at 05:01
@ScottChamberlain: From the [docs for the `.Remove(TKey key)` method](https://learn.microsoft.com/en-us/dotnet/api/system.collections.objectmodel.keyedcollection-2.remove): "This method is an O(n) operation, where n is Count." It seems that the internally used dictionary is only used for key-based lookups that return the associated item directly, it doesn't also store information about that item's index in the internal list. – mklement0 Jan 28 '19 at 05:07
[OrderedDictionary](https://learn.microsoft.com/en-us/dotnet/api/system.collections.specialized.ordereddictionary?view=net-6.0) offers the same results as this solution without the additional implementation. – ZakChar Mar 05 '22 at 01:05

score 13 · Answer 3 · answered Oct 21 '16 at 17:38

If you need constant complexity of Add, Remove, Contains and order preservation, then there's no such collection in .NET Framework 4.5.

If you're okay with 3rd party code, take a look at my repository (permissive MIT license): https://github.com/OndrejPetrzilka/Rock.Collections

There's OrderedHashSet<T> collection:

based on classic HashSet<T> source code (from .NET Core)
preserves order of insertions and allows manual reordering
features reversed enumeration
has same operation complexities as HashSet<T>
Add and Remove operations are 20% slower compared to HashSet<T>
consumes 8 more bytes of memory per item

score 2 · Answer 4 · answered Mar 05 '22 at 01:13

2

You can use OrderedDictionary to preserve the order of insertion. But beware of the cost of Removing items (O(n)).

answered Mar 05 '22 at 01:13

ZakChar

191
1
4

HashSet that preserves ordering

4 Answers4

Linked

Related