250923 언리얼엔진 본캠프 35일차 unordered_map

unordered_map

unordered_map은 map이나 vector 등과 같이 STL의 컨테이너 중 하나로 자료구조 특성상 map보다 삽입, 삭제, 원소 접근 등이 빠르게 이루어진다. 이는 Red-Black트리로 이루어진 map과는 다르게 헤쉬 테이블(Hash Table)로 구현한 자료구조이기 때문에 O(1)의 시간복잡도를 갖게된다.(지난번 글에서 우리는 map의 시간복잡도는 최악의 상황에서도 logN을 보장함을 보였었다.) 또한 unordered_map은 오름차순(또는 프로그래머의 재량에 따라 내림차순)으로 자동 정렬되는 map과는 다르게 정렬을 별도로 정렬을 하고 있지 않는다.

 

데이터가 많을 때는 unordered_map

처리해야할 데이터가 많을 때는 map에 비해서 좋은 성능을 보이기에 unordered_map이 사용되곤 한다 다만 데이터가 적을 때는 메모리 낭비가 발생하거나 검색 시 오버헤드가 발생할 수도 있다. 또한 key에 유사한 데이터가 많을 경우 해쉬 테이블의 저장이 고르게 분포되지 않을 수 있고 해쉬 충돌이 발생할 수 있다.

 

 

 

헤쉬 테이블(Hash Table)이 뭐길래?

unordered_map은 내부 구조가 헤쉬 테이블로 구현되어 있고 이로 인해서 map에 비해서 검색이나 삽입, 삭제가 빠르게 이루어진다고 설명했다. 그러면 왜 그런 특징이 생기는 걸까? 헤쉬 테이블을 이해하기 위해서는 일단 헤쉬(Hash)에 대해서 먼저 알아보아야 한다. 헤쉬는 어떤 데이터를 특정한 연산을 통해서 특별한 값으로 변환시켜 주는 개념이다.

출처 : 위키피디아 헤쉬함수

 

hash 연산을 하는 함수를 해쉬 함수라고 하며 해쉬 알고리즘은 MD5, SHA 등 여러 종류가 존재한다고 한다. STL에서는 자체적인 헤쉬 함수를 제공하며 이러한 Hash 연산을 적극적으로 활용하는 map이 따로 hashmap이라고 존재하는데 비표준 컨테이너이기 때문에 이식성이 떨어져 비주얼 스튜디오에서는 권장하지 않는 방법이라 unordered_map을 사용하라 권한다. 하여튼 이러한 해쉬 함수를 통해서 key를 특정 값으로 변환시키고 이 값을 value를 저장할 공간의 인덱스로 활용하게 된다. 여기서 저장되는 공간은 보통 bucket 또는 slot이라고 부르게 된다. 함수마다 다르지만 어느 함수는 해시 함수의 반환 값을 bucket size로 나눈 나머지 값을 인덱스로 사용하기도 하며 이는 key를 통해서 value가 저장된 인덱스에 상수 시간에 접근할 수 있기에 표준적으로는 O(1)의 시간복잡도를 가지게 된다.

 

 

 

헤쉬 충돌

문제는 이러한 해쉬 함수에서 발생한다. 넣을 수 있는 key는 무한한데 반해서 bucket의 사이즈는 유한하다는 점과 그렇기에 확률상 key값이 다르더라도 함수가 동일한 값을 반환하는 경우도 있다. 결국 반환받는 헤쉬가 같으니 서로 다른 두 value의 인덱스가 같아지게 되는 대참사가 발생한다(...) 이러한 현상을 헤쉬 충돌이라고 한다. 이를 완벽하게 해결할 방법은 사실상 없다고 봐야 한다. 그저 헤쉬 함수를 설계할 때 충돌을 대비해서 최대한 잘 설계해 두는 등의 예방책이 최선인 상황이며 오히려 헤쉬 충돌이 발생했을 때를 대비하는 방법을 알아두는 것이 중요하다. 당장 unordered_map은 헤쉬 충돌을 방지하여 체이닝(chaining)을 사용하고 있다. 간단하게 표현하자면 기존에 값이 존재하는 인덱스가 반환되면 그 인덱스의 뒤를 가리키는 포인터를 생성하여 기존의 값 뒤에 새로 넣을 값을 넣고 체인처럼 연결하는 방식이다. 자세히는 기회가 된다면 알아보도록 하자.

 

 

 

참고 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

해시 함수 - 위키백과, 우리 모두의 백과사전

[C++] 해시맵(Hashmap)을 이해해보자 | std::unordered_map | 기술면접

[C++] 해시맵(Hashmap)을 이해해보자 | std::unordered_map | 기술면접