[스터디] 해시 테이블 자료구조 정리

해시 테이블을 사용하는 유니티의 자료구조는 크게 두 가지가 있다.

 

1. Dictionary

2. HashSet

 

두 자료구조 전부 '해시 테이블'을 내부 구조로 사용하기 때문에 먼저 해시 테이블에 대해서 알아보자!

 

해시 테이블은 '키'를 통해 데이터에 빠르게 접근 할 수 있는 자료구조로 내부적으로 해시 함수를 사용해 키를 해시값으로 변환하고, 이를 인덱스로 사용하여 데이터에 접근한다. 

 

해시 테이블의 장점

 

1. 빠른 데이터 접근

키를 통해 거의 '상수 시간'에 데이터를 조회/추가/삭제 할 수 있는 평균 시간 복잡도를 제공한다. 이는 리스트나 배열에서 요소를 찾기 위해 필요한 '선형 시간'과 비교하면 매우 빠르다. 이러한 특성은 게임이 실시간으로 데이터를 처리해야 할 때 매우 유용하다.

 

※ 딕셔너리 vs 리스트

그럼 여기서 딕셔너리와 리스트 두 자료구조를 비교해보자!

 

1. Dictionary

 

# 장점

* 빠른 데이터 검색/추가/삭제

* 'key' 를 통한 데이터 접근

 

# 단점

* 높은 메모리 사용량

* 데이터가 순차적이지 않기 때문에 정렬된 데이터 처리에는 적합하지 않음

 

# 적합한 사용 사례

* 키를 통해 빠르게 접근해야 하는 데이터

* 플레이어 ID와 같은 유일한 식별자를 키로 사용하여, 각 플레이어의 데이터(Ex : 점수, 인벤토리)를 저장하고 관리할 때

* 데이터의 조회가 자주 일어나고, 해당 데이터의 삽입/삭제가 빈번한 경우

 

2. List

 

# 장점

* 데이터가 순차적으로 저장되어, 순차 접근에 최적화됨

* 사용하기 간단하며, 동적으로 크기 조정 가능

 

# 단점

* 특정 요소를 검색하는 데 시간이 오래 걸릴 수 있음 (데이터를 처음부터 순차적으로 탐색해서 검색하기 때문)

* 큰 리스트에서 요소를 추가하거나 삭제하는 과정에서 성능 저하가 발생할 수 있음

 

# 적합한 사용 사례

* 데이터가 추가된 순서대로 처리해야 할 때 (Ex : 적 목록, 이벤트 로그 등)

* 데이터의 순차적 접근이 중요할 때

* 리스트의 크기가 크기 않고, 요소 검색이 빈번하지 않는 경우

* 인덱스를 통한 빠른 접근이 필요한 경우

* 데이터의 추가/삭제 보다는 조회가 더 자주 일어나는 경우

 

@ 나만의 요약 : 보통 딕셔너리가 좋다 => for문돌려 index로 순차적 접근만 구현하는 기능이라면 리스트가 좋다!!

 

 

다시 해시 테이블의 장점으로 넘어가자

 

2. 데이터의 유일성 보장

'HashSet' 과 같은 자료구조는 자동으로 데이터의 유일성을 보장한다. 즉, 중복된 데이터를 추가하려고 할 때 자동으로 거부되므로, 개발자는 데이터의 유일성을 수동으로 관리할 필요가 없다. 이는 예를 들어 플레이어가 특정 아이템을 한 번만 획득할 수 있도록 하는 등의 게임 로직을 구현할 때 유용하다.

 

3. 효율적인 메모리 사용

해시 테이블은 필요에 따라 동적으로 크기가 조정된다. 데이터가 추가되면 해시 테이블의 크기가 자동으로 증가하며, 이는 메모리 사용을 최적화하는데 도움을 준다. 게임에서는 이러한 동적 크기 조정이 메모리 관리를 더욱 효율적으로 만들어 준다.

 

4. 'Dictionary' 같은 자료구조는 키와 값의 명확한 맵핑을 제공한다.

 

5. 데이터 무결성

해시 테이블은 키를 통한 데이터 검색 시 키 충돌을 자동적으로 관리한다. 이는 데이터의 무결성을 유지하는 데 도움을 주며, 실수로 잘못된 데이터 접근이 일어날 가능성을 줄여준다.

 

6. 확장성

해시 테이블은 데이터가 증가함에 따라 자동으로 크기를 조정할 수 있어 확장성이 뛰어나다. 대규모 데이터를 다루는 게임에서는 이러한 특성이 데이터 관리를 용이하게 만들어 준다. 

 

 

그렇다면 이제 Dictionary vs HashSet 차이를 알아보자

 

1. Dictionary

 

# 특징

* 키에 대한 빠른 검색/추가/삭제가 가능

* 키는 해시 함수를 사용하여 내부적으로 인덱싱 됨

* 키-값 쌍으로 구성되어 있어서, 키를 사용하여 빠르게 해당 데이터에 접근 가능

 

2. HashSet

HashSet<T>는 고유한 요소만을 저장하는 컬렉션이다. 리스트와 유사하지만, 모든 요소가 유일해야 한다는 점에서 차이가 있다.

 

# 사용 목적

데이터의 유일성을 보장하면서 빠른 검색이 필요할 때 사용한다. 예를 들어, 게임에서 한 번만 얻을 수 있는 아이템의 ID를 저장하는데 적합하다.

 

# 특징

* 요소의 추가/검색/삭제가 매우 빠름

* 요소가 유일하며, 순서를 보장하지 않음

* 내부적으로 해시 테이블을 사용하여 요소의 존재 여부를 빠르게 확인 가능

 

 

Dictionary vs HashSet 차이점

 

* Dictionary는 키-값 쌍으로 저장하는 반면, HashSet는 값만을 저장하고 모든 값은 고유함

* Dictionary는 키를 통해 빠르게 데이터에 접근하려는 경우에 사용하고, HashSet은 데이터의 유일성을 보장하는데 사용

 

 

@ 나만의 요약 : 데이터에 빠르게 접근하면서 키-값이 중요하다면 Dictionary를 사용, 데이터의 유일성만 중요하다면 HashSet 사용!!

 

즉, 해시 테이블을 사용하려는데 키 값이 필요할 것 같은건 Dictionary.. 키 값 필요없고 먹은 아이템 목록, 생성된 적 목록, 발사된 스킬 구조체 등과 같이 키 값이 딱히 필요없고 그 데이터의 유일성만 필요한 것들은 HashSet 사용!!