map
- 레드 블랙 트리 기반
- 검색속도가 빠른 Binary Search Tree(BST) + Self-Balancing 기능을 추가
- O(logN)을 보장하는 수준으로 Balancing
- 키 값의 분포가 고르지 못할 경우 node rotation에 대한 비용이 계속 발생하기에 Insert / Delete 성능이 저하
- 물론 최악의 경우에도 O(logN)의 성능은 보장
unordered_map
- 해시 테이블 기반의 hash container
- node 정렬할 필요가 없음
- 주어진 테이블의 크기가 충분하다면 insert/delete/search의 성능을 보장
Key가 int인 경우
- map은 캐시 미스로 인하여 데이터량이 많아질 경우 소요 시간이 증가
- unordered_map은 O(1)의 시간 복잡도 유지
Key가 문자열(const char*)인 경우
- map은 insert 할 시, 문자열 전체를 hashing 하지 않고 비교 함수를 통해 정렬
- 문자열 비교 함수 성능 > 문자열 전체 hashing
- 문자열 비교 함수 성능
- 앞 글자부터 한 글자씩 차례로 비교하여 크고 작음을 분별
- 문자열 길이에 크게 퍼포먼스 영향을 받지 않음
- key 문자열의 접두사가 같거나 유사하면 비교 함수의 성능은 저하됨
- key 문자열의 분포가 고르면 map의 성능이 우수
- 문자열 전체 hashing
- 문자열 길이가 길수록 key hashing 성능(unordered_map)은 저하
결론
- 데이터가 많은 경우에는 unordered_map 이 map 보다 우수한 퍼포먼스
- 문자열을 키로 사용하는 경우 문자열이 길어질수록 성능은 map > unordered_map
- 유사도가 높은 문자열 집합을 키로 사용하는 경우에는 map 의 성능이 저하
적은 데이터의 경우 성능이 unordered_map < map인 이유?
- hash function 연산 비용 + hash table 탐색 시간 소요
- ordered_map은 key 자체로 탐색을 하기 때문에 상대적으로 빠름
- 데이터가 많아질수록 hash 탐색이 유리해진다고 보면 됨
출처
