[C++][hash_map] map과 unordered_map의 차이?

<map과 unordered_map의 차이는 무엇일까?>

=> map과 unordered_map의 차이는 구현방식이다.

map은 균형 이진트리(Red-black tree)로 구현되고, unordered_map(hash_map)은 hash 방식(hash table)으로 구현된다.

즉,  map에 들어가는 element 들은 key에 따라 정렬되어 저장되고, unordered_map은 key의 hash값에 따라서 저장된다.

 

<map과 unorderd_map 중에 성능은 뭐가 좋을까?>

=> 데이터가 적은 경우는 map > unordered_map, 데이터가 많은 경우는 map < unordered_map 성능이 더 좋다.

map의 데이터들은 정렬되어 저장되므로 O(logN)의 탐색 속도를 보장하고, key값으로 탐색하는 unordered_map의 경우 O(1)의 탐색속도를 갖기 때문이다.

참고로 map의 경우 데이터 추가, 삭제 시 비용이 커진다.(그래도 O(logN)의 성능은 보장된다.) 데이터가 적더라도 데이터의 수정이 많이 일어나는 경우는 unordered_map의 성능이 더 좋다는 말이다. unordered_map은 정렬할 필요가 없으므로 데이터 추가, 삭제 시에도 그 성능이 꾸준히 보장된다.

---

★ 참고로 hash_map은 비표준 Container이고, unordered_map이 C++11에서 STL 표준 Container로 추가되었다.

즉, unordered_map이 hash_map과 거의 동일한 기능을 제공한다고 보면 된다.

 

아래 microsoft C++ 공식문서 참조~! 

unordered_map 클래스