[C++] map vs unordered_map

1. map

각 노드가 key와 value 쌍으로 이루어진 트리다. first-key, second-value pair로 저장된다.

내부 원소들이 key에 따라 결정되고, key값을 이용해 value에 접근하기 때문에 key값 중복을 허용하지 않는다.

C++에서 map의 내부 구현은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구성되어 있다. 

데이터를 순서대로 보관한다.

 

2. unordered_map

map보다 검색, 삽입, 삭제가 빠르다. 시간복잡도는 일반적으로 O(1), 최악의 경우 O(n)이다.

해시 테이블 기반으로, 정렬이 없기 때문에 데이터를 순서 없이 보관한다.

데이터가 많을 때 map보다 성능이 좋다.

데이터가 적을 때는 메모리 낭비를 할 수 있고, 검색 시 오버헤드(특정 기능을 수행할 때  드는 자원)가 생길 수 있다. 

key에 유사한 데이터가 많을 경우 해시 테이블 저장이 고르게 분포되지 않을 수 있고, 때문에 해시 충돌이 발생할 수 있다.

 

3. chaining

unordered_map에서 해시함수를 통과한 후 값이 같을 때, 리스트 방식의 체이닝으로 관리를 하면서 최악의 시간복잡도 O(n)이 생긴다.

체이닝은 충돌 발생 시 다른 자리에 값을 저장하는 방법으로, Linear Probing, Quadratic Probing, Double Hashing이 있다.

Linear Probing (선형 프로빙): 해당 해시 값에 자리가 있을 경우 근처 빈 슬롯에 저장하는 방식이다. hash(n), hash(n)+1, hash(n)+2, ... 순서로 검색하고, 테이블의 끝까지 갔을 시 처음으로 돌아와서 검색한다.

Quadratic Probing (이차 프로빙): hash(n)+1^2, hash(n)+2^2, ... 방식으로 검색한다.

Double Hashing (이중 해싱): 서로 다른 두 해시를 사용한다. 충돌 발생 시 다른 해시함수로 다시 해시값을 만드는 것이다.

 

4. 좋은 해시 함수?

SUHA (Simple Uniform Hashing Assumption)을 만족하는 해시 함수가  좋은 해시 함수다. 각 해시 key가 균등하게 분배되는 것이다. 이를 통해 해시 충돌을 막을 수 있다.

 

 

참고자료

https://m.blog.naver.com/dorergiverny/223337764957

https://github.com/Romanticism-GameDeveloper/GameDeveloper-Client-Interview/blob/main/C%2B%2B/map%20vs%20unordered_map.md