HashSet giữ nguyên thứ tự

Question

Tôi cần một HashSet lưu giữ thứ tự chèn, có bất kỳ triển khai nào trong khung này không?

Answer 1

Chuẩn .NET HashSet không giữ lại thứ tự chèn. Để kiểm tra đơn giản, thứ tự chèn có thể được bảo quản do tai nạn, nhưng nó không được bảo đảm và sẽ không luôn hoạt động theo cách đó. Để chứng minh rằng nó là đủ để làm một số loại bỏ ở giữa.

Xem câu hỏi này để biết thêm thông tin về rằng: Does HashSet preserve insertion order?

tôi có một thời gian ngắn thực hiện một HashSet mà đảm bảo trật tự chèn. Nó sử dụng Dictionary để tra cứu các mục và LinkedList để bảo vệ đơn đặt hàng. Tất cả ba công việc chèn, loại bỏ và tra cứu vẫn còn trong 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

Bạn có thể nhận được chức năng này dễ dàng bằng KeyedCollection<TKey,TItem> quy định cụ thể đối số kiểu tương tự cho TKey và TItem:

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

Answer 3

Nếu bạn cần phức tạp liên tục của Add, Remove, Contains và bảo quản trật tự, sau đó không có bộ sưu tập như vậy trong .NET Framework 4.5.

Nếu bạn đang okay với mã bên thứ 3, hãy nhìn vào kho lưu trữ của tôi (giấy phép MIT dễ dãi): https://github.com/OndrejPetrzilka/Rock.Collections

Có OrderedHashSet<T> bộ sưu tập:

• dựa trên mã nguồn cổ điển HashSet<T> (từ .NET Core)
• bảo tồn thứ tự chèn vào và cho phép chỉnh sửa thủ công
• tính năng đảo ngược liệt kê
• có phức tạp hoạt động tương tự như HashSet<T>
• Add và Remove hoạt động chậm hơn 20% so với HashSet<T>
• tiêu thụ hơn 8 byte bộ nhớ cho mỗi mục