map STL에 속한 컨테이너 중 하나로 key와 value로 이루어져 있으며 이는 pair 객체 형태로 저장된다.
unordered_map은 무엇인가?
unordered_map은 hash_table 기반의 hash container 이다. 기존의 map과 달리 이진 탐색트리가 아닌 해시 테이블로 구성 되어있다. 언뜻보면 hash_map과 똑같다고 볼 수 있지만 hash_map은 비표준 컨테이너 인데 반해 unordered_map은 c++11에서 STL 표준 컨테이너로 추가되었으며, hash_map과 거의 동일한 기능을 제공한다고 한다. hash_map과 동일하다고 하지만 MSDN에서는 표준 컨테이너인 unordered map 사용을 권장하고 있다.
Hash Table은 무엇인가?
key아 value로 된 쌍을 저장하는 자료구조이고, c#에서 Dictionary와 같다.
map과 unordered_map의 차이점
map은 자료를 저장할 때 자동으로 정렬을하고, unordered_map은 정렬하지 않는다. 일반적으로 unordered_map이 map보다 성능이 더 좋지만 데이터의 양이 많으면 많을수록 map보다 성능이 더 떨어진다고 한다. 이유는 균형트리는 이론상 무조건 균형을 맞추게 되어 있기 때문이다. 따라서 데이터가 작다면 unordered_map을, 크다면 map을 사용하는 것이 바람직하다.
map과 unordered_map의 장단점
map의 장점 : 컨테이너에 속한 list나 vector보다 탐색 속도가 빠르기 때문에 검색에는 최적의 컨테이너이다. map의 단점 : 키를 새로 추가할 때마다 정렬된 위치를 찾아서 추가를 해야 하므로 대용량의 맵을 작성하는 데에는 시간이 많이 소요됨
unordered_map의 장점 : hash로 인해 key를 통한 value로의 접근이 빠르고 적은 양의 자료에 유리 unordered_map의 단점 : 해시 충돌로 인하여 성능이 저하 될 수 있고 버킷으로 인해 메모리 사용양이 증가함
map과 unordered_map의 시간 복잡도
map
unordered_map
검색
O(logN)
O(1)
삽입
O(logN)
O(1)
삭제
O(logN)
O(1)
map 활용 시 주의사항
자료를 저장할 때 자동으로 정렬된 상태로 저장하기 때문에 삽입 삭제가 빈번하면 안됨.
map이 사용하는 자료구조
map이 사용하는 자료구조는 "레드 블랙트리(Red-Black Tree)"라는 자료구조이다.
레드 블랙트리는 무엇인가?
자가균형이진탐색 트리로써, 대표적으로 "연관배열" 등을 구현하는데 쓰이는 자료구조이다. 트리에 n개의 원소가 있을때 O(logn)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
레드 블랙트리는 어느 경우에 사용되는가?
이진 탐색 트리 중에 값이 한쪽으로 치우치게 되는 경우가 있다. 이런 경우, 이진 탐색 트리의 검색 효율을 나쁘게 하므로, 균형을 바로 잡기 위해서 해당 자료구조를 사용한다.
map에서 사용하는 이유는?
map은 많은 자료를 정렬하여 저장하고 있고 빠른 검색을 필요로 할 때 자주 사용하게된다. 그러므로 map을 구현을 할 때 레드 블랙트리를 참고하면 좋을 것 같다. 복잡한 자료구조 이지만, 사용하는데 있어서 효율적이고, 최악의 경우에도 상당히 우수한 검색 속도를 보여준다.
