순서를 유지하는 HashSet

Question

삽입 순서를 유지하는 HashSet이 필요합니다. 프레임 워크에이 구현이 있습니까?

Answer 1

표준 .NET HashSet은 삽입 순서를 유지하지 않습니다. 간단한 테스트의 경우 삽입 주문은 사고로 인해 보존 될 수 있지만 보장되지는 않으며 항상 그런 식으로 작동하지는 않습니다. 그 사이에 몇 가지 제거 작업을 수행하는 것만으로 충분하다는 것을 입증합니다.

는에 대한 자세한 내용은이 질문을 참조하십시오 : Does HashSet preserve insertion order?

나는 간단히 삽입 순서를 보장하는 HashSet을 구현했습니다. 항목을 조회하는 데 Dictionary을 사용하고 순서를 유지하려면 LinkedList을 사용합니다. 3 가지 삽입, 제거 및 검색 작업은 모두 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

쉽게 TKEY 및 TITEM에 대해 동일한 유형의 인수 지정 KeyedCollection<TKey,TItem>을 사용하여이 기능을 얻을 수 있습니다 : 당신이 Add, Remove, Contains 및 주문 보존 일정 복잡성을해야하는 경우

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

Answer 3

을 한 후 아무 없다 .NET Framework 4.5에서 이러한 컬렉션.

당신이 제 3 자 코드 괜찮아, 내 저장소 (허용 MIT 라이센스)를 살펴 : 고전 HashSet<T> 소스 코드를 기반으로

• (에서 : https://github.com/OndrejPetrzilka/Rock.Collections

  OrderedHashSet<T> 수집있다 .NET 코어)

• 보존 삽입 순서 및 수동 재주문
열거
• 반전
• 기능 동일한 동작 복잡성HashSet<T> 같은
• Add 및 Remove 작업 HashSet<T>
• 는 I 상상