[언리얼 엔진] std::map과 TMap 차이 정리

언리얼 엔진으로 클래스를 작성하다 보면 TMap을 사용하는 경우가 있다.

처음에는 TMap이 해시 기반 컨테이너이고,
탐색이 평균적으로 O(1)이기 때문에 당연히 빠른 컨테이너라고 생각했다.
하지만 실제로는 항상 TMap이 빠른 것은 아니라고 한다.

예를 들어 TArray는 메모리에 연속적으로 데이터를 저장하기 때문에 캐시 효율이 좋고,
데이터 개수나 접근 방식에 따라서는 이론적인 시간 복잡도와 다르게 TArray가 더 빠를 수도 있다.

그래서 TMap이 실제로 내부에서 데이터를 어떻게 관리하는지 궁금해졌다.

이번 글에서는 TMap의 내부 구조를 이해하기 위해
C++의 std::map과 비교하면서 두 컨테이너의 차이를 간단히 정리해보려고 한다.

---

std::map

std::map은 C++ 표준 라이브러리에서 제공하는 Key-Value 컨테이너이다.

기본적으로 Key 기준 정렬을 유지하고, 내부적으로는 보통 레드-블랙 트리 같은 균형 이진 탐색 트리로 구현된다.
그래서 탐색, 삽입, 삭제는 O(log N)의 시간 복잡도를 가진다.

언리얼 엔진 관점에서 보면 std::map은 순수 C++ 컨테이너이기 때문에
언리얼 리플렉션 시스템과 직접 연결되지 않는다.

따라서 UPROPERTY로 선언할 수 없고, 에디터 노출이나 직렬화 같은 언리얼 기능과 함께 사용하기 어렵다.

---

TMap

TMap은 언리얼 엔진에서 제공하는 Key-Value 컨테이너이다.
C++의 std::map과 비슷하게 Key와 Value를 함께 저장하지만 내부 동작 방식은 다르다.

TMap은 트리 기반이 아니라 해시 기반 컨테이너이다.

TMap<FName, int32> ItemCounts;

ItemCounts.Add(TEXT("Potion"), 3);
ItemCounts.Add(TEXT("Sword"), 1);
ItemCounts.Add(TEXT("Shield"), 2);

TMap은 Key에 해시 함수를 적용해서 해시 값을 만들고,
그 해시 값을 이용해 데이터가 들어갈 위치를 찾는다.
그래서 평균적으로 탐색, 삽입, 삭제가 O(1)에 가깝다.

다만 해시 기반 컨테이너이기 때문에 해시 충돌이 많아지면 성능이 나빠질 수 있다.
또한 TMap은 기본적으로 정렬을 보장하지 않는다.

따라서 순회 순서가 필요하거나 Key 정렬이 중요한 상황이라면
std::map처럼 정렬된 컨테이너와는 다르게 생각해야 한다.

---

std::map과 TMap 비교

두 컨테이너를 간단히 비교하면 다음과 같다.

구분	std::map	TMap
내부 구조	보통 균형 이진 탐색 트리	해시 기반
정렬 여부	Key 기준 정렬	기본적으로 정렬되지 않음
탐색 / 삽입 / 삭제	O(log N)	평균 O(1)
UPROPERTY	불가능	가능, 단 Key/Value 타입 제한 있음
주 사용 상황	정렬된 Key 순회가 필요할 때	언리얼 객체/데이터에서 빠른 Key 검색이 필요할 때

둘 다 Key-Value 컨테이너라는 점은 같지만,
정렬이 필요한지, 언리얼 리플렉션 시스템과 함께 사용할 것인지에 따라 선택이 달라질 수 있다.

---

해시 맵이란?

TMap을 이해하려면 해시 맵의 기본 개념을 알아야 한다.

해시 맵은 Key에 해시 함수를 적용해 해시 값을 만들고,
그 값을 이용해서 데이터를 저장할 버킷 위치를 찾는 방식이다.

간단히 보면 다음과 같은 흐름이다.

Key
-> Hash Function
-> Hash Value
-> Bucket Index
-> Value 저장 위치

예를 들어 FName이나 문자열 같은 Key가 들어오면 해시 함수를 통해 정수 형태의 해시 값을 만들고,
그 값을 이용해서 내부 배열의 특정 위치에 접근한다.

이 방식은 Key를 하나씩 비교하면서 찾는 것이 아니라
해시 값을 통해 바로 위치를 찾으려고 하기 때문에 평균적으로 빠르다.

---

해시 충돌

해시 맵에서는 서로 다른 Key가 같은 버킷 위치를 가리키는 경우가 생길 수 있다.
이것을 해시 충돌이라고 한다.

해시 충돌을 해결하는 대표적인 방법에는 다음과 같은 방식이 있다.

• 체이닝
• 개방 주소법

체이닝은 같은 버킷에 들어온 원소들을 연결해서 관리하는 방식이다.

개방 주소법은 충돌이 발생했을 때 다른 빈 위치를 찾아 데이터를 저장하는 방식이다.

TMap도 해시 충돌을 처리해야 한다.

다만 일반적인 설명에서 말하는 것처럼 버킷에 연결 리스트 노드를 직접 저장하는 형태라기보다는,
내부 배열의 인덱스를 따라가며 같은 버킷의 원소들을 연결하는 방식에 가깝다.

