자료구조 — 해시 테이블(Hash Table)

개요 — 왜 해시 테이블을 알아야 하는가

배열은 인덱스로 O(1) 접근이 가능하지만, “특정 아이템 ID에 해당하는 데이터를 찾아라”처럼 키(Key) 기반 탐색에는 적합하지 않습니다. 정렬된 배열과 이진 탐색을 조합해도 O(log n)에 그칩니다. **해시 테이블(Hash Table)**은 키를 수학적 함수로 변환해 배열 인덱스로 직접 매핑함으로써 평균 O(1)의 삽입·탐색·삭제를 달성하는 자료구조입니다.

게임 개발에서 해시 테이블은 사실상 어디에나 있습니다.

• 수천 개의 아이템 데이터를 ID로 즉시 조회하는 아이템 데이터베이스
• 접속 중인 플레이어를 세션 ID로 관리하는 세션 시스템
• Unreal Engine의 에셋 레지스트리(Asset Registry)와 오브젝트 맵
• C++의 std::unordered_map, Unreal의 TMap·TSet

이 구조의 내부를 이해하면 언제 O(1)이 무너지는지, 왜 TMap이 TArray보다 느릴 수 있는지를 설명할 수 있게 됩니다.

---

1. 해시 테이블의 내부 구조

1.1 핵심 아이디어: 키 → 인덱스 변환

해시 테이블은 내부적으로 **고정 크기 배열(버킷 배열, Bucket Array)**을 사용합니다. 데이터를 저장할 때 다음 과정을 거칩니다.

Key → 해시 함수(Hash Function) → 해시 코드(정수) → 버킷 인덱스(해시 코드 % 버킷 수)

예를 들어 버킷이 8개이고, 키 "Sword"의 해시 코드가 1234라면:

버킷 인덱스 = 1234 % 8 = 2

"Sword" 관련 데이터는 버킷 2번에 저장됩니다. 이후 조회 시에도 동일한 계산으로 O(1) 접근이 가능합니다.

┌─────────────────────────────────────────┐
│           Bucket Array (size=8)         │
├────┬────┬────┬────┬────┬────┬────┬─────┤
│ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │  7  │
│    │    │ SW │    │    │    │    │     │  ← "Sword" → index 2
└────┴────┴────┴────┴────┴────┴────┴─────┘

1.2 해시 함수(Hash Function)의 요건

좋은 해시 함수는 세 가지 조건을 만족해야 합니다.

조건	설명
결정적(Deterministic)	같은 키는 항상 같은 해시 코드를 반환
균등 분포(Uniform Distribution)	해시 코드가 버킷 전체에 고르게 퍼져야 충돌 최소화
고속 연산(Fast Computation)	해시 계산 자체가 병목이 되지 않아야 함

정수 키 해시 예시:

// 간단한 나머지 연산 (버킷 수가 소수일 때 분포 균등)
size_t HashInt(int Key, size_t BucketCount)
{
    return static_cast<size_t>(Key) % BucketCount;
}

문자열 키 해시 예시 (djb2 알고리즘):

size_t HashString(const std::string& Key)
{
    size_t Hash = 5381;
    for (char Ch : Key)
    {
        Hash = Hash * 33 + static_cast<unsigned char>(Ch);
    }
    return Hash;
}

djb2는 단순하지만 문자열 분포가 양호하여 실무에서도 자주 사용됩니다. C++ 표준 라이브러리는 내부적으로 더 정교한 알고리즘(MurmurHash, FNV-1a 등)을 씁니다.

---

2. 해시 충돌(Collision) 해결 방법

서로 다른 두 키가 같은 버킷 인덱스를 가리키는 상황을 **해시 충돌(Collision)**이라고 합니다. 충돌은 피할 수 없으므로, 어떻게 처리하느냐가 핵심입니다.

2.1 체이닝(Chaining) — 연결 리스트로 연결

각 버킷이 **연결 리스트(또는 다른 동적 컨테이너)**를 가지며, 충돌 시 해당 리스트에 노드를 추가합니다.

