[PART9.컬렉션 기본 사용법(3/8)] HashSet<T> — 중복 없는 집합, Add 한 번으로 끝내는 이유
왜 List.Contains+Add 패턴이 위험한가 / Contains가 O(1)인 메커니즘 / 집합 연산으로 태그·플래그를 다루는 법
목차
문제 제기 — "중복만 거르면 되는데 왜 게임이 끊기는가"
Unity 신입이 처음 작성하는 인벤토리 코드, 파티 가입 코드, 한 프레임 내 충돌 처리 코드는 거의 같은 모양이다. "이미 있으면 무시하고, 없으면 넣는다."
// Unity에서 흔히 보는 코드 — 한 프레임에 같은 적과 여러 번 충돌해도 데미지는 한 번만
private List<Collider> _hitThisFrame = new();
void OnTriggerEnter(Collider other)
{
if (!_hitThisFrame.Contains(other)) // ← (1) O(n) 선형 탐색
{
_hitThisFrame.Add(other); // ← (2) 추가
ApplyDamage(other);
}
}코드는 분명히 동작한다. 적이 5마리, 10마리일 때는 아무 문제도 없다. 그러나 보스전에서 폭발 이펙트가 터지고 한 프레임에 콜라이더가 80개 들어오기 시작하면, 위 Contains 호출이 매 호출마다 0~79개 항목을 모두 비교하기 시작한다. 80개 항목을 처리하려면 평균 80 × 40 = 3200회의 참조 비교가 일어난다. Unity 프로파일러에서는 이 한 줄이 한 프레임에서 GC 스파이크 없이도 수 밀리초를 갉아먹는 함수로 잡힌다.
"그냥 Contains를 안 쓰면 되지 않나?" 그렇다. 그래서 C#에는 중복 검사와 추가를 한 번의 O(1) 연산으로 처리하는 자료구조가 별도로 있다. HashSet<T>다. 이 글은 그 한 번의 연산이 어떻게 가능한지, 어떤 비용을 지불하고 어떤 함정을 피해야 하는지를 본다.
개념 정의 — "값을 저장하지 않는 사전"
비유: 회원 명단 vs 회원 카드 박스
List<T>가 번호표 순서대로 줄 세운 회원 명단이라면, HashSet<T>는 회원 ID로 칸이 정해진 회원 카드 박스다. 어떤 회원이 가입했는지 확인하려면
- List는 1번부터 끝까지 한 명씩 이름을 비교해야 한다 — O(n)
- HashSet은 "ID 35번"이라는 정보만으로 35번 칸을 직접 열어 확인한다 — O(1)
대신 HashSet은 순서를 보장하지 않는다. 박스 안의 칸 번호는 ID에서 계산된 것이지, 가입 순서가 아니다.
구조 한눈에
가장 단순한 사용
using System.Collections.Generic;
var visited = new HashSet<int>();
bool wasNew = visited.Add(42); // true — 새로 추가됨
bool wasNew2 = visited.Add(42); // false — 이미 있어서 무시됨
bool exists = visited.Contains(42); // true
visited.Remove(42); // 제거HashSet<T>— 해시 기반 집합 (Hash Set) 중복을 허용하지 않고, 순서가 없으며,Add/Remove/Contains가 모두 평균 O(1)인 컬렉션이다. 내부적으로는 값(Value) 슬롯이 없는 해시 테이블이다.
예시:var s = new HashSet<int> { 1, 2, 3 };s.Add(1)은false를 반환한다.
Add의 두 번째 호출이 예외를 던지지 않는다. 단지 false를 반환할 뿐이다. 이 한 가지 사실이 글 전체에서 가장 중요한 차이점이다 — 중복 체크와 추가가 한 번의 메서드 호출에 합쳐져 있다는 뜻이다.
기술 정의로 옮기면, HashSet<T> 는 System.Collections.Generic 네임스페이스에 정의된 제네릭 컬렉션으로, ISet<T> 인터페이스를 구현하고 평균 O(1) 시간복잡도로 멤버십 검사·삽입·삭제를 수행한다. 검사 키는 IEqualityComparer<T> 가 결정하며, 기본값은 EqualityComparer<T>.Default 다.
내부 동작 — Dictionary와 같은 엔진, 다른 외관
핵심 통찰: HashSet은 "값 슬롯이 없는 Dictionary"
이 한 줄이 HashSet의 모든 것을 설명한다. Dictionary<TKey, TValue> 와 HashSet<T> 는 동일한 해시 테이블 알고리즘을 공유하며, 단지 Dictionary가 키마다 값을 함께 저장하는 반면 HashSet은 키만 저장한다.
이 구조 덕분에 Dictionary 글에서 다룬 모든 내부 동작 — buckets 배열, 해시 충돌 시 체이닝, 로드 팩터 초과 시 리해싱, 소수(prime) 크기 사용 — 이 그대로 적용된다.
Add가 왜 O(1)인가 — IL로 보는 호출 횟수
Before: List.Contains + Add (호출 2회)
Unity에서 흔히 쓰는 "이미 있으면 무시" 패턴이다.
public static void ListContainsAdd(List<int> list, int item)
{
if (!list.Contains(item))
{
list.Add(item);
}
}.method public hidebysig static
void ListContainsAdd (List`1<int32> list, int32 item) cil managed
{
.maxstack 8
IL_0000: ldarg.0 // list
IL_0001: ldarg.1 // item
IL_0002: callvirt instance bool List`1<int32>::Contains(!0) // ← O(n) 선형 탐색
IL_0007: brtrue.s IL_0010 // 있으면 점프
IL_0009: ldarg.0
IL_000a: ldarg.1
IL_000b: callvirt instance void List`1<int32>::Add(!0) // ← 다시 호출
IL_0010: ret
}callvirt 가 두 번 보인다. 첫 번째는 O(n) 검색, 두 번째는 O(1) 추가. List 크기가 커지면 첫 번째 호출의 비용이 선형으로 늘어난다.
After: HashSet.Add (호출 1회)
public static bool HashSetAdd(HashSet<int> set, int item)
{
return set.Add(item);
}.method public hidebysig static
bool HashSetAdd (HashSet`1<int32> set, int32 item) cil managed
{
.maxstack 8
IL_0000: ldarg.0 // set
IL_0001: ldarg.1 // item
IL_0002: callvirt instance bool HashSet`1<int32>::Add(!0) // ← 단 한 번
IL_0007: ret
}callvirt 가 한 번이다. 그리고 그 한 번의 호출 안에서 — 해시 계산, 버킷 인덱스 계산, 체인 탐색, 삽입 결정이 모두 O(1) 평균 시간에 끝난다. 반환된 bool 이 곧 "새로 추가됐는가" 의 답이다. 따로 Contains를 부를 필요가 없다.
Contains의 O(1) 메커니즘
HashSet.Contains(key) 가 어떻게 단 몇 번의 명령으로 답을 돌려주는지는 다음 4단계로 요약된다.
key.GetHashCode()를 호출해 32비트 해시 코드를 얻는다bucketIndex = hashCode % buckets.Length로 버킷 인덱스를 구한다buckets[bucketIndex]가 가리키는 슬롯부터 시작해next체인을 따라간다- 각 슬롯에서
comparer.Equals(slot.value, key)로 동등성을 비교, 일치하면 true
해시 분포가 고르면 3번의 체인 길이는 평균 1~2 — 그래서 평균 O(1) 이다. 충돌이 심하면 최악의 경우 O(n) 까지 갈 수 있다는 점을 기억해야 한다.
public static bool HashSetContains(HashSet<string> set, string key)
{
return set.Contains(key);
}IL_0000: ldarg.0
IL_0001: ldarg.1
IL_0002: callvirt instance bool HashSet`1<string>::Contains(!0)
IL_0007: retIL 자체는 단순하다 — 호출 한 번이다. 진짜 동작은 HashSet.Contains 내부에서 위 4단계로 펼쳐진다. JIT 컴파일러는 이 호출을 인라이닝하지 않는 경우가 많지만(메서드가 충분히 작지 않다), 호출 비용은 일정하다.
실전 적용 — 한 번 호출로 끝내는 패턴
Before/After: 한 프레임 중복 처리 방지
문제 제기에서 본 코드를 HashSet으로 바꾼다.
Before — List.Contains + Add (O(n))
private List<Collider> _hitThisFrame = new();
void OnTriggerEnter(Collider other)
{
if (!_hitThisFrame.Contains(other)) // ← O(n)
{
_hitThisFrame.Add(other);
ApplyDamage(other);
}
}// Contains 호출 후 분기, 다시 Add 호출 — callvirt 2회
callvirt List`1::Contains // O(n)
brtrue.s
callvirt List`1::AddAfter — HashSet.Add 의 bool 반환 활용 (O(1))
private HashSet<Collider> _hitThisFrame = new();
void OnTriggerEnter(Collider other)
{
if (_hitThisFrame.Add(other)) // ← O(1), 새로 추가된 경우에만 true
{
ApplyDamage(other);
}
}// Add 한 번으로 검사 + 추가 + 결과 반환
callvirt HashSet`1::Add // O(1)
brfalse.s콜라이더가 80개 들어와도 비교 횟수는 80번에 그친다. List 버전은 평균 80 × 40 = 3200번이었다. 40배 차이가 한 줄 변경에서 나온다.
추가로, 매 프레임 끝에 _hitThisFrame.Clear() 를 호출하는 것을 잊지 않아야 한다. Clear는 O(n)이지만 1회성이다.
집합 연산 — 태그/플래그 관리
HashSet<T> 의 진짜 위력은 수학적 집합 연산이 메서드 한 번으로 끝난다는 점이다. Unity에서 캐릭터의 상태 태그를 관리하는 코드를 보자.
public static void SetOps(HashSet<int> a, HashSet<int> b)
{
a.UnionWith(b); // 합집합 — a = a ∪ b
a.IntersectWith(b); // 교집합 — a = a ∩ b
a.ExceptWith(b); // 차집합 — a = a − b
}.method public hidebysig static
void SetOps (HashSet`1<int32> a, HashSet`1<int32> b) cil managed
{
IL_0002: callvirt instance void HashSet`1<int32>::UnionWith(IEnumerable`1<!0>)
IL_0009: callvirt instance void HashSet`1<int32>::IntersectWith(IEnumerable`1<!0>)
IL_0010: callvirt instance void HashSet`1<int32>::ExceptWith(IEnumerable`1<!0>)
IL_0015: ret
}세 메서드 모두 인자 타입이 IEnumerable<T> 다 — 다른 HashSet, List, 배열, LINQ 결과 무엇이든 받는다.
Unity 적용 예: 플레이어가 가진 능력 태그와 적의 면역 태그가 있을 때 "효과를 받는 능력만 남기기" 는 교집합으로 한 줄이다.
public class Character : MonoBehaviour
{
private HashSet<string> _abilities = new() { "Fire", "Ice", "Stun", "Poison" };
private HashSet<string> _enemyImmunities = new() { "Fire", "Stun" };
public HashSet<string> GetEffectiveAbilities()
{
var effective = new HashSet<string>(_abilities);
effective.ExceptWith(_enemyImmunities); // 면역되는 능력 제거
return effective; // { "Ice", "Poison" }
}
}같은 일을 List로 하려면 이중 루프가 필요하다 — 코드 길이도 길고 O(n × m) 이다. HashSet의 ExceptWith는 b를 한 번 순회하며 a에서 O(1) 제거하므로 O(m) 이다.
IEqualityComparer 주입 — 대소문자 무시 집합
문자열 집합에서 "Apple" 과 "apple" 을 같은 항목으로 취급해야 할 때, 생성자에 비교자를 주입한다.
public static HashSet<string> CaseInsensitiveSet()
{
return new HashSet<string>(StringComparer.OrdinalIgnoreCase);
}.method public hidebysig static
HashSet`1<string> CaseInsensitiveSet () cil managed
{
IL_0000: call class StringComparer::get_OrdinalIgnoreCase()
IL_0005: newobj instance void HashSet`1<string>::.ctor(IEqualityComparer`1<!0>)
IL_000a: ret
}StringComparer.OrdinalIgnoreCase 는 정적 프로퍼티 한 번 읽기로 끝나며 — 매번 새 인스턴스를 만들지 않는다. 이 비교자는 GetHashCode 를 호출할 때 대소문자를 무시한 해시를 계산하므로, "Apple" 과 "apple" 이 같은 버킷에 들어간다.
var tags = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
tags.Add("Player"); // true
tags.Add("PLAYER"); // false — 같은 항목으로 인식
tags.Contains("player"); // true도메인 객체에 대해서도 같은 패턴이 작동한다. IEqualityComparer<Item> 을 직접 구현해 "ID가 같으면 같은 아이템" 같은 규칙을 외부에서 주입할 수 있다.
IEqualityComparer<T>— 동등성 비교자 인터페이스 두 객체가 같은지(Equals)와 해시 코드를 어떻게 계산할지(GetHashCode)를 외부에서 정의하는 인터페이스다. HashSet/Dictionary 생성자에 넘기면 기본 비교 대신 이 규칙이 사용된다.
예시:new HashSet<Item>(new ItemByIdComparer());ItemByIdComparer가 정의한 규칙으로 중복을 판별
함정과 주의사항
함정 1: GetHashCode와 Equals의 계약 위반
해시 기반 컬렉션이 동작하는 전제는 단 하나다. a.Equals(b) == true 이면 반드시 a.GetHashCode() == b.GetHashCode() 다. 이 규칙을 어기면 HashSet 안에 같은 객체가 두 개 들어갈 수 있다 — 그러나 어느 쪽도 찾을 수 없다.
❌ 잘못된 패턴 — Equals만 오버라이드, GetHashCode는 그대로
public class Item
{
public int Id;
public override bool Equals(object obj)
{
return obj is Item other && other.Id == Id;
}
// ⚠️ GetHashCode 오버라이드 없음 — Object.GetHashCode 가 그대로 사용됨
}
var set = new HashSet<Item>();
set.Add(new Item { Id = 1 });
set.Add(new Item { Id = 1 }); // ← true 반환 — 중복이 들어감
Console.WriteLine(set.Count); // 2Object.GetHashCode 는 객체의 메모리 식별자에 기반한 값을 돌려준다. 두 Item 인스턴스는 메모리 주소가 다르므로 해시도 다르고, 다른 버킷에 들어간다. HashSet은 버킷이 다르면 Equals를 부르지 않으므로 중복임을 알아채지 못한다.
✅ 올바른 패턴 — 둘 다 오버라이드
public class Item
{
public int Id;
public override bool Equals(object obj)
=> obj is Item other && other.Id == Id;
public override int GetHashCode()
=> Id.GetHashCode();
}이제 같은 Id를 가진 두 인스턴스는 같은 해시 → 같은 버킷 → Equals 호출 → 중복 판정. set.Count 는 1이다.
record 또는 record struct 를 쓰면 컴파일러가 두 메서드를 자동으로 만들어준다 — 도메인 키 객체를 만들 때 가장 안전한 방법이다.
함정 2: 가변 키를 넣고 변경하기
GetHashCode/Equals 를 올바르게 구현해도, HashSet에 넣은 후 키 필드를 변경하면 객체가 미아가 된다.
❌ 잘못된 패턴
var item = new Item { Id = 1 };
var set = new HashSet<Item>();
set.Add(item);
Console.WriteLine(set.Contains(item)); // true
item.Id = 2; // ← 해시가 달라지는 필드를 변경
Console.WriteLine(set.Contains(item)); // false — 자기 자신을 찾지 못함객체는 여전히 set 안에 있지만, 새 해시(2.GetHashCode())로 계산한 버킷에는 아무것도 없다. 원래 들어갔던 버킷에는 item 이 있지만 — 그 버킷을 찾으려면 옛 해시를 알아야 한다. 결과적으로 컬렉션 안에서 잃어버린 객체가 된다.
✅ 올바른 패턴: 키 필드는 불변
public sealed class Item
{
public int Id { get; } // get-only — 생성 후 변경 불가
public Item(int id) => Id = id;
public override bool Equals(object obj) => obj is Item o && o.Id == Id;
public override int GetHashCode() => Id.GetHashCode();
}record 를 쓰면 모든 위치 매개변수가 자동으로 init-only가 되고 키 변경이 컴파일 시점에 막힌다.
함정 3: 순서를 가정하기
HashSet은 순서를 보장하지 않는다. 추가 순서도, 정렬 순서도, "특정 구현이 항상 같은 순서" 도 약속하지 않는다.
❌ 잘못된 패턴
var set = new HashSet<int> { 3, 1, 2 };
foreach (var x in set)
Console.WriteLine(x); // ← 어떤 순서로 나올지 모름. 1, 2, 3 일 수도, 3, 1, 2 일 수도Unity에서 종종 HashSet으로 적 리스트를 관리하다 "왜 가끔 표시 순서가 바뀌지?" 라는 버그를 만난다. 답은 — 원래 순서가 없기 때문이다.
✅ 순서가 필요하면 별도 컬렉션 사용
// 순서가 의미 있고, 중복도 막고 싶다 → List + HashSet 조합
var ordered = new List<int>();
var seen = new HashSet<int>();
foreach (var x in input)
if (seen.Add(x)) // O(1) 중복 검사
ordered.Add(x); // 순서 유지
// 또는 정렬된 집합이 필요하면 → SortedSet<T> (트리 기반, O(log n))
var sorted = new SortedSet<int> { 3, 1, 2 }; // 1, 2, 3 순회함정 4: enum HashSet 의 박싱 (과거 .NET Framework)
이 함정은 .NET Framework / .NET Core 2.0 이하에서만 발생한다. Unity Mono 백엔드에서는 여전히 주의가 필요하다.
public enum Tag { Player, Enemy, NPC }
public static bool EnumHashSet(HashSet<Tag> set, Tag t)
{
return set.Contains(t);
}IL_0000: ldarg.0
IL_0001: ldarg.1
IL_0002: callvirt instance bool HashSet`1<valuetype Program/Tag>::Contains(!0)
IL_0007: retIL을 보면 box 명령이 없다 — 호출 측에서는 박싱이 발생하지 않는다. 문제는 HashSet.Contains 내부에서 일어난다.
- .NET Framework / .NET Core 2.0 이하:
EqualityComparer<TEnum>.Default가 enum을 처리할 때 내부에서Object로 박싱했다. 매 Contains 호출마다 enum이 힙에 박싱되며 GC 압박을 만들었다. - .NET Core 2.1 이후 (.NET 5/6/7/8/9 포함): 런타임이 enum 전용 비교자(
EnumEqualityComparer<TEnum>)를 자동 선택하여 박싱이 사라졌다. - Unity IL2CPP: AOT 컴파일이라 박싱 동작이 다소 다르지만, 대용량 enum HashSet의 핫패스에서는 명시적 비교자 주입이 가장 안전하다.
✅ 안전한 패턴: 명시적 비교자 주입 (모든 환경에서 박싱 없음)
// 직접 작성하거나 Microsoft.Extensions.Primitives 등의 헬퍼 사용
public sealed class TagComparer : IEqualityComparer<Tag>
{
public bool Equals(Tag x, Tag y) => x == y;
public int GetHashCode(Tag obj) => (int)obj;
}
var tags = new HashSet<Tag>(new TagComparer());이러면 런타임이 무엇이든 박싱 없이 동작한다. 핫패스가 아니라면 굳이 작성할 필요는 없다 — 일반적인 .NET 5+ 환경에서는 기본 비교자가 이미 박싱하지 않는다.
C# 버전별 변화
HashSet<T> 자체는 .NET Framework 3.5 / C# 3.0 에 도입되었고, 이후 큰 API 변화는 없었다. 다만 컬렉션 초기화·비교자 주입·성능 영역에서 의미 있는 개선이 있었다.
C# 3.0 (.NET 3.5) — 등장과 컬렉션 이니셜라이저
처음부터 컬렉션 이니셜라이저를 지원했다.
var set = new HashSet<int> { 1, 2, 3 };내부적으로는 Add 를 세 번 호출하는 코드로 변환된다.
C# 7+ (.NET Core 2.0) — 생성자 오버로드 보강
// 용량을 미리 지정해 리해싱 비용 회피
var set = new HashSet<int>(capacity: 1024);
// IEnumerable 로부터 초기화하면서 비교자도 지정
var ci = new HashSet<string>(initialItems, StringComparer.OrdinalIgnoreCase);용량을 미리 지정하면 내부 배열이 한 번에 충분한 크기로 할당되어, 추가 도중 리해싱이 일어나지 않는다. Unity에서 한 프레임에 수백 개를 넣어야 한다면 의미 있는 최적화다.
.NET Core 2.1 — enum 박싱 제거
위 함정 4 에서 다룬 변화. 코드는 그대로지만, 같은 코드를 .NET Framework 4.x 에서 돌릴 때와 .NET 5+ 에서 돌릴 때 GC 동작이 달라진다.
// .NET Framework 4.x: 매 호출마다 Tag 가 박싱 — GC 발생
// .NET 5+: 박싱 없음
public bool HasTag(HashSet<Tag> set, Tag t) => set.Contains(t);C# 12 (.NET 8) — 컬렉션 식
// C# 11 이전
HashSet<int> a = new HashSet<int> { 1, 2, 3 };
// C# 12 — 컬렉션 식 (collection expression)
HashSet<int> b = [1, 2, 3];대상 타입에 맞춰 컴파일러가 적절한 컬렉션을 만들어준다. HashSet에 대해서도 동일하게 동작한다.
정리 — HashSet 체크리스트
이것만 기억하면 된다:
- [ ] "중복을 막는 게 목적이다" 는 순간 HashSet을 떠올린다. List.Contains+Add 패턴은 항상 의심 대상이다.
- [ ]
Add의 bool 반환값을 활용하라.if (set.Add(x)) { ... }한 줄이 검사+추가+반응을 한 번에 처리한다. - [ ] Contains 가 O(1)인 이유는 해시 → 버킷 → 짧은 체인 탐색 이다. 평균 O(1) 이지, 보장된 O(1) 이 아니다.
- [ ] HashSet 은 Dictionary 의 값 슬롯이 빠진 형태. 내부 동작·함정·성능 특성이 같다.
- [ ] 사용자 정의 타입을 키로 쓸 때는
Equals와GetHashCode를 쌍으로 오버라이드. record 사용이 가장 안전하다. - [ ] 키 필드는 불변으로 유지하라. 컬렉션에 넣은 뒤 변경하면 객체가 미아가 된다.
- [ ] 순서가 필요하면 List+HashSet 조합 또는 SortedSet 을 쓴다. HashSet 자체는 순서를 약속하지 않는다.
- [ ] 집합 연산(
UnionWith/IntersectWith/ExceptWith) 은 List에서 이중 루프로 짜야 할 코드를 한 줄로 압축한다. Unity 태그/플래그 관리에 적극 활용한다. - [ ] 대소문자 무시·도메인 키 비교는
IEqualityComparer<T>주입으로 해결한다.StringComparer.OrdinalIgnoreCase가 문자열 집합의 표준 도구다. - [ ] enum HashSet 은 .NET 5+ 에서는 박싱이 없지만, Unity Mono 핫패스에서는 명시적 비교자 주입이 안전하다.