保留排序的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 => m_Dictionary.Count;

    public virtual bool IsReadOnly => m_Dictionary.IsReadOnly;

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

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

    public void Clear()
    {
        m_LinkedList.Clear();
        m_Dictionary.Clear();
    }

    public bool Remove(T item)
    {
        if (item == null) return false;
        var found = m_Dictionary.TryGetValue(item, out var 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 item != null && 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 Framework 4.5 中没有此类集合。

如果您同意第 3 方代码，请查看我的存储库（宽松的 MIT 许可证）： https://github.com/OndrejPetrzilka/Rock.Collections

有

OrderedHashSet<T>

收藏：

• 基于经典

  HashSet<T>

  源代码（来自.NET Core）
• 保留插入顺序并允许手动重新排序
• 功能反向枚举
• 与 HashSet<T>具有相同的操作复杂性
与
• Add 相比，Remove

   和 

  HashSet<T>
操作速度慢 20%
• 每个项目多消耗 8 个字节的内存

Answer 4

您可以使用 OrderedDictionary 来保留插入顺序。但要注意移除物品的成本 (O(n))。

Answer 5

您可以使用

SortedSet<T>

：https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedset-1?view=net-8.0