Bucket[2] → ["Sword", 150 gold] → ["Shield", 80 gold] → nullptr

// 체이닝 방식 해시 테이블 개념 코드
template <typename KeyType, typename ValueType>
class FChainHashTable
{
    static constexpr int32 BucketCount = 16;

    struct FEntry
    {
        KeyType   Key;
        ValueType Value;
        FEntry*   Next = nullptr;
    };

    FEntry* Buckets[BucketCount] = {};

    int32 GetBucketIndex(const KeyType& Key) const
    {
        return std::hash<KeyType>{}(Key) % BucketCount;
    }

public:
    void Insert(const KeyType& Key, const ValueType& Value)
    {
        int32 Idx    = GetBucketIndex(Key);
        FEntry* Node = new FEntry{Key, Value, Buckets[Idx]};
        Buckets[Idx] = Node;  // 리스트 앞에 삽입 (O(1))
    }

    ValueType* Find(const KeyType& Key)
    {
        int32 Idx    = GetBucketIndex(Key);
        FEntry* Node = Buckets[Idx];
        while (Node)
        {
            if (Node->Key == Key) { return &Node->Value; }
            Node = Node->Next;
        }
        return nullptr;
    }
};

장점: 구현이 단순하고, 버킷 수보다 데이터가 많아도 동작합니다.
단점: 포인터 추적으로 인한 캐시 미스(Cache Miss)가 발생하며, 최악의 경우(모든 키가 같은 버킷) O(n) 탐색이 됩니다.

2.2 오픈 어드레싱(Open Addressing) — 빈 버킷을 직접 탐색

충돌 시 연결 리스트 대신, 배열 내 다른 버킷을 찾아 이동합니다. 모든 데이터가 배열 자체에 저장되므로 캐시 친화적입니다.

선형 탐사(Linear Probing): 충돌 시 인덱스를 1씩 증가시켜 빈 슬롯을 탐색합니다.

HashIndex = hash(Key) % N
충돌 시:  (HashIndex + 1) % N
재충돌 시: (HashIndex + 2) % N
...

이차 탐사(Quadratic Probing): 탐사 거리를 1, 4, 9, 16… (i²) 으로 증가시켜 클러스터링(Clustering) 문제를 완화합니다.

(HashIndex + i²) % N

이중 해싱(Double Hashing): 두 번째 해시 함수를 사용해 탐사 간격 자체를 결정합니다.

(HashIndex + i × hash2(Key)) % N

// 선형 탐사 방식 해시 테이블 개념 코드
template <typename KeyType, typename ValueType>
class FLinearProbeHashTable
{
    static constexpr int32 BucketCount = 16;

    struct FSlot
    {
        KeyType   Key;
        ValueType Value;
        bool      bOccupied = false;
    };

    FSlot Slots[BucketCount];

    int32 GetStartIndex(const KeyType& Key) const
    {
        return static_cast<int32>(std::hash<KeyType>{}(Key) % BucketCount);
    }

public:
    bool Insert(const KeyType& Key, const ValueType& Value)
    {
        int32 Idx = GetStartIndex(Key);
        for (int32 i = 0; i < BucketCount; ++i)
        {
            int32 ProbeIdx = (Idx + i) % BucketCount;
            if (!Slots[ProbeIdx].bOccupied)
            {
                Slots[ProbeIdx] = {Key, Value, true};
                return true;
            }
        }
        return false;  // 테이블이 가득 참
    }

    ValueType* Find(const KeyType& Key)
    {
        int32 Idx = GetStartIndex(Key);
        for (int32 i = 0; i < BucketCount; ++i)
        {
            int32 ProbeIdx = (Idx + i) % BucketCount;
            if (!Slots[ProbeIdx].bOccupied) { return nullptr; }
            if (Slots[ProbeIdx].Key == Key) { return &Slots[ProbeIdx].Value; }
        }
        return nullptr;
    }
};

장단점 비교:

방식	캐시 효율	삭제 난이도	클러스터링	메모리 오버헤드
체이닝	낮음	쉬움	없음	포인터 비용
선형 탐사	높음	복잡(Tombstone 필요)	심함	없음
이차 탐사	높음	복잡	보통	없음
이중 해싱	높음	복잡	최소	없음

