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 Framework 4.5 нет такой коллекции.

Если вы в порядке с сторонним кодом, посмотрите на мой репозиторий (разрешительная лицензия MIT): https://github.com/OndrejPetrzilka/Rock.Collections

Есть OrderedHashSet<T> коллекция:

• на основе классического HashSet<T> исходного кода (из .NET Core)
• сохраняет порядок вставок и позволяет ручное изменение порядка
• функции обратное перечисление
• имеет те же сложности операции , что и HashSet<T>
• Add и Remove на 20% медленнее по сравнению с HashSet<T>
• потребляет еще 8 байт памяти на элемент