Unity 개발자를 위한 C# HashSet(해시셋) 구현

HashSet(해시셋)은 다양한 프로그래밍 환경에서 반복적으로 등장하는 기본 자료구조입니다. 값의 순서보다는 “이 값이 들어 있냐, 없냐”를 빠르게 판별하는 데 특화되어 있으며, 같은 값을 두 번 넣더라도 한 번만 저장된다는 점이 가장 큰 특징입니다.

 

이번 글에서는 HashSet의 개념과 특징을 정리하고, C# 배열과 연결 리스트를 이용해 직접 구현한 뒤, Unity에서 간단한 테스트 코드를 통해 동작을 확인해 보겠습니다.

 

※  해시(hash)는 원래 “잘게 자르다, 뒤섞다”라는 뜻을 가진 단어로, 여러 데이터를 섞어서 전혀 다른 형태로 만드는 것을 의미합니다. 컴퓨터 과학에서는 이 개념이 확장되어, 크기가 제각각인 데이터(문자열, 파일 등)를 고정된 크기의 정수 값으로 변환하는 과정을 해시라고 부릅니다. 이때 사용되는 함수를 해시 함수(Hash Function)라 하고, 그 결과를 해시코드(Hash Code)라고 합니다. HashSet에서는 이 해시코드를 이용해 “이 값이 어느 버킷에 들어갈지”를 빠르게 결정하여 탐색 속도를 높입니다.

---

1. HashSet의 구조와 동작 방식

HashSet은 중복을 허용하지 않는 집합(Set) 자료구조입니다. 핵심은 “값의 존재 여부를 빠르게 확인한다”는 점입니다. 특정 값이 이미 들어 있는지 알고 싶을 때, 매번 처음부터 끝까지 순회(List 탐색)를 하는 대신, 해시 함수를 사용해 바로 해당 값이 들어 있을 법한 위치를 찾아갑니다.

 

내부 구조는 크게 세 부분으로 나뉩니다.

• 값에서 정수 해시코드를 만들어 주는 해시 함수
• 해시코드로 접근하는 버킷(bucket) 배열
• 같은 버킷에 몰린 값들을 이어 붙이는 연결 리스트(Node 체이닝)

먼저 값에서 해시코드를 계산한 뒤, 버킷 개수로 나눈 나머지를 사용해 인덱스를 구합니다. 이 인덱스가 “이 값이 들어 있을 가능성이 있는 자리”가 됩니다. 만약 그 자리에 여러 값이 모이면, 단일 연결 리스트로 이어서 관리합니다.

 

개념을 단순화하면 다음과 같이 볼 수 있습니다.

• Add(추가): 값 → 해시코드 → 인덱스 계산 → 해당 버킷 리스트에 이미 있으면 무시, 없으면 맨 앞에 삽입
• Contains(검색): 값 → 해시코드 → 인덱스 계산 → 해당 버킷 리스트만 순회하며 같은 값이 있는지 확인
• Remove(삭제): 값 → 해시코드 → 인덱스 계산 → 해당 버킷 리스트에서 노드를 찾아 연결을 끊어 제거

이 구조 덕분에, 한 번 Add / Contains / Remove를 호출할 때 걸리는 시간은 전체 원소 수에 거의 비례하지 않고, 평균적으로 일정한 시간(O(1))에 가깝게 동작합니다. 다만 데이터가 많아질수록 특정 버킷에 값이 몰리거나, 버킷 배열을 확장(Resize) 해야 하는 시점이 오면 순간적으로 더 많은 비용이 들 수는 있습니다. 그럼에도 연산 하나가 리스트처럼 원소 수(n)에 비례하여 선형으로 증가하는 구조는 아닙니다.

---

2. HashSet이 활용되는 대표적인 사례

HashSet은 구조가 단순해 보이지만, “중복을 허용하지 않고, 포함 여부를 자주 확인해야 하는 기능”의 핵심으로 자주 사용됩니다. 게임 개발 관점에서 대표적인 사례를 몇 가지 정리해 보겠습니다.

