실행 가능한 C# 문서: HashSet

Q: C#에서 HashSet이란 무엇인가요?

HashSet 는 정해진 순서가 없는 고유한 항목들의 컬렉션입니다. 이미 있는 항목을 추가하면 아무 일도 일어나지 않고, 항목이 Dictionary의 키처럼 해시 코드로 저장되므로 Contains는 집합이 아무리 커도 거의 상수 시간에 답합니다.

Q: HashSet.Add는 무엇을 반환하나요?

Add는 항목이 추가되면 true를, 이미 집합에 있었으면 false를 반환합니다. 그래서 if (!seen.Add(x))는 한 줄짜리 중복 검사가 됩니다. 같은 호출로 새 항목을 추가하고 반복된 항목을 알려 줍니다.

Q: C#에서 List의 중복을 제거하려면 어떻게 하나요?

list.Distinct().ToList()는 중복이 없는 새 리스트를 반환하며, 각 항목의 첫 번째 등장을 원래 순서대로 유지합니다. new HashSet (list)도 중복을 제거하지만 집합에는 보장된 순서가 없습니다. 제자리에서 중복을 제거하려면 var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));를 쓰세요.

Q: 언제 List 대신 HashSet을 써야 하나요?

주로 "이 항목이 컬렉션에 있나?"를 묻거나 항목이 고유해야 할 때 HashSet 를 쓰세요. List .Contains는 모든 요소를 훑으므로 리스트가 커질수록 느려지지만, HashSet .Contains는 그렇지 않습니다. 순서, 중복, 인덱스 접근이 중요하면 List 를 쓰세요.

Q: HashSet에 중복 객체가 들어가는 이유는 무엇인가요?

클래스가 Equals와 GetHashCode를 재정의하지 않아서 집합이 참조를 비교하고, 필드 값이 같은 두 객체를 다르다고 보기 때문입니다. 두 메서드를 (항상 함께) 재정의하거나, 집합의 생성자에 IEqualityComparer 를 넘기세요.

HashSet<T>는 모든 항목이 최대 한 번만 나타나는 컬렉션입니다. 인덱스도 보장된 순서도 없는 대신, 포함 여부를 거의 상수 시간에 확인합니다. 백만 개 중에서 태그 하나를 찾는 데 열 개 중에서 찾는 것과 비슷한 시간이 걸립니다.

항목 추가하기: Add는 bool을 반환합니다

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

출력:

True
False
3
True
True
False
2

중복을 추가하는 것은 오류가 아닙니다. Add는 단순히 false를 반환하고 집합은 바뀌지 않습니다. 이 반환값이 이 메서드에서 가장 쓸모 있는 부분입니다. "이걸 본 적이 있나?"와 "기억해 두기"를 한 번의 호출로 합칩니다:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

출력:

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Contains가 빠른 이유

List<T>.Contains는 값을 각 요소와 차례로 비교하므로 비용이 리스트와 함께 늘어납니다. HashSet<T>는 항목의 해시 코드를 계산하고, 그 코드의 버킷으로 바로 가서, 거기 저장된 몇 개의 항목만 비교합니다. 루프 안의 포함 여부 검사라면 O(n) 단계가 O(1) 단계가 되고, 두 리스트에 대한 중첩 루프가 한 번의 순회가 됩니다:

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

집합을 만드는 데 리스트를 한 번 순회하는 비용이 들므로, 몇 번 이상 조회할 때만 이득입니다.

리스트에서 중복 제거하기

흔한 방법은 세 가지이며, 순서가 어떻게 되는지가 다릅니다:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

출력:

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

리스트를 돌려받고 싶을 때는 Distinct가 올바른 기본값입니다. 제자리 버전이 동작하는 이유는 RemoveAll이 요소마다 순서대로 한 번씩 조건자를 호출하기 때문입니다. 두 번째 이후 복사본에 대해 seen.Add가 false를 반환하므로 정확히 그것들이 제거됩니다.

집합 연산: 합집합, 교집합, 차집합

HashSet<T>에는 집합론의 연산이 있습니다. ...With 메서드는 호출 대상 집합을 바꾸고 아무것도 반환하지 않습니다.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

출력:

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

인수는 배열, 리스트, 다른 집합 등 어떤 IEnumerable<T>든 될 수 있습니다. SetEquals는 인수의 순서와 중복을 무시합니다. 집합의 열거 순서는 믿을 만한 것이 아니므로 Show 헬퍼는 출력하기 전에 정렬합니다.

LINQ에는 새 시퀀스를 반환하고 입력은 그대로 두는 대응 메서드가 있습니다: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). 집합을 바꾸고 싶지 않거나 입력이 리스트일 때 이것을 쓰세요.

직접 만든 클래스의 같음 비교

