What is the equivalent of LinkedHashSet (Java) in C#?

Question

What is the equivalent of a LinkedHashSet (Java) in C#?

Answer 1

I completed the unfinished methods and generally polished the class that 'achitaka-san' posted.

public class LinkedHashSet<T> : ISet<T> {

    private readonly IDictionary<T, LinkedListNode<T>> dict;
    private readonly LinkedList<T> list;

    public LinkedHashSet(int initialCapacity) {
        this.dict = new Dictionary<T,LinkedListNode<T>>(initialCapacity);
        this.list = new LinkedList<T>();
    }

    public LinkedHashSet() {
        this.dict = new Dictionary<T,LinkedListNode<T>>();
        this.list = new LinkedList<T>();
    }

    public LinkedHashSet(IEnumerable<T> e) : this() {
        addEnumerable(e);
    }

    public LinkedHashSet(int initialCapacity, IEnumerable<T> e) : this(initialCapacity) {
        addEnumerable(e);
    }

    private void addEnumerable(IEnumerable<T> e) {
        foreach (T t in e) {
            Add(t);
        }
    }

    //
    // ISet implementation
    //

    public bool Add(T item) {
        if (this.dict.ContainsKey(item)) {
            return false;
        }
        LinkedListNode<T> node = this.list.AddLast(item);
        this.dict[item] = node;
        return true;
    }

    public void ExceptWith(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        foreach (T t in other) {
            Remove(t);
        }
    }

    public void IntersectWith(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        T[] ts = new T[Count];
        CopyTo(ts, 0);
        foreach (T t in ts) {
            if (!System.Linq.Enumerable.Contains(other, t)) {
                Remove(t);
            }
        }
    }

    public bool IsProperSubsetOf(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        int contains = 0;
        int noContains = 0;
        foreach (T t in other) {
            if (Contains(t)) {
                contains++;
            } else {
                noContains++;
            }
        }
        return contains == Count && noContains > 0;
    }

    public bool IsProperSupersetOf(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        int otherCount = System.Linq.Enumerable.Count(other);
        if (Count <= otherCount) {
            return false;
        }
        int contains = 0;
        int noContains = 0;
        foreach (T t in this) {
            if (System.Linq.Enumerable.Contains(other, t)) {
                contains++;
            } else {
                noContains++;
            }
        }
        return contains == otherCount && noContains > 0;
    }

    public bool IsSubsetOf(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        foreach (T t in this) {
            if (!System.Linq.Enumerable.Contains(other, t)) {
                return false;
            }
        }
        return true;
    }

    public bool IsSupersetOf(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        foreach (T t in other) {
            if (!Contains(t)) {
                return false;
            }
        }
        return true;
    }

    public bool Overlaps(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        foreach (T t in other) {
            if (Contains(t)) {
                return true;
            }
        }
        return false;
    }

    public bool SetEquals(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        int otherCount = System.Linq.Enumerable.Count(other);
        if (Count != otherCount) {
            return false;
        }
        return IsSupersetOf(other);
    }

    public void SymmetricExceptWith(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        T[] ts = new T[Count];
        CopyTo(ts, 0);
        HashSet<T> otherList = new HashSet<T>(other);
        foreach (T t in ts) {
            if (otherList.Contains(t)) {
                Remove(t);
                otherList.Remove(t);
            }
        }
        foreach (T t in otherList) {
            Add(t);
        }
    }

    public void UnionWith(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other cannot be null");
        }
        foreach (T t in other) {
            Add(t);
        }
    }

    //
    // ICollection<T> implementation
    //

    public int Count {
        get {
            return this.dict.Count;
        }
    }

    public bool IsReadOnly {
        get {
            return this.dict.IsReadOnly;
        }
    }

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

    public void Clear() {
        this.dict.Clear();
        this.list.Clear();
    }

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

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

    public bool Remove(T item) {
        LinkedListNode<T> node;
        if (!this.dict.TryGetValue(item, out node)) {
            return false;
        }
        this.dict.Remove(item);
        this.list.Remove(node);
        return true;
    }

    //
    // IEnumerable<T> implementation
    //

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

    //
    // IEnumerable implementation
    //

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

}

Required usings:

using System;
using System.Collections;
using System.Collections.Generic;

Warning: The class is largely untested, especially the ISet methods. Use at your own risk.
I hope someone finds this useful. :)

Answer 2

HashSet does the job because it is virtually equivalent to LinkedHashSet in Java. HashSet is backed by a linked list - though the docs don't explicitly state that it preserves the order or that it is backed by a array-based linked list. You can see from the source code the implementation is a LinkedHashSet.

Duplicates are not allowed just like the Java LinkedHashSet. The one difference between this and LinkedHashSet is that if you remove something from the set, it only marks the element as free in the array, and so adding an item after a remove() fills up the empty array slots first before “appending”. The way around this is to call the TrimExcess() method. So, while it is not exactly the same in many use cases, e.g. serialize and deserialize and for effectively immutable sets once created it works great.

You can always subclass and override remove() to always call TrimExcess() to get the same behavior. And you can name the class LinkedHashSet for clarity!

using System;
using System.Collections.Generic;


namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            String[] crew = {"Spock", "Kirk", "Bones", "Picard", "Uhura", "Chekov"};
            HashSet<String> linkedHashSet = new HashSet<String>(crew);

            // Show order is preserved
            foreach(String value in linkedHashSet){
                Console.Write(value); Console.Write(" ");
            }

            // Remove from the middle
            linkedHashSet.Remove("Picard");
            Console.WriteLine();
            foreach(String value in linkedHashSet){
                Console.Write(value); Console.Write(" ");
            }

            // Add it back but it is back in the middle not the end
            linkedHashSet.Add("Picard");
            Console.WriteLine();
            foreach(String value in linkedHashSet){
                Console.Write(value); Console.Write(" ");
            }

            // Remove and trim then add
            linkedHashSet.Remove("Picard");
            linkedHashSet.TrimExcess();
            linkedHashSet.Add("Picard");
            Console.WriteLine();
            foreach(String value in linkedHashSet){
                Console.Write(value); Console.Write(" ");
            }
            Console.WriteLine();
        }
    }
}

Output:

Spock Kirk Bones Picard Uhura Chekov
Spock Kirk Bones Uhura Chekov
Spock Kirk Bones Picard Uhura Chekov
Spock Kirk Bones Uhura Chekov Picard

Answer 3

There is no direct equivalent in C#. The appropriate class to use depends on the desired behaviour. The HashSet class will preserve the uniqueness of the elements. You may also want to check out SortedSet and SortedDictionary.

There is no class in C# that combines a Linked List with uniqueness required in a Set data structure, so if you need both behaviours then you will need to build your own.

Answer 4

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> : ISet<T>
{
    private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
    private readonly LinkedList<T> m_LinkedList;

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

    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;
    }

    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 int Count
    {
        get { return m_Dictionary.Count; }
    }

    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 virtual bool IsReadOnly
    {
        get { return m_Dictionary.IsReadOnly; }
    }

    public void UnionWith(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public void IntersectWith(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public void ExceptWith(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public bool IsSubsetOf(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public void SymmetricExceptWith(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public bool IsSupersetOf(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public bool IsProperSupersetOf(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public bool IsProperSubsetOf(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public bool Overlaps(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    public bool SetEquals(IEnumerable<T> other)
    {
        throw GetNotSupportedDueToSimplification();
    }

    private static Exception GetNotSupportedDueToSimplification()
    {
        return new NotSupportedException("This method is not supported due to simplification of example code.");
    }
}