Pertanyaan HashSet yang menjaga pemesanan


Saya memerlukan HashSet yang mempertahankan penyisipan pemesanan, apakah ada implementasi ini dalam kerangka?


32
2017-10-12 00:42


asal


Jawaban:


Standar .NET HashSet jangan pertahankan urutan penyisipan. Untuk tes sederhana urutan penyisipan dapat dipertahankan karena kecelakaan, tetapi itu tidak dijamin dan tidak akan selalu bekerja seperti itu. Untuk membuktikan bahwa itu cukup untuk melakukan beberapa penghapusan di antaranya.

Lihat pertanyaan ini untuk informasi lebih lanjut tentang hal itu: Apakah HashSet mempertahankan urutan penyisipan?

Saya telah menerapkan secara singkat a HashSet yang menjamin urutan penyisipan. Ini menggunakan Dictionary untuk mencari item dan LinkedList untuk menjaga ketertiban. Semua tiga penyisipan, penghapusan dan pencarian masih dalam 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



Anda bisa menggunakan fungsi ini dengan mudah KeyedCollection<TKey,TItem> menentukan argumen tipe yang sama untuk TKey dan TItem:

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

17
2018-02-26 21:27



Jika Anda membutuhkan kompleksitas konstan Add, Remove, Contains dan memesan pelestarian, maka tidak ada koleksi seperti itu di .NET Framework 4.5.

Jika Anda setuju dengan kode pihak ketiga, lihatlah repositori saya (permisif lisensi MIT): https://github.com/OndrejPetrzilka/Rock.Collections

Ada OrderedHashSet<T> koleksi:

  • berdasarkan klasik HashSet<T> kode sumber (dari .NET Core)
  • mempertahankan urutan penyisipan dan memungkinkan penataan ulang manual
  • fitur enumerasi terbalik
  • punya kompleksitas operasi yang sama sebagai HashSet<T>
  • Add dan Remove operasi 20% lebih lambat dibandingkan dengan HashSet<T>
  • mengkonsumsi 8 lebih banyak byte memori per item

3
2017-10-21 17:38