(ordered) Map vs Unordered Map

C++에서 map은 red-black tree로 구현이 된다.

Unordered Map은 hash table로 구현이 된다. 

차이점

1. map과 unordered map의 큰 차이점은 구현에서부터 이미 차이가 난다.

2. map은 탐색 연산의 시간 복잡도가 O(log N)인 반면 unordered map은 hash table을 이용하므로 O(1)

3. map은 AVL 트리와 같이 삽입/삭제 시 항상 밸런스를 맞추기 위해 정렬을 하지만, unordered map은 그렇지 않다.

결론

1. 정렬을 필요로 하는 경우가 아니라면 연산 속도 면에서 unordered map이 훨~~~~~씬 유리

2. 일반적으로 key값이 짧고, int형인 경우 unordered map을 권장( 그 이유는 hash function에 대해 또 다른 설명이 필요하므로 여기서는 생략)

3. key값이 길고 복잡하며, 유사한 값이 많을 경우 unordered map의 Hash Collision으로 인해 성능이 저해될 수 있다.