HashSet 은 중복을 받지 않는다

앞 글까지의 자료구조는 전부 무엇이 들어 있는가를 다뤘습니다. 그런데 값 자체보다 이미 있는지 없는지만 궁금할 때가 있습니다.

방문한 페이지, 이미 처리한 주문 번호, 중복 없이 모아야 하는 태그 같은 것들입니다.

List 로 하면 이렇게 됩니다.

List<string> visited = new List<string>();

if (!visited.Contains(url))
{
    visited.Add(url);
}

돌아가긴 합니다. 문제는 Contains 입니다. List 는 번호로만 곧장 찾을 수 있으니, 내용으로 찾으려면 앞에서부터 전부 비교합니다.

주소 1000개를 이렇게 넣으면, 마지막 하나를 넣을 때 앞의 999개를 전부 봅니다. 전체로 보면 50만 번쯤 비교하게 됩니다. 개수가 늘면 그 제곱으로 늘어납니다.

중복을 안 받고, 있는지 없는지를 곧장 답하는 것이 HashSet 입니다.

HashSet 은 이렇게 생겼다

using System.Collections.Generic;

HashSet<string> visited = new HashSet<string>();

visited.Add("a.com");
visited.Add("b.com");
visited.Add("a.com");        // 이미 있으니 안 들어갑니다

Console.WriteLine(visited.Count);            // 2
Console.WriteLine(visited.Contains("a.com"));  // True

꺾쇠 안이 하나입니다. 담을 타입만 적습니다. Dictionary 처럼 두 칸이 아닙니다. 값이 없으니까요.

같은 것을 두 번 넣어도 에러가 아닙니다. 그냥 안 들어갑니다.

칸을 계산하고, 그 칸 안에서 비교하고, 같으면 안 넣습니다. 같은 칸에 왔다고 같은 값은 아닙니다. 그래서 비교가 최종 판단을 합니다.

Add 가 넣었는지 여부를 돌려주기 때문에, 앞의 코드를 이렇게 줄일 수 있습니다.

if (visited.Add(url))
{
    // 처음 보는 주소일 때만 여기로 옵니다
}

확인과 넣기가 한 번에 끝납니다. Dictionary 의 TryGetValue 에서 본 것과 같은 모양입니다. 실패할 수 있는 일은 성공 여부를 돌려준다, 이 방식이 자료구조 전반에 반복됩니다.

값을 뗀 Dictionary 다

어떻게 곧장 찾을까요. 앞 글에서 이미 봤습니다.

Dictionary 는 키를 해시로 숫자를 만들고 그 숫자로 칸을 정했습니다. HashSet 은 거기서 값 칸만 뗀 것입니다. 키만 남습니다.

그래서 성질이 그대로 따라옵니다. 몇 개가 들어 있든 확인하는 시간이 거의 같고, 넣은 순서는 지켜지지 않습니다.

중복 제거에 그대로 쓴다

같은 값이 여러 번 있는 목록에서 중복을 빼는 일이 자주 있습니다. HashSet 에 넣었다 빼면 끝입니다.

List<int> nums = new List<int> { 3, 1, 3, 2, 1 };

HashSet<int> unique = new HashSet<int>(nums);

Console.WriteLine(unique.Count);    // 3

만들 때 목록을 통째로 넘길 수 있습니다. 중복은 알아서 빠집니다.

다만 순서가 사라진다는 것을 기억해야 합니다. 원래 순서를 지키면서 중복만 빼려면 HashSet 을 확인용으로만 쓰고 결과는 List 에 따로 담습니다.

List<int> result = new List<int>();
HashSet<int> seen = new HashSet<int>();

for (int i = 0; i < nums.Count; i++)
{
    if (seen.Add(nums[i]))
    {
        result.Add(nums[i]);
    }
}

seen 은 답이 아니라 판단하는 도구입니다. 답은 result 에 쌓입니다. 자료구조 두 개를 같이 쓰는 흔한 모양입니다.

집합끼리 묶고 자른다

HashSet 은 수학의 집합에 해당합니다. 그래서 집합 연산이 있습니다.

HashSet<string> a = new HashSet<string> { "검", "방패", "포션" };
HashSet<string> b = new HashSet<string> { "포션", "활" };

a.UnionWith(b);        // 합집합: 검, 방패, 포션, 활
a.IntersectWith(b);    // 교집합: 둘 다에 있는 것만 남긴다
a.ExceptWith(b);       // 차집합: b 에 있는 것을 뺀다

이름 끝의 With 를 봐 두세요. 자기 자신이 바뀝니다. 앞에서 문자열 메서드는 원본을 두고 새 값을 돌려준다고 했는데, 여기는 반대입니다. 결과를 받아 적는 게 아니라 a 가 그 자리에서 변합니다.

한 줄로 여러 개를 이어 쓰면 안 되는 이유가 이겁니다. a.UnionWith(b) 를 하고 나면 a 는 이미 원래 a 가 아닙니다.

무엇으로 같다고 볼 것인가

HashSet 은 해시로 자리를 정하고, 같은 자리에 온 것끼리 같은지 비교합니다. 그러니 무엇을 같다고 볼지가 정해져 있어야 합니다.

숫자와 문자열은 걱정할 게 없습니다. 값이 같으면 같습니다.

HashSet<string> s = new HashSet<string> { "포션", "포션" };
Console.WriteLine(s.Count);    // 1

직접 만든 타입을 담으면 이야기가 달라집니다. 아무것도 안 하면 내용이 같아도 다른 것으로 봅니다. 같다고 볼 값은 같은 해시를 내놓아야 같은 칸으로 가는데, 아무것도 안 하면 그게 보장되지 않습니다. 내가 만든 타입을 담을 생각이면 Equals 와 GetHashCode 를 같이 손봐야 합니다.

정리

• HashSet 은 같은 값을 두 번 담지 않습니다. 두 번 넣어도 에러 없이 무시됩니다.
• Dictionary 에서 값을 떼고 키만 남긴 것입니다. 찾는 방식이 같습니다.
• 그래서 몇 개가 들어 있든 Contains 가 곧장 답합니다. List 는 전부 훑습니다.
• Add 가 넣었는지를 돌려줍니다. 확인과 넣기를 한 번에 합니다.
• 순서는 지켜지지 않습니다. 순서가 필요하면 List 와 같이 씁니다.
• UnionWith 계열은 새 집합을 돌려주는 게 아니라 자기 자신을 바꿉니다.