<map> vs. <unordered_map>

두 개의 차이점이 헷갈려서 정리해본다.

unordered_map과 map의 차이는 정렬 여부와 성능에 있다.

1. 정렬 여부

• map:
  • map은 키가 자동으로 정렬된 상태로 저장된다.
  • 내부적으로 이진 탐색 트리(예: 레드-블랙 트리)를 사용하여 데이터가 정렬된 순서대로 저장된다.
  • 삽입, 삭제, 검색 시 최악의 경우 시간 복잡도는 O(log N)이다.

• unordered_map:
  • unordered_map은 정렬되지 않은 상태로 저장된다.
  • 내부적으로 해시 테이블을 사용하여 데이터를 저장한다.
  • O(1)이라는 평균 시간 복잡도를 가지며, 삽입, 삭제, 검색이 더 빠를 수 있다.
  • 단, 해시 충돌이나 최악의 경우(해시 충돌이 많이 발생하면) 시간 복잡도가 O(N)이 될 수 있다.

2. 성능 차이

• map은 내부적으로 트리를 사용하여 정렬된 상태로 데이터를 유지하므로, 삽입, 삭제, 검색에 대해 항상 O(log N)의 시간 복잡도를 가진다.
• unordered_map은 해시 테이블을 사용하여 평균적으로 O(1)의 시간 복잡도를 가진다. 하지만 해시 함수에 의한 충돌이나 해시 테이블 크기 조정에 의해 성능이 떨어질 수 있다. 그러나 평균적으로는 map보다 빠르다.

3. 사용 시 차이점

• map을 사용하는 경우:
  • 데이터를 정렬된 상태로 유지해야 할 때 사용. (예를 들어, 범위 쿼리나 정렬된 데이터를 순차적으로 처리해야 할 때)
• unordered_map을 사용하는 경우:
  • 정렬이 필요 없고 데이터를 빠르게 삽입하고 검색해야 할 때 사용. (예를 들어, 전화번호부, 단어의 빈도 수 계산, 키-값 쌍에 대해 빠른 검색이 필요한 경우에 적합)