• 이미 로드된 리소스 ID 관리
  애셋 번들 이름, Addressables 키, 프리팹 이름 등을 HashSet으로 관리하면, “이 리소스가 이미 로드되어 있는지”를 한 번의 Contains 호출로 빠르게 확인할 수 있습니다.
• 버프/디버프 타입 중복 적용 방지
  캐릭터에게 적용된 버프 타입을 HashSet<BuffType>으로 관리하면, 같은 버프 타입을 여러 번 적용하려 할 때 Add의 리턴값만 확인해도 중복 여부를 쉽게 알 수 있습니다.
• 차단(블랙리스트) 유저 ID
  채팅 또는 파티 시스템에서 차단한 유저 ID 목록을 HashSet으로 관리하면, 메시지 수신 시 해당 ID가 블랙리스트에 포함되어 있는지 실시간으로 필터링할 수 있습니다.
• 이미 방문한 노드/타일 기록
  길찾기(DFS/BFS), 던전 탐색, 필드 로딩 등에서 “이미 방문한 위치”를 HashSet으로 관리하면, 같은 위치를 다시 처리하는 일을 방지할 수 있습니다.
• 한 번만 처리해야 하는 이벤트 ID
  퀘스트 완료, 보상 지급, 업적 해제 등 한 번만 처리해야 하는 이벤트의 ID를 HashSet으로 저장해 두고, 실행 전에 Contains로 체크하면 중복 처리를 쉽게 막을 수 있습니다.

이런 패턴은 “배열이나 리스트로도 구현은 가능하지만, 데이터가 많아질수록 성능이 떨어지는” 코드들을 HashSet 하나로 깔끔하게 정리해 주기 때문에, 실제 프로젝트에서 자주 등장하는 구조입니다.

---

3. HashSet이 제공하는 기능(구현 기준)

이번에 구현한 HashSet은 다음과 같은 기능을 제공합니다. 실제로 HashSet을 직접 구현할 때 “최소 이 정도 기능은 있어야 한다”는 기준으로 보면 됩니다.

• Count
  현재 HashSet에 저장되어 있는 요소의 개수를 반환합니다.
• Add
  새로운 값을 집합에 추가합니다. 이미 동일한 값이 존재하면 아무것도 추가하지 않고 false를 반환합니다. 새로 추가되면 true를 반환합니다.
• Contains
  해당 값이 HashSet에 포함되어 있는지 확인합니다. 있으면 true, 없으면 false입니다.
• Remove
  해당 값을 집합에서 제거합니다. 실제로 제거가 일어나면 true, 값이 없어서 제거할 것이 없으면 false입니다.
• Clear
  모든 요소를 제거하고, 버킷 배열을 기본 크기(DEFAULT_CAPACITY)로 다시 초기화합니다.

실제 .NET의 HashSet<T>는 이 외에도 IEnumerable 지원, 집합 연산(합집합, 교집합 등), TrimExcess 같은 추가 기능을 제공합니다. 필요하다면 이번 구현을 기반으로 이런 기능을 확장해 나가면 됩니다.

 

참고: TrimExcess는 HashSet이 내부적으로 보유한 버킷 배열 크기를 현재 요소 수에 맞게 줄여 메모리를 최적화하는 기능입니다. 많은 요소를 넣었다가 제거한 경우, 사용하지 않는 버킷에 대한 메모리를 반환하여 공간 효율을 높일 수 있습니다.

---

4. HashSet의 내부 동작 방식

이제 HashSet이 내부적으로 어떻게 동작하는지 단계별로 살펴보겠습니다.

 

4.1 Node 구조

• 값과 다음 노드를 가리키는 변수로 이뤄져 있습니다.

Node

Value : 값 Next : 다음 노드

 

4.2 버킷 배열

• 배열인데 세로로 있다고 생각해야 이해가 쉽습니다.

0

1

2

3

...

 

4.3 버킷 인덱스 계산

private int GetIndex(T value)
{
    int hash = _cmp.GetHashCode(value) & 0x7FFFFFFF;
    return hash % _buckets.Length;
}