실전 팁: std::unordered_map은 체이닝을 사용합니다. absl::flat_hash_map(Google Abseil)이나 Robin Hood Hashing 라이브러리는 오픈 어드레싱으로 캐시 효율을 높입니다. Unreal의 TSet / TMap은 체이닝 기반입니다.

---

3. 로드 팩터(Load Factor)와 리해싱(Rehashing)

3.1 로드 팩터란

로드 팩터 (α) = 저장된 원소 수 / 버킷 수

• α = 0.5 → 버킷의 절반이 채워진 상태
• α = 1.0 → 버킷이 모두 찼거나 평균 1개씩 차지

로드 팩터가 높아질수록 충돌 확률이 증가하여 탐색 시간이 O(1)에서 멀어집니다. 체이닝 방식의 경우 평균 탐색 시간은 O(1 + α)로 표현할 수 있습니다.

3.2 리해싱(Rehashing)

로드 팩터가 임계값을 초과하면, 버킷 배열을 더 크게 재할당하고 모든 원소를 재배치하는 리해싱을 수행합니다.

임계 로드 팩터(Threshold) 초과 → 버킷 수 2배 확장 → 모든 키를 새 배열에 재해시

// 리해싱 개념 코드
void Rehash()
{
    int32 NewBucketCount = BucketCount * 2;
    // 새 배열 할당
    std::vector<std::list<std::pair<KeyType, ValueType>>> NewBuckets(NewBucketCount);

    // 기존 원소 전체를 새 위치로 이동
    for (auto& Bucket : Buckets)
    {
        for (auto& [Key, Value] : Bucket)
        {
            int32 NewIdx = std::hash<KeyType>{}(Key) % NewBucketCount;
            NewBuckets[NewIdx].emplace_back(Key, Value);
        }
    }

    Buckets     = std::move(NewBuckets);
    BucketCount = NewBucketCount;
}

표준 라이브러리의 임계값:

구현	기본 max_load_factor
std::unordered_map	1.0
Unreal TMap	로드 팩터 기반 동적 확장

unordered_map.reserve(N)을 미리 호출하면 삽입 중 리해싱을 방지할 수 있습니다. 원소 수를 사전에 알고 있다면 반드시 호출하세요.

---

4. 시간복잡도 분석

연산	평균	최악
삽입(Insert)	O(1)	O(n)
탐색(Lookup)	O(1)	O(n)
삭제(Delete)	O(1)	O(n)
리해싱	—	O(n)

평균 O(1)의 조건:

• 해시 함수가 키를 균등하게 분포시킨다.
• 로드 팩터가 적절한 임계값 이하로 유지된다.

최악 O(n)이 되는 상황:

• 모든 키가 동일한 해시 코드를 가져 하나의 버킷에 집중될 때 (최악의 해시 함수 또는 의도적인 해시 충돌 공격).
• 리해싱이 발생하는 순간 (단발 O(n), 분할 상각(Amortized)하면 삽입 1회당 O(1) 수렴).

배열(Array) vs 해시 테이블 비교:

연산	std::vector (정렬 없음)	std::vector (정렬 후 이진 탐색)	std::unordered_map
탐색	O(n)	O(log n)	O(1) 평균
삽입(끝)	O(1) 분할 상각	O(n) (정렬 유지)	O(1) 평균
순서 보장	O	O	X
메모리 효율	높음	높음	낮음 (포인터/버킷 오버헤드)

---

5. C++ std::unordered_map과 Unreal TMap / TSet

5.1 std::unordered_map 기본 사용

#include <unordered_map>
#include <string>

// 아이템 ID → 아이템 이름 매핑
std::unordered_map<int32, std::string> ItemDatabase;

void InitItemDatabase()
{
    ItemDatabase.reserve(1024);  // 리해싱 방지를 위해 미리 예약

    ItemDatabase[1001] = "Long Sword";
    ItemDatabase[1002] = "Iron Shield";
    ItemDatabase[1003] = "Health Potion";
}

