[C#][자료구조] HashSet<T>

✅ HashSet<T>

📌 HashSet이란?

HashSet<T>는 중복 없는 요소만 저장하는 집합(Set) 컬렉션입니다. 내부적으로 해시 테이블(Hash Table)을 사용하여 삽입/삭제/검색이 평균적으로 O(1)로 매우 빠릅니다.

즉, 리스트(List)와 달리 같은 값은 두 번 들어갈 수 없고, 집합 연산(합집합, 교집합, 차집합)을 지원한다는 점이 특징입니다.

📌 HashSet은 언제 사용될까?

• 데이터 중복을 허용하지 않아야 할 때
• 빠른 검색과 삽입/삭제가 필요할 때
• 집합 연산(Union, Intersect, Except)을 활용할 때
• 고유 ID, 태그, 방문 여부 체크(예: 그래프 탐색)

📊 기본 연산과 시간 복잡도

연산	설명	평균 시간 복잡도
Add	요소 추가 (중복 시 false 반환)	O(1)
Remove	특정 요소 제거	O(1)
Contains	특정 값 존재 여부 확인	O(1)
UnionWith	합집합	O(M+N)
IntersectWith	교집합	O(M+N)
ExceptWith	차집합	O(M+N)

* M, N은 각각 두 집합의 원소 개수입니다.

✅ C#에서의 HashSet

📌 기본 사용법

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var set = new HashSet();

        // 추가
        set.Add(1);
        set.Add(2);
        set.Add(2); // 중복 -> 무시됨

        Console.WriteLine(string.Join(", ", set)); // 1, 2

        // 검색
        Console.WriteLine(set.Contains(1)); // True
        Console.WriteLine(set.Contains(3)); // False

        // 삭제
        set.Remove(1);
        Console.WriteLine(string.Join(", ", set)); // 2

        // 집합 연산
        var a = new HashSet {1, 2, 3};
        var b = new HashSet {3, 4, 5};

        a.UnionWith(b);        // 합집합 {1,2,3,4,5}
        a.IntersectWith(b);    // 교집합 {3,4,5}
        a.ExceptWith(b);       // 차집합 {}
    }
}

📌 HashSet vs List vs Dictionary

구분	List<T>	HashSet<T>	Dictionary<TKey,TValue>
중복 허용	✅	❌	Key 기준 ❌
검색 속도	O(N)	O(1)	O(1)
순서 보장	삽입 순서 유지	❌	❌
데이터 구조	동적 배열	해시 테이블	해시 테이블

📝 정리

• HashSet<T>는 중복 없는 집합 자료구조
• 삽입/삭제/검색 평균 O(1)
• 집합 연산(합집합, 교집합, 차집합) 지원
• 순서가 중요한 경우에는 적합하지 않음
• 고유 데이터 관리, 빠른 검색에 유리