알고리즘 문제를 풀다 C++에서 hash table 용도로 활용하는 map 컨테이너에 대한 궁금증이 생겨 찾아보았다.
일반적으로, 나의 경우 map 컨테이너를 주로 사용하는데 어떤 코드에서는 unordered_map 컨테이너를 활용하여 문제를 해결하기도 하였다. 그렇다면 여기서, map과 unordered_map은 과연 어떤 차이가 있을까?
Reference에 따르면,
map: http://www.cplusplus.com/reference/map/map/?kw=map
unordered_map: http://www.cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map
map: pair<const Key, T> 로 이루어진 컨테이너. Key값 기준으로 sorting 되어있음. 이진탐색트리로 구현되면서 sorting하므로 unordered_map보다 value값을 찾는 데에 오래걸릴 수 있음.
unordered_map: map과는 달리 Key 혹은 Value 기준으로 sorting 되어있지 않은 컨테이너. Key값으로 hash value를 찾는 데에 시간이 적게 걸림.(Average: O(1)) 우리가 흔히 사용하는 hash 자료구조에 해당된다고 보면 됨.
정리하면, 알고리즘 자료구조에서는 unordered_map을 일반적인 hash table 자료구조로 사용한다.
(알고리즘 문제에서는 괜찮지만 실무 혹은 개발 프로젝트에서 hash table 활용 시, hash bucket collison 이슈가 발생하지 않도록 하는 것에 주의를 기울여야 한다...!)