void LookupItem(int32 ItemId)
{
    // find()는 end() 반환으로 실패를 안전하게 처리
    auto It = ItemDatabase.find(ItemId);
    if (It != ItemDatabase.end())
    {
        // It->first = Key, It->second = Value
        printf("Item: %s\n", It->second.c_str());
    }
}

커스텀 타입을 키로 사용할 때: std::hash 특수화가 필요합니다.

struct FItemKey
{
    int32 CategoryId;
    int32 ItemId;

    bool operator==(const FItemKey& Other) const
    {
        return CategoryId == Other.CategoryId && ItemId == Other.ItemId;
    }
};

// std::hash 특수화
namespace std
{
    template<>
    struct hash<FItemKey>
    {
        size_t operator()(const FItemKey& Key) const
        {
            // 두 정수를 XOR과 비트 시프트로 결합
            size_t H1 = std::hash<int32>{}(Key.CategoryId);
            size_t H2 = std::hash<int32>{}(Key.ItemId);
            return H1 ^ (H2 << 32 | H2 >> 32);
        }
    };
}

std::unordered_map<FItemKey, std::string> CategorizedItems;

5.2 Unreal Engine TMap

TMap<KeyType, ValueType>은 Unreal의 해시 기반 키-값 맵입니다. 내부적으로 TSet을 래핑하여 구현되어 있으며, 체이닝 방식의 해시 테이블을 사용합니다.

#include "Containers/Map.h"

// 플레이어 ID → 플레이어 정보 매핑
UCLASS()
class AMyGameMode : public AGameModeBase
{
    GENERATED_BODY()

private:
    // TMap은 UPROPERTY로 선언 가능 (UObject 기반 GC 대상)
    UPROPERTY()
    TMap<int32, TObjectPtr<APlayerState>> PlayerSessionMap;

public:
    void RegisterPlayer(int32 PlayerId, APlayerState* State)
    {
        PlayerSessionMap.Add(PlayerId, State);
    }

    APlayerState* FindPlayer(int32 PlayerId) const
    {
        // Find()는 포인터를 반환. nullptr 반환 시 키 없음
        TObjectPtr<APlayerState> const* Found = PlayerSessionMap.Find(PlayerId);
        return Found ? Found->Get() : nullptr;
    }

    void UnregisterPlayer(int32 PlayerId)
    {
        PlayerSessionMap.Remove(PlayerId);
    }

    void IteratePlayers()
    {
        for (auto& [Id, State] : PlayerSessionMap)
        {
            if (State)
            {
                UE_LOG(LogTemp, Log, TEXT("Player %d: %s"), Id, *State->GetPlayerName());
            }
        }
    }
};

TMap 주요 API 정리:

메서드	설명
Add(Key, Value)	키-값 삽입 (키 중복 시 덮어씀)
Find(Key)	값의 포인터 반환, 없으면 nullptr
FindOrAdd(Key)	키가 없으면 기본값으로 추가 후 참조 반환
Remove(Key)	키 삭제
Contains(Key)	키 존재 여부 bool 반환
Num()	원소 수 반환
Reserve(N)	N개 원소를 위한 공간 미리 확보
Empty()	모든 원소 제거

커스텀 타입을 TMap 키로 사용할 때: GetTypeHash() 함수와 operator==를 정의해야 합니다.

struct FInventorySlot
{
    int32 BagIndex;
    int32 SlotIndex;

    bool operator==(const FInventorySlot& Other) const
    {
        return BagIndex == Other.BagIndex && SlotIndex == Other.SlotIndex;
    }
};

// GetTypeHash 정의 (전역 함수)
inline uint32 GetTypeHash(const FInventorySlot& Slot)
{
    // HashCombine은 Unreal의 해시 결합 유틸리티
    return HashCombine(GetTypeHash(Slot.BagIndex), GetTypeHash(Slot.SlotIndex));
}

// 이제 TMap 키로 사용 가능
TMap<FInventorySlot, FItemData> InventoryGrid;

5.3 Unreal Engine TSet