• 비교기(_cmp)의 GetHashCode(value)로 해시코드를 계산합니다.
• GetHashCode()는 해당 타입의 모든 값에 대해 유일한 값을 보장하지는 않습니다. 하지만 동일한 값에 대해서는 항상 동일한 해시코드를 반환합니다.
• & 0x7FFFFFFF 연산으로 음수 비트를 제거해 항상 양수 해시코드를 만듭니다.
• 버킷 길이로 나눈 나머지를 사용해 0 ~ (_buckets.Length - 1) 범위의 인덱스를 얻습니다.

 

4.4. Add 흐름

✔ 초기 상태

• 모든 버킷이 비어 있음
• 여기서 사용한 ∅ 기호는 ‘비어 있음(null)’을 나타내는 공집합 기호입니다.

[0]  ∅
[1]  ∅
[2]  ∅
[3]  ∅
[4]  ∅
[5]  ∅

 

2) 값 14 추가 (예: 버킷 인덱스 2)

• 14의 HashCode를 가지고 버킷 인덱스를 구했을 때 2라고 가정
• 2번 버킷에 저장

[0]  ∅
[1]  ∅
[2]  14 → ∅
[3]  ∅
[4]  ∅
[5]  ∅

 

3) 값 30 추가 (예: 버킷 인덱스 1)

• 같은 방식으로 구해서 30의 버킷 인덱스가 1이라고 가정
• 1번 버킷에 저장

[0]  ∅
[1]  30 → ∅
[2]  14 → ∅
[3]  ∅
[4]  ∅
[5]  ∅

 

4) 값 22 추가 (예: 버킷 인덱스 2)

• 22의 버킷 인덱스가 2라고 가정
• 새 값을 연결 리스트의 앞쪽에 삽입합니다.

[0]  ∅
[1]  30 → ∅
[2]  22 → 14 → ∅
[3]  ∅
[4]  ∅
[5]  ∅

 

Add 메서드의 실제 코드는 다음과 같습니다.

public bool Add(T value)
{
    int idx = GetIndex(value); // 버킷 인덱스 구하기
    Node cur = _buckets[idx]; // 버킷의 첫 노드

    // 이미 존재하는 값인지 확인
    while (cur != null)
    {
        if (_cmp.Equals(cur.Value, value))
        {
            return false; // 중복 방지
        }

        cur = cur.Next;
    }

    // 새 노드를 앞쪽에 삽입
    Node node = new Node(value, _buckets[idx]);
    _buckets[idx] = node;
    ++_count;

    // 버킷 확장
    if (_count > _buckets.Length * 0.75f)
    {
        Resize();
    }

    return true;
}

 

버킷 인덱스를 계산한 후, 해당 버킷의 리스트를 한번 훑어보면서 이미 같은 값이 있는지 검사하고, 없다면 새 노드를 리스트 맨 앞에 붙이는 구조입니다. 평균적으로 O(1)에 가깝지만, 특정 버킷에 값이 몰리면 그 버킷의 길이만큼 O(k) 비용이 추가됩니다.

 

4.5. Contains / Remove 흐름

Contains(22) 호출

위에서 본 상태를 그대로 사용하면 버킷[2]에는 다음과 같은 연결 리스트가 있습니다.

[2]  22 → 14 → ∅

 

Contains(22)는 인덱스를 계산한 뒤, 해당 버킷의 연결 리스트를 순회하면서 값이 같은지 비교합니다. 첫 노드가 바로 22이므로, 첫 비교에서 true를 반환합니다.

public bool Contains(T value)
{
    int idx = GetIndex(value);
    Node cur = _buckets[idx];

    while (cur != null)
    {
        if (_cmp.Equals(cur.Value, value))
        {
            return true;
        }

        cur = cur.Next;
    }

    return false;
}

 

Remove(14) 호출

Remove는 단일 연결 리스트에서 노드를 제거해야 하므로, prev 포인터를 함께 사용합니다. 삭제 전 상태는 다음과 같습니다.

[2]  22 → 14 → ∅

 

14를 찾은 뒤, 이전 노드(22)의 Next를 14의 Next(∅)로 바꿔서 리스트에서 제거합니다.

[2]  22 → ∅

 

코드 흐름은 다음과 같습니다.

