[Unity] 유니티(C#) 자료구조 - Dictionary와 SortedDictionary

조재훈·2024년 7월 1일

Dictionary<TKey, TSet>

유니티에서 Dictionary<TKey, TSet>는 System.Collections.Generic 네임스페이스에 있는 제네릭 클래스이며 키-값 쌍으로 데이터를 저장하고 관리하는 데 사용된다

해시 테이블 기반의 자료구조라 Key를 사용하여 Value를 효율적으로 검색, 추가, 삭제할 수 있다

이 타입은 HashTable 타입과 유사하지만 해쉬 테이블 자료형의 경우 비제네릭이라 자료형을 명시하지 않아 박싱/언박싱이 필요하므로 성능면에서 딕셔너리가 우월하므로 가급적 딕셔너리를 사용하자

딕셔너리는 해시 테이블 기반의 자료 구조로, 버킷이라는 배열로 구성되며 하나 이상의 키-값 데이터가 저장될 수 있다. 키를 받으면 해시 함수를 사용해 키를 해시 코드로 변경하고 이렇게 나온 해시 코드를 버킷 배열의 인덱스로 사용해 데이터를 사용하고 검색한다(모든 자료형에는 GetHashCode라는 함수가 있음)

해시 충돌을 방지하기 위해 Chaining 또는 Open Addressing 등의 기법을 사용할 수 있음

선언과 초기화

선언할 때 키의 자료형, 값의 자료형을 명시해주고 다른 자료구조와 비슷하게 선언한다

// 선언
public Dictionary<int, string> idCards;

// 기본 생성자로 초기화
idCards = new Dictionary<int, string>();

// 초기 용량을 지정해서 초기화 -> 대량의 데이터 예상 시 유용
// 초기 용량을 지정하면 해시 충돌의 확률을 줄이고 데이터가 추가될 때 배열이 가득차면 새로운 배열을 할당하는 과정을 줄일 수 있어 성능을 최적화할 수 있음
idCards = new Dictionary<int, string>(100);

// 초기 데이터 지정(1번째)
idCards = new Dictionary<int, string>
{
	{1, "황성빈"},
    {2, "윤동희"},
    {3, "고승민"}
}

// 2번째 방법
idCards = new Dictionary<int, string>
{
	[1] = "황성빈",
    [2] = "윤동희",
    [3] = "고승민"
}

// 기존 컬렉션 복사
// 딕셔너리 타입이나 IDictionary 타입으로 복사가 할 수 있음

// Enumerable로 생성
// LINQ를 사용하여 `IEnumerable<KeyValuePair<TKey, TValue>>`를 딕셔너리로 변환할 수 있음

함수

Add(TKey key, TValue value)

딕셔너리에 키-값 쌍을 추가한다. 이미 존재하는 키를 추가하려고 하면 예외가 발생함

idCards.Add(3, "레이예스");	// O
idCards.Add(0, "이대호");	// X

예외가 발생하지 않게 하려면 TryAdd 함수를 사용하자

ContainsKey(TKey key)

key와 일치하는 키가 딕셔너리에 존재하는 지 확인한다. bool 값 반환

idCards.ContainsKey(0);

ContainsValue(TValue value)

value와 일치하는 값이 딕셔너리에 존재하는 지 확인한다. bool 값 반환

idCards.ContainsKey(0);

Remove(TKey key)

지정된 키를 가진 키-값 쌍을 딕셔너리에서 제거한다. 제거에 성공하면 true, 실패하면 false 반환

idCards.Remove(2);

Clear()

딕셔너리의 모든 키-값 쌍을 제거한다

Count 프로퍼티

딕셔너리에 저장되어 있는 키-값 쌍의 개수를 반환한다

Keys

딕셔너리에 있는 모든 키를 가져오는 프로퍼티

ICollection<int> keys = idCards.Keys;
foreach(int key in keys)
{
	Debug.Log(key);
}

// 0 1 2 3

Values

딕셔너리에 있는 모든 값을 가져오는 프로퍼티

ICollection<string> values = idCards.Values;
foreach(string value in values)
{
	Debug.Log(value);
}

// 황성빈 윤동희 고승민 레이예스

[Tkey key] 연산자

딕셔너리[index]를 하게 되면 키에 맞는 값을 참조할 수 있다

장단점, 사용할만한 곳

장점
- 빠른 검색, 삽입, 삭제
  - 위 작업이 모두 O(1)의 시간 복잡도이므로 빠른 작업이 가능하다
- 유연한 Key 타입
  - 해쉬 코드로 변경할 수만 있다면 모든 타입을 Key의 자료형으로 사용할 수 있고 제네릭이라 타입 안정성을 보장할 수 있다
- 중복 키 허용 X
  - 딕셔너리의 각 Key는 고유하므로 데이터의 무결성을 유지할 수 있다
  - 중복 값은 허용할 수 있게 만들 수 있다
- 편리한 데이터 접근
  - 인덱서[]를 사용해 키를 통해 값에 접근하고 수정할 수 있다
단점
- 메모리 오버헤드
  - 해시 테이블과 연결 리스트를 사용해 해시 충돌을 처리하므로 추가적인 메모리 오버헤드가 발생한다
- 순서 예측 불가
  - 딕셔너리는 데이터가 추가된 순서대로 데이터를 유지하지 않으므로 순서가 중요한 경우에는 SortedDictionary나 OrderedDictionary를 사용하는 것이 좋음
- 해시 함수의 품질에 의존
  - 해시 함수가 고르게 분포되지 않으면, 해시 충돌이 많이 발생해 성능이 저하될 수 있음
- 키의 불변성 필요
  - 키는 불변이어야 하며, 그렇지 않으면 해시 코드가 변경되어 데이터에 접근할 수 없게 됨
사용할만한 곳
- 빠른 검색이 필요한 경우
- 키-값 매핑이 필요한 경우
- 설정 데이터 관리
- 캐싱
- 다국어 지원

SortedDictionary

SortedDictionary, 이름에서 유추할 수 있듯이 정렬된 Dictionary 자료형이다. Dictionary와 똑같이 키-값 쌍 데이터를 저장하고 관리하며 제공하는 함수들도 비슷한 편이다

하지만 Dictionary는 해시 테이블 기반으로 구현되어 있는 반면, SortedDictionary는 데이터를 정렬된 순서대로 유지해야 하기에 이진 탐색 트리(레드-블랙 트리) 기반으로 구현되어 있어 키를 자동으로 정렬한다

기본적으로 Key 자료형의 정렬 순서(예. int면 오름차순)로 정렬되지만 커스텀 정렬자를 통해 사용자 입맛대로 정렬할 수 있다

public Dictionary<int, string> idCards;
public SortedDictionary<int, string> sortedIDCards;

idCards = new Dictionary<int, string>()
{
    [0] = "황성빈",
    [2] = "고승민",
    [1] = "윤동희"
};

sortedIDCards = new SortedDictionary<int, string>()
{
    [0] = "황성빈",
    [2] = "고승민",
    [1] = "윤동희"
};

// 출력해보면
// 황성빈 고승민 윤동희
// 황성빈 윤동희 고승민

// 자동으로 int형 key값의 오름차순에 따라 정렬되어 저장된다

함수는 Dictionary에서 제공하는 것과 매우 비슷하므로 패스

Dictionary와 SortedDictionary를 비교해보자

성능
- 삽입, 삭제, 검색
  - Dictionary는 평균적으로 O(1)
  - SortedDictionary는 O(log n) -> 트리를 생각해보면 됨
- 메모리 사용
  - Dictionary는 메모리 오버헤드가 비교적 적다
  - SortedDictionary는 정렬하면서 트리 구조를 유지하기 위해 추가적인 메모리를 사용함

따라서 키의 순서가 중요하지 않고 빠른 검색, 삽입, 삭제가 필요한 경우에는 Dictionary
키가 정렬된 상태로 유지되어야 하며 범위 검색이 필요한 경우에는 SortedDictionary를 사용하자