TSet<ElementType>은 중복 없는 원소 집합으로, TMap의 키 전용 버전과 유사합니다. 내부적으로 해시 버킷 배열과 원소 배열을 조합하여 구현되어 있습니다.

#include "Containers/Set.h"

// 활성화된 태그 관리
TSet<FName> ActiveTags;

void AddTag(FName Tag)
{
    ActiveTags.Add(Tag);          // 중복 추가해도 하나만 유지
}

bool HasTag(FName Tag) const
{
    return ActiveTags.Contains(Tag);  // O(1) 평균
}

void RemoveTag(FName Tag)
{
    ActiveTags.Remove(Tag);
}

// 두 집합의 교집합 (Gameplay Tag 시스템과 유사한 패턴)
TSet<FName> GetCommonTags(const TSet<FName>& Other) const
{
    return ActiveTags.Intersect(Other);
}

TSet의 FSetElementId:

TSet은 원소를 제거해도 실제 메모리를 즉시 해제하지 않고 빈 슬롯(hole)을 남깁니다. FSetElementId는 이 슬롯의 직접 인덱스로, O(1) 접근을 보장합니다. 단, 원소 추가로 리해싱이 발생하면 기존 FSetElementId는 무효화될 수 있습니다.

// FSetElementId를 이용한 O(1) 직접 접근
FSetElementId ElementId = ActiveTags.Add(TEXT("Poisoned")).Id;

// Id가 유효한 동안 O(1) 접근
if (ActiveTags.IsValidId(ElementId))
{
    FName& Tag = ActiveTags[ElementId];
}

5.4 TMap vs std::unordered_map 선택 기준

기준	std::unordered_map	TMap
프로젝트 환경	순수 C++	Unreal Engine 프로젝트
UPROPERTY 지원	불가	가능
GC 통합	불가	가능 (UObject 포인터 값)
직렬화(Serialization)	수동 구현	엔진 자동 지원
커스텀 키 요구사항	std::hash 특수화	GetTypeHash() + operator==
성능 특성	표준 체이닝	체이닝 (TSet 기반)

Unreal 프로젝트 내부에서는 항상 TMap과 TSet을 사용하세요. std::unordered_map은 GC와 직렬화 시스템에 통합되지 않아 의도치 않은 버그의 원인이 됩니다.

---

6. 게임 개발 실전 활용

6.1 아이템 데이터베이스

대규모 RPG에서 수천 개의 아이템을 즉시 조회하는 데이터 테이블 시스템입니다.

USTRUCT(BlueprintType)
struct FItemData
{
    GENERATED_BODY()

    UPROPERTY(EditAnywhere) FName  ItemName;
    UPROPERTY(EditAnywhere) int32  BasePrice  = 0;
    UPROPERTY(EditAnywhere) float  Weight     = 0.0f;
    UPROPERTY(EditAnywhere) TObjectPtr<UTexture2D> Icon;
};

UCLASS()
class UItemDatabaseSubsystem : public UGameInstanceSubsystem
{
    GENERATED_BODY()

private:
    // 아이템 ID → 아이템 데이터. 게임 시작 시 DataTable에서 로드
    UPROPERTY()
    TMap<int32, FItemData> ItemDatabase;

public:
    void Initialize(FSubsystemCollectionBase& Collection) override
    {
        LoadItemsFromDataTable();
    }

    const FItemData* FindItem(int32 ItemId) const
    {
        return ItemDatabase.Find(ItemId);  // O(1) 평균
    }

    void LoadItemsFromDataTable()
    {
        // DataTable에서 모든 행을 읽어 TMap에 적재
        // 실제 구현에서는 UDataTable::GetAllRows<FItemData>() 사용
        ItemDatabase.Reserve(2048);  // 예상 아이템 수로 리해싱 방지
    }
};

사용 예시:

if (UItemDatabaseSubsystem* DB = GetGameInstance()->GetSubsystem<UItemDatabaseSubsystem>())
{
    if (const FItemData* Item = DB->FindItem(1001))
    {
        UE_LOG(LogTemp, Log, TEXT("Item: %s, Price: %d"), *Item->ItemName.ToString(), Item->BasePrice);
    }
}