집합은 GetHashCode와 Equals로 "같은 항목"인지 판단합니다. 이를 재정의하지 않은 클래스에서는 둘 다 객체의 동일성에 기반하므로, 필드가 같은 두 객체는 서로 다른 두 항목입니다:

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

출력:

2
1
True

규칙: Equals로 같은 객체는 같은 GetHashCode를 반환해야 합니다. Equals만 재정의하면 집합이 엉뚱한 버킷을 찾아서 여전히 중복을 보고합니다. .NET Core 2.1 이상에서는 HashCode.Combine(X, Y)가 직접 계산식을 쓰지 않고도 좋은 해시 코드를 만들어 줍니다.

클래스를 바꿀 수 없거나 한 집합에만 다른 "같음" 개념이 필요하다면, 생성자에 IEqualityComparer<T>를 넘기세요. 문자열에는 미리 만들어진 비교자가 있습니다:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

출력:

True
False
2

C# 9 이상에서는 record가 값 기반 Equals와 GetHashCode를 생성해 주므로, record Point(int X, int Y);는 추가 코드 없이 집합에서 동작합니다.

객체가 집합에 있는 동안 GetHashCode에 쓰이는 필드를 절대 바꾸지 마세요. 객체가 예전 해시의 버킷에 남아 있어서 Contains와 Remove가 더 이상 찾지 못합니다.

순서와 SortedSet

HashSet<T>의 열거 순서는 임의로 취급해야 합니다. 항목을 정렬해야 한다면 출력할 때 정렬하거나(set.OrderBy(x => x)), 항목을 항상 정렬된 상태로 유지하고 연산마다 O(log n)으로 Min, Max, 범위 쿼리를 더해 주는 SortedSet<T>를 쓰세요:

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet과 List와 Dictionary

필요한 것	사용
고유한 항목, 빠른 "있나?"	`HashSet<T>`
고유한 항목, 항상 정렬됨	`SortedSet<T>`
순서, 중복, 인덱스 접근	`List<T>`
키마다 저장되는 값	`Dictionary<TKey, TValue>`

집합은 값 없이 키만 있는 딕셔너리입니다. 포함 여부만 추적하려고 Dictionary<string, bool>을 쓰고 있다면, HashSet<string>이 같은 것을 더 명확하게 말합니다.

흔한 실수

순서를 기대하기. 집합에는 믿을 만한 순서가 없습니다. 정렬하거나 SortedSet<T>를 쓰세요.
Equals와 GetHashCode 없는 사용자 정의 클래스. 같아 보이는 객체가 별개의 항목이 됩니다.
Equals만 재정의하기. 항상 GetHashCode도 함께 재정의하세요.
추가한 뒤 항목 바꾸기. 집합이 더 이상 찾지 못합니다.
집합에 인덱싱하기. set[0]은 컴파일되지 않습니다. 인덱스가 없습니다. 위치가 필요하면 ToList()로 변환하세요.

자주 묻는 질문

C#에서 HashSet이란 무엇인가요?

HashSet<T>는 정해진 순서가 없는 고유한 항목들의 컬렉션입니다. 이미 있는 항목을 추가하면 아무 일도 일어나지 않고, 항목이 Dictionary의 키처럼 해시 코드로 저장되므로 Contains는 집합이 아무리 커도 거의 상수 시간에 답합니다.

HashSet.Add는 무엇을 반환하나요?

Add는 항목이 추가되면 true를, 이미 집합에 있었으면 false를 반환합니다. 그래서 if (!seen.Add(x))는 한 줄짜리 중복 검사가 됩니다. 같은 호출로 새 항목을 추가하고 반복된 항목을 알려 줍니다.

C#에서 List의 중복을 제거하려면 어떻게 하나요?

list.Distinct().ToList()는 중복이 없는 새 리스트를 반환하며, 각 항목의 첫 번째 등장을 원래 순서대로 유지합니다. new HashSet<T>(list)도 중복을 제거하지만 집합에는 보장된 순서가 없습니다. 제자리에서 중복을 제거하려면 var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));를 쓰세요.

언제 List 대신 HashSet을 써야 하나요?

주로 "이 항목이 컬렉션에 있나?"를 묻거나 항목이 고유해야 할 때 HashSet<T>를 쓰세요. List<T>.Contains는 모든 요소를 훑으므로 리스트가 커질수록 느려지지만, HashSet<T>.Contains는 그렇지 않습니다. 순서, 중복, 인덱스 접근이 중요하면 List<T>를 쓰세요.

HashSet에 중복 객체가 들어가는 이유는 무엇인가요?

클래스가 Equals와 GetHashCode를 재정의하지 않아서 집합이 참조를 비교하고, 필드 값이 같은 두 객체를 다르다고 보기 때문입니다. 두 메서드를 (항상 함께) 재정의하거나, 집합의 생성자에 IEqualityComparer<T>를 넘기세요.