Pregunta HashSet que conserva el orden


Necesito un HashSet que preserve el orden de inserción, ¿hay alguna implementación de esto en el marco?


32
2017-10-12 00:42


origen


Respuestas:


Estándar .NET HashSet no conservar el orden de inserción. Para pruebas simples, el orden de inserción puede conservarse debido a un accidente, pero no está garantizado y no siempre funcionará de esa manera. Para demostrar que es suficiente hacer algunas remociones en el medio.

Vea esta pregunta para más información sobre eso: ¿HashSet conserva el orden de inserción?

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

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

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

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

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

22
2017-07-25 08:41



Puede obtener esta funcionalidad fácilmente usando KeyedCollection<TKey,TItem> especificando el mismo argumento de tipo para TKey y TItem:

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

17
2018-02-26 21:27



Si necesita complejidad constante de Add, Remove, Contains y preservación de pedidos, entonces no existe tal colección en .NET Framework 4.5.

Si está de acuerdo con el código de terceros, eche un vistazo a mi repositorio (licencia MIT permisiva): https://github.com/OndrejPetrzilka/Rock.Collections

Hay OrderedHashSet<T> colección:

  • basado en clásico HashSet<T> código fuente (de .NET Core)
  • conservas orden de inserciones y permite reordenamiento manual
  • caracteristicas enumeración inversa
  • tiene mismas complejidades de operación como HashSet<T>
  • Add y Remove las operaciones son un 20% más lentas en comparación con HashSet<T>
  • consume 8 bytes más de memoria por artículo

3
2017-10-21 17:38