6.2 플레이어 세션 관리

멀티플레이어 게임에서 NetId를 키로 플레이어 상태를 빠르게 조회합니다.

UCLASS()
class AMyGameState : public AGameState
{
    GENERATED_BODY()

private:
    // UniqueNetId 문자열 → 플레이어 커스텀 데이터
    TMap<FString, FPlayerSessionData> ActiveSessions;

public:
    void OnPlayerConnected(APlayerController* PC)
    {
        if (!PC || !PC->PlayerState) { return; }

        FString NetId = PC->PlayerState->GetUniqueId().ToString();
        FPlayerSessionData& SessionData = ActiveSessions.FindOrAdd(NetId);
        SessionData.ConnectTime         = FDateTime::UtcNow();
        SessionData.PlayerName          = PC->PlayerState->GetPlayerName();
    }

    void OnPlayerDisconnected(APlayerController* PC)
    {
        if (!PC || !PC->PlayerState) { return; }

        FString NetId = PC->PlayerState->GetUniqueId().ToString();
        ActiveSessions.Remove(NetId);
    }

    int32 GetActivePlayerCount() const
    {
        return ActiveSessions.Num();
    }
};

6.3 에셋 레지스트리 패턴

게임 내 동적 에셋 참조를 경로(FName)로 캐싱하여, 비동기 로드 전 동기식 O(1) 조회를 지원합니다.

UCLASS()
class UAssetCacheSubsystem : public UGameInstanceSubsystem
{
    GENERATED_BODY()

private:
    // 에셋 경로 → 로드된 에셋 (TWeakObjectPtr로 GC 대상 허용)
    TMap<FName, TWeakObjectPtr<UObject>> AssetCache;

public:
    UObject* GetCachedAsset(FName AssetPath)
    {
        if (TWeakObjectPtr<UObject>* Cached = AssetCache.Find(AssetPath))
        {
            if (Cached->IsValid())
            {
                return Cached->Get();  // O(1): 캐시 히트
            }
            // GC로 수거된 에셋 → 캐시에서 제거
            AssetCache.Remove(AssetPath);
        }
        return nullptr;
    }

    void CacheAsset(FName AssetPath, UObject* Asset)
    {
        if (Asset)
        {
            AssetCache.Add(AssetPath, Asset);
        }
    }
};

TWeakObjectPtr을 값으로 사용하면 GC가 에셋을 수거해도 캐시 맵 자체는 오염되지 않습니다. 다음 조회 시 IsValid() 체크로 무효 항목을 자동 감지할 수 있습니다.

---

7. 정리

개념	핵심 요약
해시 함수	키 → 정수 인덱스 변환. 균등 분포가 성능을 결정
체이닝	충돌 시 연결 리스트로 연결. 구현 단순, 캐시 효율 낮음
오픈 어드레싱	충돌 시 빈 버킷 탐색. 캐시 친화적, 삭제 복잡
로드 팩터	원소 수 / 버킷 수. 높을수록 충돌 증가
리해싱	로드 팩터 초과 시 버킷 2배 확장 후 전체 재배치. O(n) 단발 비용
평균 O(1)	해시 함수가 균등하고 로드 팩터가 적절할 때 보장
TMap	Unreal의 GC/직렬화 통합 해시 맵. 커스텀 키는 GetTypeHash() 필요
TSet	중복 없는 원소 집합. FSetElementId로 O(1) 직접 접근 가능

해시 테이블은 평균 O(1)이라는 강력한 보장 덕분에 게임 개발의 수많은 조회 중심 시스템에서 기본 자료구조로 자리 잡고 있습니다. 그러나 해시 함수 품질, 로드 팩터 관리, 리해싱 비용을 이해해야만 최악의 O(n)으로 성능이 무너지는 상황을 방지할 수 있습니다.

Unreal 프로젝트에서는 TMap과 TSet을 통해 엔진 생태계(GC, 직렬화, 블루프린트 연동)와 자연스럽게 통합된 해시 테이블을 활용하세요.