언리얼 TSet, TSparseArray

TSet

• 해시 테이블 기반의 중복 없는 값 저장 자료구조
• 값을 추가하면 자동으로 중복 제거
• 평균 O(1) 시간복잡도로 빠른 검색, 삽입, 삭제
• 순서는 보장되지 않음 (해시 기반이라 무작위)
• 값 자체가 키 역할을 함 (TMap과의 차이점)

TSet Numbers;
Numbers.Add(10);
Numbers.Add(20);
Numbers.Add(10);  // 무시됨 (중복)

bool Has = Numbers.Contains(20);  // O(1) - 매우 빠름

---

TSet 내부 구조

Hash 배열:

• 해시 테이블의 버킷 역할
• 각 버킷은 첫 번째 요소의 인덱스를 저장
• TArray<int32> 타입

TSparseArray (데이터 저장소):

• 실제 데이터를 저장하는 배열
• 각 요소는 3가지 정보 포함:
  • Value: 실제 저장할 값
  • HashNextId: 다음 요소의 인덱스 (체이닝용)
  • HashIndex: 어느 버킷에 속하는지

template
class TSet
{
    TArray Hash;              // 버킷
    TSparseArray Elements;  // 데이터
    
    struct FSetElement
    {
        ElementType Value;
        int32 HashNextId;   // 체이닝
        int32 HashIndex;    // 소속 버킷
    };
};

---

해시 충돌 처리: 체이닝

Separate Chaining 방식

• 같은 버킷에 여러 값이 해싱되면 연결 리스트로 연결
• 포인터가 아닌 배열 인덱스로 연결
• 각 요소의 HashNextId가 다음 요소의 인덱스를 저장

인덱스 기반 연결

• 전통적 연결 리스트는 포인터로 다음 노드를 가리킴
• 언리얼은 배열 인덱스로 다음 요소를 가리킴
• 1차원 배열이지만 인덱스로 연결하면 연결 리스트처럼 동작

---

TSparseArray

• 중간에 빈 구멍이 있을 수 있는 배열
• 요소를 삭제해도 다른 요소를 이동시키지 않음
• 삭제된 자리를 빈 칸으로 남겨두고 나중에 재사용
• 인덱스 안정성: 삭제해도 다른 요소의 인덱스 불변

TSparseArray를 쓰는 이유

해시 체이닝과의 관계

• TSet의 체인은 인덱스로 연결됨
• 중간 요소를 삭제하면 뒤 요소들이 앞으로 이동 → 인덱스 변경
• 인덱스가 바뀌면 체인이 깨짐
• TSparseArray는 삭제해도 인덱스 유지 → 체인 안전

TSparseArray 내부 동작

Data 배열:

• 실제 데이터를 저장하는 배열
• TArray<FElement> 타입

AllocationFlags:

• 비트 배열로 사용 여부 표시
• TBitArray<> 타입
• 1 = 사용 중, 0 = 빈 칸

Free List:

• 빈 칸들을 연결 리스트로 관리
• FirstFreeIndex: 첫 번째 빈 칸 위치
• 각 빈 칸은 다음 빈 칸의 인덱스를 저장

class TSparseArray
{
    TArray Data;           			 // 실제 데이터
    TBitArray<> AllocationFlags;     // 사용 중 인지 (비트)
    int32 NumFreeIndices;            // 빈 칸 개수
    int32 FirstFreeIndex;            // 첫 빈 칸
};

방식	설명	언리얼 사용 여부	장점	단점
Separate Chaining	체인으로 연결	TSet/TMap	삭제 쉬움, Load Factor 높아도 됨	포인터/인덱스 저장 필요
Open Addressing	다른 빈 칸 찾기	X	메모리 효율	삭제 복잡, 클러스터링
선형 탐사	순차적으로 찾기	X	구현 간단	클러스터링 심함
이중 해싱	두 번째 해시 함수	X	클러스터링 적음	해시 함수 2개 필요

---

특성	TSet	TMap
저장 내용	값만	키-값 쌍
해시 키	값 자체	키만
중복	값 중복 불가	키 중복 불가, 값은 가능
검색	Contains(값)	Find(키) 또는 [키]
사용 예시	중복 제거, 집합 연산	딕셔너리, 빠른 조회
코드 예시	TSet<int32> IDs;	TMap<int32, FString> Names;