---

TMap의 내부 데이터 관리 방식

TMap은 내부적으로 Key-Value 쌍을 TPair<Key, Value> 형태로 저장한다.
그리고 TMap은 내부적으로 TSet을 기반으로 Pair들을 관리하는 구조를 가진다.

개념적으로 보면 TMap<Key, Value>는
TPair<Key, Value>를 원소로 가지는 TSet을 이용해 관리된다고 볼 수 있다.

TSet<TPair<KeyType, ValueType>>

TMap은 Key에 해시 함수를 적용해 버킷 위치를 찾고,
버킷에는 실제 Pair를 직접 저장하기보다는 내부 Sparse Array의 인덱스를 저장한다.

그리고 해당 인덱스를 통해 실제 Pair 데이터에 접근한다.

Bucket
-> SparseArray Index
-> Pair<Key, Value>

Sparse Array는 중간에 원소가 삭제되어 빈 공간이 생겨도 그 공간을 관리할 수 있는 배열 구조이다.

따라서 TMap은 단순한 배열 하나만으로 관리되는 것이 아니라,
해시 버킷과 Sparse Array를 함께 이용해 데이터를 관리한다고 볼 수 있다.

---

TMap의 충돌 처리 방식

여기서 버킷 테이블에 저장된 값은 실제 데이터가 아니라
Sparse Array에서 같은 버킷 체인이 시작되는 원소의 인덱스이다.

다시 말해, 버킷은 체인의 시작 원소 인덱스를 가지고 있고,
각 원소는 HashNextId를 통해 같은 버킷에 속한 다음 원소의 인덱스를 가지고 있다.

해시 충돌이 발생하면 같은 버킷에 여러 원소가 연결될 수 있다.

TMap에서는 원소가 같은 버킷에 들어올 때
내부 원소가 다음 원소의 인덱스를 가지고 있는 방식으로 연결된다.

Sparse Array에 저장되는 내부 원소는 간단하게 다음과 같은 형태로 생각할 수 있다.

struct FSetElement
{
    TPair<FName, int32> Pair;

    int32 HashNextId; // 해시 충돌이 일어난 같은 버킷의 다음 원소 인덱스
};

실제 엔진 내부 구현을 단순화한 예시이지만,
핵심은 같은 버킷에 들어온 원소들이 내부 배열의 인덱스를 통해 연결된다는 것이다.

새로운 원소가 같은 버킷에 추가되면 그 원소가 체인의 앞쪽에 연결되고,
버킷은 새 원소의 인덱스를 가리키게 된다.

따라서 TMap의 충돌 처리는 일반적인 연결 리스트 노드를 직접 따라가는 방식이라기보다
내부 배열의 인덱스를 따라가며 다음 원소를 찾는 방식으로 이해할 수 있다.

---

UPROPERTY와 TMap

언리얼에서 TMap을 사용할 때 중요한 차이 중 하나는
UPROPERTY로 선언할 수 있다는 점이다.

UPROPERTY(EditAnywhere)
TMap<FName, int32> ItemCounts;

이렇게 선언하면 언리얼 리플렉션 시스템과 연결될 수 있고,
에디터 노출이나 직렬화 같은 기능과 함께 사용할 수 있다.

반면 std::map은 언리얼의 리플렉션 시스템이 직접 다루는 타입이 아니기 때문에
UPROPERTY로 선언할 수 없다.

// UPROPERTY로 사용할 수 없음
std::map<int32, int32> Values;

다만 TMap이라고 해서 모든 Key와 Value 타입을 무조건 UPROPERTY로 사용할 수 있는 것은 아니다.
언리얼 리플렉션 시스템이 인식할 수 있는 타입 조합이어야 한다.

---

정리

std::map과 TMap은 모두 Key-Value 데이터를 저장하는 컨테이너이다.
하지만 내부 구현 방식은 다르다.

std::map은 보통 균형 이진 탐색 트리 기반으로 구현되며 Key 기준 정렬을 유지한다.
탐색, 삽입, 삭제는 O(log N)이다.

TMap은 해시 기반 컨테이너이다.
Key에 해시 함수를 적용해 위치를 찾기 때문에 평균적으로 탐색, 삽입, 삭제가 O(1)에 가깝다.
대신 기본적으로 정렬을 보장하지 않으며, 해시 충돌이 많으면 성능이 나빠질 수 있다.

또한 TMap은 언리얼 리플렉션 시스템과 함께 사용할 수 있지만,
std::map은 UPROPERTY로 사용할 수 없다.

---

마무리

이번에 std::map과 TMap을 비교하면서 겉으로는 둘 다 Key-Value 컨테이너처럼 보이지만
내부 동작 방식은 다르다는 것을 알게 되었다.

특히 std::map은 정렬된 트리 기반 컨테이너이고,
TMap은 해시 기반 컨테이너라는 점이 가장 큰 차이였다.

언리얼에서 TMap을 사용할 때는 단순히 C++의 std::map과 같은 컨테이너라고 생각하기보다,
해시와 Sparse Array를 이용해 데이터를 관리하는 언리얼 컨테이너라고 이해하는 것이 좋을 것 같다.