251029 언리얼본캠프 55일차 TSparseArray와 TSet

TSparseArray와 TSet

지난 시간에는 TMap에 대해서 공부해 보았다. std::map와 비슷하면서도 다른 특성을 지니고 있어 그 차이를 비교하며 공부했었다. std::map은 내부자료 구조는 Red-Black트리로 이루어져 있다 했었는데 TMap의 내부 구조는 어떨까? TMap은 내부 구조가  TSet으로 이루어져 있다. 또 TSet은 TSparaseArray로 이루어져 있다. 이건 뭘까?

 

TSet

TSet은 고유한 요소들만 저장하는 해시 기반의 집합이다. TSet이 나오면 또 빠질 수 없는 게 비슷한 친구인 std::set(이하 set)이다. set은 내부 구조가 map과 같은 Red-Black트리 구조라 O(log N)의 속도를 갖지만 TSet은 앞서 말했듯 해시 테이블 기반이라 O(1)의 매우 빠른 속도를 갖는다. TSet은 앞서 설명했듯 TSparseArray를 내부 저장소로서 사용하고 있는데 Elements와 Hash로 구성되어 있다. Elements는 TSparseArray<TSetElement> 타임의 멤버로서 실제로 저장할 값과 해시 충돌 시 다음 요소를 가리키는 NextHashIndex를 가진다. Hash는 int32 타입의 배열로서 각 인데스를 버킷이라고 부른다. 이 배열은 Elments의 인덱스를 저장한다. TSet은 해시충돌을 분리 연결법으로 해결하는데 일반적인 포인터 기반의 연결리스트가 아니라 인덱스를 이용한 리스트를 구현한다.

 

TSparseArray

TSparseArray는 구멍이 있을 수 있는 배열로서 요소가 추가되거나 제거될 때 다른 요소들의 인덱스가 절대 변하지 않도록 보장한다. 예컨데 인덱스가 순서대로 1, 2, 3이 있었는데 2번 인덱스의 요소를 제거하면 1, 빈 공간, 3 이런 식으로 빈 공간이 존재할 수 있고 이러한 빈 공간을 구멍으로 표시하고 그대로 둔다. 내부적으로는 Data와 AllocationFlags로 이루어져 잇는데 Data는 실제 요소를 저장하는 TArray로서 요소가 제거되어도 배열에서 지워지지 않고 쓰레기 값으로 남는다. AllocationFlags는 TBitArray라는 비트 배열을 사용한다. Data 배열의 각 인덱스가 현재 유효한 요소를 담고 있는지 빈구멍인지 비트로 표시한다.