핵심 정리
csharp
var tags = new HashSet<string> { "csharp", "dotnet", "linq" };
tags.Add("async");
tags.Add("csharp"); // 이미 존재 → 무시, 중복 없음
bool has = tags.Contains("linq"); // O(1)
Console.WriteLine(tags.Count); // 4문법
왜 Contains가 O(1) 인가
HashSet<T>도 내부적으로 해시 테이블을 씁니다. Contains("csharp")를 호출하면 문자열의 해시코드를 계산해 해당 버킷만 확인합니다. List<T>.Contains()가 처음부터 끝까지 순회(O(n))하는 것과 대조적입니다.
csharp
// 방문 기록 관리: 수만 개여도 Contains가 빠름
var visited = new HashSet<int>();
foreach (int nodeId in graph.Nodes)
{
if (visited.Contains(nodeId)) continue;
visited.Add(nodeId);
// 처리
}집합 연산
수학적 집합 연산을 직접 제공합니다. 원본이 수정된다는 점에 유의해야 합니다.
csharp
var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };
a.UnionWith(b); // a = {1,2,3,4,5,6} 합집합
a.IntersectWith(b); // a = {3,4} 교집합
a.ExceptWith(b); // a = {1,2} 차집합 (a에만 있는 것)
// 원본 유지가 필요하면 복사 후 연산
var union = new HashSet<int>(a);
union.UnionWith(b);
// 관계 확인 (원본 변경 없음)
a.IsSubsetOf(b); // a ⊆ b
a.IsSupersetOf(b); // a ⊇ b
a.Overlaps(b); // 공통 원소 존재 여부커스텀 비교
참조 타입을 담을 때 GetHashCode와 Equals가 올바르게 구현되어 있지 않으면 중복 제거가 제대로 안 됩니다. IEqualityComparer<T>를 생성자에 전달해 비교 방식을 직접 지정할 수 있습니다.
csharp
// 대소문자 구분 없이 문자열 집합
var caseInsensitive = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
caseInsensitive.Add("Hello");
caseInsensitive.Add("hello"); // 중복으로 인식, Count = 1빠른 비교
HashSet<T> | List<T> | SortedSet<T> | |
|---|---|---|---|
| Contains | O(1) | O(n) | O(log n) |
| Add | O(1) | O(1) amortized | O(log n) |
| 순서 보장 | ❌ | ✅ 삽입 순서 | ✅ 정렬 순서 |
| 중복 | 불가 | 가능 | 불가 |
| 집합 연산 | ✅ | ❌ | ✅ |
| 잘 맞는 상황 | 빠른 포함 검사, 중복 제거 | 인덱스 접근, 순서 유지 | 정렬된 집합 필요 시 |
주의할 점
HashSet<T>는 삽입 순서를 보장하지 않습니다. 순서가 중요한 데이터에 쓰면 예상치 못한 결과가 나올 수 있습니다.
UnionWith, IntersectWith 등 집합 연산 메서드는 호출한 인스턴스를 직접 수정합니다. 원본을 보존해야 한다면 새 HashSet<T>를 만들어 복사한 뒤 연산하세요.
참고 링크
2 sources