¿Cuál es el equivalente de LinkedHashSet (Java) en C#?

Question

¿Cuál es el equivalente de un LinkedHashSet (Java) en C#?

Answer 1

Completé los métodos inacabados y generalmente pulí la clase que 'achitaka-san' publicó.

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

} 

usings requeridos:

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

Advertencia: La clase es en gran parte no probado, especialmente los métodos Iset. Úselo bajo su propio riesgo.
Espero que alguien encuentre esto útil. :)

Answer 2

No hay equivalente directo en C#. La clase apropiada para usar depende del comportamiento deseado. La clase HashSet preservará la exclusividad de los elementos. También es posible que desee consultar SortedSet y SortedDictionary.

No existe una clase en C# que combine una lista vinculada con la exclusividad requerida en una estructura de datos establecida, por lo que si necesita ambos comportamientos, entonces deberá crear la suya propia.

Answer 3

He implementado brevemente un HashSet que garantiza el orden de inserción. Utiliza el Dictionary para buscar elementos y el LinkedList para conservar el orden. Los tres trabajos de inserción, eliminación y búsqueda aún están en 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."); 
    } 
} 

Answer 4

HashSet hace el trabajo porque es prácticamente equivalente a LinkedHashSet en Java. HashSet está respaldado por una lista vinculada, aunque los documentos no indican explícitamente que conserva el orden o que está respaldado por una lista vinculada basada en una matriz. Puede ver desde the source code la implementación es un LinkedHashSet.

No se permiten duplicados como Java LinkedHashSet. La única diferencia entre esto y LinkedHashSet es que si elimina algo del conjunto, solo marca el elemento como libre en el conjunto, por lo que al agregar un elemento después de eliminar() se llenan primero los espacios vacíos de la matriz antes de "anexar". La forma de evitar esto es llamar al método TrimExcess(). Entonces, aunque no es exactamente lo mismo en muchos casos de uso, p. serializar y deserializar y para conjuntos efectivamente inmutables una vez creados funciona muy bien.

Siempre puede crear una subclase y anular eliminar() para llamar siempre a TrimExcess() para obtener el mismo comportamiento. ¡Y puede nombrar la clase LinkedHashSet para mayor claridad!

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

Salida:

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