Click here to Skip to main content
14,839,739 members
Articles / Programming Languages / C#
Technical Blog
Posted 26 Jul 2013

Tagged as

Stats

18.7K views
3 bookmarked

HashSet that Preserves Insertion Order or .NET Implementation of LinkedHashSet

Rate me:
Please Sign up or sign in to vote.
4.43/5 (3 votes)
26 Jul 2013CPOL1 min read
HashSet that preserves Insertion Order or .NET implementation of LinkedHashSet

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

OrderedHashSet

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.
C#
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;
    }
}

Image 2 Image 3

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

George Mamaladze
Software Developer
Germany Germany
Tweeter: @gmamaladze
Google+: gmamaladze
Blog: gmamaladze.wordpress.com

Comments and Discussions

 
QuestionYour remove is O(n) Pin
Basarat Ali Syed2-Oct-14 14:45
MemberBasarat Ali Syed2-Oct-14 14:45 
AnswerRe: Your remove is O(n) Pin
OliverMuenchow4-Dec-14 22:06
MemberOliverMuenchow4-Dec-14 22:06 
QuestionError in IntersectWith() Pin
Member 770004725-Sep-14 0:53
MemberMember 770004725-Sep-14 0:53 
QuestionSemi-generic?? Pin
Matt T Heffron26-Jul-13 15:39
professionalMatt T Heffron26-Jul-13 15:39 
AnswerRe: Semi-generic?? Pin
George Mamaladze26-Jul-13 22:14
MemberGeorge Mamaladze26-Jul-13 22:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.