public bool Remove(T value)
{
    int idx = GetIndex(value);
    Node cur = _buckets[idx];
    Node prev = null;

    while (cur != null)
    {
        // 삭제 대상 노드를 찾은 경우
        if (_cmp.Equals(cur.Value, value))
        {
            // 이전 노드가 없는 경우 (즉, 현재 노드가 버킷의 첫 노드인 경우)
            if (prev == null)
            {
                // 버킷의 첫 노드를 현재 노드의 다음 노드로 변경
                _buckets[idx] = cur.Next;
            }
            else
            {
                // 이전 노드의 다음 노드를 현재 노드의 다음 노드로 변경
                prev.Next = cur.Next;
            }

            --_count;
            return true;
        }

        // 다음 노드로 이동
        prev = cur;
        cur = cur.Next;
    }

    return false;
}

 

평균적으로 Contains/Remove도 O(1)에 가깝지만, 특정 버킷에 값이 몰리면 그 버킷의 리스트 길이에 비례하는 비용이 듭니다.

 

4.6. Resize와 GC/성능 관점

버킷 확장은 요소 개수가 늘어나 현재 버킷 배열로는 충분히 분산되지 않을 때 발생합니다. 아래 다이어그램은 이러한 상황에서 Resize가 수행되면, 버킷 배열과 각 노드의 배치가 어떻게 달라지는지를 예시로 나타낸 것입니다.

 

Resize 전 (버킷 6개)

[0]  ∅
[1]  30 → ∅
[2]  22 → ∅
[3]  ∅
[4]  ∅
[5]  ∅

 

Resize 후 (버킷 12개, 다시 해싱해서 재배치)

[0]  ∅
[1]  30 → ∅
[2]  ∅
[3]  ∅
[4]  22 → ∅
[5]  ∅
[6]  ∅
[7]  ∅
[8]  ∅
[9]  ∅
[10] ∅
[11] ∅

 

실제 Resize 코드는 다음과 같습니다.

private void Resize()
{
    Node[] oldBuckets = _buckets;
    _buckets = new Node[oldBuckets.Length * 2]; // 2배 크기로 확장

    foreach (Node node in oldBuckets)
    {
        Node cur = node;
        while (cur != null)
        {
            int idx = GetIndex(cur.Value); // 새로운 버킷 인덱스

            // 현재 노드를 옮기기 전에 다음 노드를 미리 저장
            Node next = cur.Next;

            // 노드를 새로운 버킷 배열의 연결 리스트 맨 앞에 삽입
            cur.Next = _buckets[idx];
            _buckets[idx] = cur;

            // 다음 노드로 이동
            cur = next;
        }
    }
}

• 버킷 배열만 새로 할당하고, Node 인스턴스는 재사용합니다.
• 각 노드에 대해 새 인덱스를 계산해서 새 버킷 배열의 리스트 앞쪽에 붙입니다. 따라서 Resize 과정 자체는 O(n)입니다.
• Node를 새로 생성하지 않으므로, Resize 과정에서 추가 Node 할당에 따른 GC 부담은 없습니다. 다만 버킷 배열을 새로 할당하는 비용과, 모든 노드를 다시 해싱하는 비용은 존재합니다.

게임처럼 프레임 타임이 민감한 환경에서는, 예상 최대 개수를 알고 있다면 생성 시 capacity를 넉넉히 잡아서 Resize가 실시간 구간에서 발생하지 않도록 설계하는 것이 좋습니다. 또한 Add/Remove가 매우 빈번하게 일어나야 한다면, Node 풀링 등 추가적인 최적화도 고려할 수 있습니다.

---

5. C# 기반 HashSet 직접 구현하기

아래는 HashSet<T> 전체 코드입니다. 기본적인 Add, Contains, Remove, Clear 기능과 Resize(버킷 확장)를 포함하고 있습니다.

using BCL = System.Collections.Generic; // BCL - Base Class Library

