HashSet<T> 유형은 언제 사용해야 합니까?

StackOverflow https://stackoverflow.com/questions/1247442

문제

나는 탐험하고있다 HashSet<T> 유형이지만 컬렉션에서 그것이 어디에 있는지 이해하지 못합니다.

그것을 대체하는 데 사용할 수 있습니까? List<T>?나는 다음의 성능을 상상한다. HashSet<T> 더 나아지기는 했지만 그 요소에 대한 개별적인 접근은 볼 수 없었습니다.

열거용으로만 사용됩니까?

도움이 되었습니까?

해결책

중요한 점은 HashSet<T> 바로 거기에 이름이 있습니다:그것은 세트.단일 집합으로 할 수 있는 유일한 작업은 해당 집합의 구성원이 무엇인지 확인하고 항목이 구성원인지 확인하는 것입니다.

단일 요소를 검색할 수 있는지 묻습니다(예: set[45])은 세트의 개념을 오해하고 있습니다.집합의 45번째 요소라는 것은 없습니다.세트의 항목에는 순서가 없습니다.집합 {1, 2, 3}과 {2, 3, 1}은 구성원이 동일하고 구성원이 중요하기 때문에 모든 측면에서 동일합니다.

반복하는 것은 다소 위험합니다. HashSet<T> 그렇게 하면 세트의 항목에 순서가 부과되기 때문입니다.그 순서는 실제로 집합의 속성이 아닙니다.당신은 그것에 의존해서는 안됩니다.컬렉션의 항목 순서가 중요하다면 해당 컬렉션은 세트가 아닙니다.

세트는 매우 제한적이며 고유한 멤버로 구성됩니다.반면에 그들은 정말 빠릅니다.

다른 팁

다음은 내가 사용하는 실제 예입니다. HashSet<string>:

UnrealScript 파일용 구문 강조 표시의 일부는 다음과 같은 새로운 기능입니다. Doxygen 스타일 주석을 강조 표시합니다..나는 @ 또는 \ 명령은 회색(유효) 또는 빨간색(유효)으로 표시할지 여부를 결정하는 데 유효합니다.나는 HashSet<string> 모든 유효한 명령 중 하나를 누를 때마다 @xxx 어휘 분석기의 토큰을 사용합니다. validCommands.Contains(tokenText) 내 O(1) 유효성 검사로.난 정말 그 외에는 아무것도 신경쓰지 않아 존재 명령의 세트 유효한 명령 중.내가 직면한 대안을 살펴보겠습니다.

  • Dictionary<string, ?>:값에 어떤 유형을 사용합니까?그냥 쓸 예정이라 값은 의미가 없습니다. ContainsKey.메모:.NET 3.0 이전에는 이것이 O(1) 조회를 위한 유일한 선택이었습니다. HashSet<T> 3.0에 추가되어 구현하도록 확장되었습니다. ISet<T> 4.0용.
  • List<string>:목록을 정렬된 상태로 유지하면 다음을 사용할 수 있습니다. BinarySearch, 이는 O(log n)입니다(위에서 언급한 이 사실을 보지 못했습니다).그러나 유효한 명령 목록은 절대 변경되지 않는 고정 목록이므로 이는 단순히...
  • string[]:다시, Array.BinarySearch O(log n) 성능을 제공합니다.목록이 짧다면 이것이 가장 성능이 좋은 옵션일 수 있습니다.항상 오버헤드 공간이 적습니다. HashSet, Dictionary, 또는 List.심지어 BinarySearch, 큰 세트의 경우 더 빠르지는 않지만 작은 세트의 경우 실험해 볼 가치가 있습니다.내 것에는 수백 가지 항목이 있으므로 이것을 전달했습니다.

ㅏ HashSet<T> 구현 ICollection<T> 상호 작용:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

ㅏ List<T> 구현하다 IList<T>, 이는 ICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

HashSet에는 내부적으로 해시 테이블을 통해 구현된 의미 체계가 설정되어 있습니다.

세트는 다음을 포함하지 않는 컬렉션입니다 중복 요소와 그 요소의 는 특별한 순서가 없습니다.

인덱스/위치/목록 동작이 손실되면 HashSet은 무엇을 얻나요?

HashSet에서 항목을 추가하고 검색하는 것은 인덱서를 통하지 않고 항상 개체 자체에 의해 수행되며 O(1) 작업에 가깝습니다(목록은 O(1) 추가, O(1) 인덱스별 검색, O(n) 찾기 /제거하다).

HashSet의 동작은 다음을 사용하는 것과 비교할 수 있습니다. Dictionary<TKey,TValue> 키만 값으로 추가/제거하고 사전 값 자체는 무시합니다.사전의 키에는 중복된 값이 없을 것으로 예상할 수 있으며 이것이 "설정" 부분의 핵심입니다.

성능은 List 대신 HashSet을 선택하는 나쁜 이유입니다.대신, 귀하의 의도를 더 잘 포착하는 것은 무엇입니까?순서가 중요하다면 Set(또는 HashSet)은 제외됩니다.중복이 허용되는 경우에도 마찬가지입니다.그러나 순서에 신경 쓰지 않고 중복을 원하지 않는 상황이 많이 있습니다. 바로 그런 경우에 세트가 필요합니다.

