保留排序的HashSet

Question

我需要一个保留插入排序的HashSet,在框架中是否有任何实现？

Answer 1

标准.NET HashSet不保留插入顺序. 对于简单的测试,插入顺序可能由于事故而保留,但是不能保证并且不会总是以这种方式工作.为了证明在两者之间进行一些删除就足够了.

有关详细信息,请参阅此问题:HashSet是否保留了插入顺序？

我简要地实现了一个HashSet保证插入顺序的方法.它使用Dictionary查找项目和LinkedList保存顺序.所有三个插入,移除和查找工作仍在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);
    }
}

Answer 2

您可以使用KeyedCollection<TKey,TItem>为TKey和TItem指定相同的类型参数来轻松获得此功能:

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

Answer 3

如果你需要不断的复杂性Add，Remove，Contains和订单保存，再有就是在.NET框架4.5没有这样的集合。

如果您对第三方代码没问题，请查看我的存储库（MIT许可许可证）：https : //github.com/OndrejPetrzilka/Rock.Collections

有OrderedHashSet<T>集合：

• 基于经典HashSet<T>源代码（来自.NET Core）
• 保留插入顺序并允许手动重新排序
• 功能反转枚举
• 具有相同的操作复杂性的HashSet<T>
• Add和Remove操作相比，速度要慢20％HashSet<T>
• 每个项目消耗8个以上的内存字节