namespace Daebak.Common.Collections
{
    /// <summary>
    /// 해시셋(HashSet) 구현체.
    /// 내부적으로 버킷 배열(bucket array)과 체이닝 리스트(chaining list)로 구성
    /// </summary>
    public class HashSet<T>
    {
        /// <summary>버킷 배열 (각 요소는 연결 리스트의 시작 노드를 가리킴)</summary>
        private Node[] _buckets;

        /// <summary>요소 개수</summary>
        private int _count;

        /// <summary>해시코드 계산용 비교기</summary>
        private readonly BCL.IEqualityComparer<T> _cmp;

        /// <summary>기본 버킷 개수</summary>
        private const int DEFAULT_CAPACITY = 16;

        /// <summary>현재 요소 수</summary>
        public int Count => _count;

        /// <summary>
        /// 연결 리스트 노드
        /// </summary>
        private class Node
        {
            public T Value;
            public Node Next;

            public Node(T value, Node next)
            {
                Value = value;
                Next = next;
            }
        }

        public HashSet(int capacity = DEFAULT_CAPACITY, BCL.IEqualityComparer<T> comparer = null)
        {
            _buckets = new Node[capacity];
            _cmp = comparer ?? BCL.EqualityComparer<T>.Default;
        }

        /// <summary>
        /// 요소 추가
        /// </summary>
        public bool Add(T value)
        {
            int idx = GetIndex(value); // 버킷 인덱스 구하기
            Node cur = _buckets[idx]; // 버킷의 첫 노드

            // 이미 존재하는 값인지 확인
            while (cur != null)
            {
                if (_cmp.Equals(cur.Value, value))
                {
                    return false; // 중복 방지
                }

                cur = cur.Next;
            }

            // 새 노드를 앞쪽에 삽입
            Node node = new Node(value, _buckets[idx]);
            _buckets[idx] = node;
            ++_count;

            // 버킷 확장
            if (_count > _buckets.Length * 0.75f)
            {
                Resize();
            }

            return true;
        }

        /// <summary>
        /// 요소 포함 여부 확인
        /// </summary>
        public bool Contains(T value)
        {
            int idx = GetIndex(value);
            Node cur = _buckets[idx];

            while (cur != null)
            {
                if (_cmp.Equals(cur.Value, value))
                {
                    return true;
                }

                cur = cur.Next;
            }

            return false;
        }

        /// <summary>
        /// 요소 삭제
        /// </summary>
        public bool Remove(T value)
        {
            int idx = GetIndex(value);
            Node cur = _buckets[idx];
            Node prev = null;

            while (cur != null)
            {
                // 삭제 대상 노드를 찾은 경우
                if (_cmp.Equals(cur.Value, value))
                {
                    // 이전 노드가 없는 경우 (즉, 현재 노드가 버킷의 첫 노드인 경우)
                    if (prev == null)
                    {
                        // 버킷의 첫 노드를 현재 노드의 다음 노드로 변경
                        _buckets[idx] = cur.Next;
                    }
                    else
                    {
                        // 이전 노드의 다음 노드를 현재 노드의 다음 노드로 변경
                        prev.Next = cur.Next;
                    }

                    --_count;
                    return true;
                }

                // 다음 노드로 이동
                prev = cur;
                cur = cur.Next;
            }

            return false;
        }

        /// <summary>
        /// 모든 요소 제거
        /// </summary>
        public void Clear()
        {
            _buckets = new Node[DEFAULT_CAPACITY];
            _count = 0;
        }

        /// <summary>
        /// 값에서 버킷 인덱스를 계산
        /// </summary>
        private int GetIndex(T value)
        {
            int hash = _cmp.GetHashCode(value) & 0x7FFFFFFF;
            return hash % _buckets.Length;
        }

        /// <summary>
        /// 버킷 크기 확장
        /// </summary>
        private void Resize()
        {
            Node[] oldBuckets = _buckets;
            _buckets = new Node[oldBuckets.Length * 2]; // 2배 크기로 확장

            foreach (Node node in oldBuckets)
            {
                Node cur = node;
                while (cur != null)
                {
                    int idx = GetIndex(cur.Value); // 새로운 버킷 인덱스

                    // 현재 노드를 옮기기 전에 다음 노드를 미리 저장
                    Node next = cur.Next;

                    // 노드를 새로운 버킷 배열의 연결 리스트 맨 앞에 삽입
                    cur.Next = _buckets[idx];
                    _buckets[idx] = cur;

                    // 다음 노드로 이동
                    cur = next;
                }
            }
        }
    }
}

