[C++ STL] map vs unordered_map

개요

프로그래머스 호텔 방 배정 문제를 푸는데 자료구조로 map을 사용할 경우 TLE가 발생하지만 unordered_map을 사용할 경우 실행 시간이 훨씬 빨라져 AC를 받을 수 있었습니다.

이에 따라 이 두 자료구조의 차이점을 알고 싶었습니다.

다행히도 Peter Ahn님이 잘 정리하신 게시글이 있었고 저는 해당 게시글을 짧게 요약해보겠습니다.

https://gracefulprograming.tistory.com/3

[C++] map vs hash_map(unordered_map)

 

map

map은 기본적으로 레드 블랙 트리(RB Tree) 기반으로 구성되어 있고 이 때문에 모든 데이터는 정렬되어 저장됩니다.

RB Tree는 AVL Tree와 마찬가지로 BST(Binary Search Tree)에 검색 시 O(logN) 수준을 보장하는 Self-Balancing 기능을 추가한 것입니다.

이러한 특성 땜누에 입력되는 키 값의 분포가 고르지 못할 경우 균형을 맞추는데 비용이 많이 투입되고 삽입 및 삭제 성능이 저하될 수 있다는 단점이 있습니다.

 

unordered_map

unordered_map은 map과 달리 hash_table 기반으로 구성되어 있습니다.

따라서, unordered_map은 map과 달리 노드들을 정렬할 필요가 없으며 충분한 hash_table의 크기만 주어진다면 데이터 양이 많아지더라도 조회, 삽입, 삭제 모두 좋은 성능을 보장할 수 있습니다.

물론, hash_table의 크기가 데이터 양에 비해 작다면 hash 충돌로 인해 성능이 저하될 수 있습니다.

 

성능 비교

Peter Ahn님의 게시글을 보시면 알 수 있다시피 정수형 키에 대해서는 unordered_map이 map보다 훨씬 뛰어난 성능을 보여줍니다.

하지만 문자열 키에 대해서는 조금 다른데 키의 길이가 길어질수록 unordered_map의 성능이 급격히 떨어지는 것을 확인할 수 있었습니다.

이는 map에 삽입을 할 때 key를 기반으로 정렬하게 되는데 문자열 비교 함수의 성능은 문자열 전체를 hashing 하는 것에 비해 우수하기 때문입니다.

-> 문자열 전체를 비교하지 않고 앞에서부터 한 글자씩 차례로 비교하기 떄문에 문자열의 길이가 길어지더라도 map은 상대적으로 덜 민감하게 반응합니다.

물론, 키 값들이 모두 동일한 prefix(접두어)를 가지고 있다면 map 또한 성능이 급격하게 떨어질 것입니다.

 

결론

키가 정수형이라면 map 대신 unordered_map을 사용하고 키가 문자열이라면 키 값들을 잘 분석한 뒤 map을 사용할지 unordered_map을 사용할지 판단하면 좋을 것 같습니다.

그래도 단순하게 정리하자면 Peter Ahn님이 말씀하신대로 key를 이용하여 정렬을 해야 하는 케이스가 아닐 경우 대량의 데이터를 저장할 때는 map보다 unordered_map을 사용하는 것을 추천드립니다.

 

출처

https://gracefulprograming.tistory.com/3

[C++] map vs hash_map(unordered_map)