해시셋은 세트 해싱으로 구현됩니다.집합은 중복된 요소가 없는 값의 모음입니다.세트의 값은 일반적으로 순서가 지정되지 않습니다.따라서 아니요, 집합을 사용하여 목록을 대체할 수는 없습니다(처음에 집합을 사용해야 하지 않는 한).

어떤 세트가 좋을지 궁금하시다면:중복을 제거하고 싶은 곳이라면 어디든지 가능합니다.약간 인위적인 예로, 소프트웨어 프로젝트의 10,000개 개정 목록이 있고 해당 프로젝트에 기여한 사람이 몇 명인지 알고 싶다고 가정해 보겠습니다.당신은 Set<string> 개정 목록을 반복하고 각 개정의 작성자를 세트에 추가합니다.반복이 끝나면 세트의 크기가 원하는 답이 됩니다.

HashSet은 IEnumerble 컬렉션에서 중복 요소를 제거하는 데 사용됩니다.예를 들어,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

해당 코드가 실행된 후 UniqueStrings는 {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"}를 보유합니다.

아마도 해시세트의 가장 일반적인 용도는 포함 여부를 확인하는 목록이 O( n) (및 O(log n)인 정렬된 집합).따라서 항목이 일부 목록에 포함되어 있는지 여부를 많이 확인하면 hahsset이 성능을 향상시킬 수 있습니다.그것들에 대해서만 반복한다면 큰 차이는 없을 것입니다(전체 세트에 대한 반복은 O(n)이며, 항목을 추가할 때 목록 및 해시 세트와 마찬가지로 약간 더 많은 오버헤드가 있습니다).

그리고 아니요, 집합을 인덱싱할 수 없습니다. 이는 집합이 순서가 지정되지 않기 때문에 어쨌든 의미가 없습니다.일부 항목을 추가하면 세트는 어느 것이 첫 번째인지, 어느 것이 두 번째인지 등을 기억하지 못합니다.

List<T> 주문된 정보 세트를 저장하는 데 사용됩니다.목록 요소의 상대적 순서를 알고 있으면 일정한 시간에 해당 요소에 액세스할 수 있습니다.그러나 목록에서 요소가 어디에 있는지 확인하거나 해당 요소가 목록에 존재하는지 확인하려면 조회 시간이 선형입니다.반면에, HashedSet<T> 저장된 데이터의 순서를 보장하지 않으며 결과적으로 해당 요소에 대한 지속적인 액세스 시간을 제공합니다.

이름에서 알 수 있듯이, HashedSet<T> 구현하는 데이터 구조입니다. 의미론 설정.데이터 구조는 집합 연산(예:Union, Difference, Intersect)는 기존 List 구현으로는 효율적으로 수행할 수 없습니다.

따라서 사용할 데이터 유형을 선택하는 것은 애플리케이션으로 무엇을 하려는지에 따라 달라집니다.컬렉션에서 요소의 순서가 어떻게 지정되는지 신경 쓰지 않고 열거하거나 존재 여부만 확인하려는 경우 다음을 사용하세요. HashSet<T>.그렇지 않으면 사용을 고려하십시오. List<T> 또는 다른 적절한 데이터 구조.

HashSet<T> .NET Framework의 데이터 구조로 다음을 나타낼 수 있습니다. 수학 세트 객체로서.이 경우 해시 코드( GetHashCode 각 항목의 결과) 집합 요소의 동등성을 비교합니다.

집합은 그 안에 포함된 동일한 요소가 한 번만 발생하도록 허용한다는 점에서 목록과 다릅니다. HashSet<T> 그냥 돌아올거야 false 두 번째 동일한 요소를 추가하려는 경우.실제로 요소 검색은 매우 빠릅니다(O(1) 시간), 내부 데이터 구조는 단순히 해시 테이블이기 때문입니다.

어떤 것을 사용해야 할지 고민된다면 List<T> 어디 HashSet<T> 적절하다는 것이 가장 큰 실수는 아니지만 컬렉션에 바람직하지 않은 중복 항목이 있는 경우 문제가 발생할 수 있습니다.게다가 조회(항목 검색)가 훨씬 더 효율적입니다. 이상적으로는 O(1) (완벽한 버킷팅을 위해) 대신 O(n) 시간 - 많은 시나리오에서 매우 중요합니다.

간단히 말해서 사전(또는 S가 T의 속성인 사전)을 사용하고 싶은 유혹을 느낄 때마다 HashSet(또는 HashSet + S와 동일하게 T에 IEquatable을 구현하는 것)을 고려해야 합니다.

기본 의도 시나리오에서 HashSet<T> LINQ가 제공하는 것보다 두 컬렉션에 대해 더 구체적인 집합 작업을 원할 때 사용해야 합니다.LINQ 메서드는 다음과 같습니다. Distinct, Union, Intersect 그리고 Except 대부분의 상황에서는 충분하지만 때로는 더 세밀한 작업이 필요할 수도 있습니다. HashSet<T> 다음을 제공합니다:

  • UnionWith
  • IntersectWith
  • ExceptWith
  • SymmetricExceptWith
  • Overlaps
  • IsSubsetOf
  • IsProperSubsetOf
  • IsSupersetOf
  • IsProperSubsetOf
  • SetEquals

LINQ와 LINQ의 또 다른 차이점 HashSet<T> "겹치는" 메서드는 LINQ가 항상 새 메서드를 반환한다는 것입니다. IEnumerable<T>, 그리고 HashSet<T> 메서드는 소스 컬렉션을 수정합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top