---

6. 유니티(Unity) 환경에서 테스트해 보기

아래는 Unity에서 HashSet<T>를 간단히 테스트하는 예제입니다. 숫자를 추가하고, 중복 추가를 시도하고, 삭제와 포함 여부를 확인하는 과정을 통해 HashSet의 기본 동작을 로그창에서 확인할 수 있습니다.

using UnityEngine;
using Daebak.Common.Collections;

public class Test_HashSet : MonoBehaviour
{
    void Start()
    {
        HashSet<int> set = new HashSet<int>();

        Debug.Log("=== HashSet 테스트 시작 ===");

        // 1) 기본 Add
        Debug.Log($"Add(1) => {set.Add(1)}");
        Debug.Log($"Add(2) => {set.Add(2)}");
        Debug.Log($"Add(3) => {set.Add(3)}");
        Debug.Log($"Count = {set.Count}");

        // 2) 중복 Add
        Debug.Log($"Add(2) (중복) => {set.Add(2)}");
        Debug.Log($"Count = {set.Count}");

        // 3) Contains 테스트
        Debug.Log($"Contains(1) => {set.Contains(1)}");
        Debug.Log($"Contains(4) => {set.Contains(4)}");

        // 4) Remove 테스트
        Debug.Log($"Remove(2) => {set.Remove(2)}");
        Debug.Log($"Remove(2) (이미 삭제됨) => {set.Remove(2)}");
        Debug.Log($"Count = {set.Count}");
        Debug.Log($"Contains(2) => {set.Contains(2)}");

        // 5) Clear 테스트
        set.Clear();
        Debug.Log("Clear() 호출");
        Debug.Log($"Count = {set.Count}");

        Debug.Log("=== HashSet 테스트 종료 ===");
    }
}

실행 결과

=== HashSet 테스트 시작 ===
Add(1) => True
Add(2) => True
Add(3) => True
Count = 3
Add(2) (중복) => False
Count = 3
Contains(1) => True
Contains(4) => False
Remove(2) => True
Remove(2) (이미 삭제됨) => False
Count = 2
Contains(2) => False
Clear() 호출
Count = 0
=== HashSet 테스트 종료 ===

 

이 결과를 통해 다음 사항을 직관적으로 확인할 수 있습니다.

• 중복 Add는 실패(false)를 반환하며 Count가 증가하지 않습니다.
• Contains는 실제 포함 여부에 따라 true/false를 정확히 반환합니다.
• Remove는 실제 삭제가 일어날 때만 true를 반환하며, 없는 값에 대해서는 false입니다.
• Clear 후에는 Count가 0으로 초기화됩니다.

---

마무리

HashSet은 중복 없이 값을 저장하고, 포함 여부를 매우 빠르게 확인할 수 있는 자료구조입니다. 해시 함수, 버킷 배열, 체이닝 구조를 조합해 평균적으로 O(1)에 가까운 효율을 제공합니다.

 

이번 글에서는 HashSet의 핵심 구조, Add/Contains/Remove 흐름, 충돌 처리 방식, 그리고 Resize 동작까지 살펴보았습니다. 게임 개발에서는 이미 로드된 리소스, 적용된 버프, 방문한 노드 등 “중복 없이 빠르게 검사해야 하는 데이터”가 많기 때문에 HashSet은 매우 유용하게 활용됩니다.

 

앞으로 필요하다면 IEnumerable 지원, 집합 연산, 커스텀 비교기 등 더 다양한 기능을 추가해 기능을 확장할 수 있습니다.

 

※ 다음 글에서는 Dictionary(딕셔너리) 구조를 살펴보며, 값의 존재 여부를 다루는 HashSet에서 한 단계 확장하여 키–값(Key–Value) 쌍을 기반으로 데이터를 빠르게 조회하고 관리하는 방식을 중심으로 정리합니다.