[21.7.22]Map 과 Hash

Map

: binary tree 사용 (red-black tree)

내부 데이터 정렬됨

평균 탐색 시간복잡도는 O(log n)

삽입 / 삭제 O(log n)

key 중복 허용 X

 

 

Hash Map (unordered_map 사용을 권장)

: hash table 사용

내부 데이터 비정렬

평균 탐색시간복잡도는 O(1)

삽입 / 삭제는 O (1)

 

unordered_map

:

평균 탐색 시간복잡도는 O(1)

hash table 사용

내부 데이터 비정렬

key 중복 허용 X

#include< unordered_map > 을 선언해야 함

데이터가 많을 시  map보다 성능 좋음 (유사한 key가 많으면 성능 떨어짐 주의/ 해쉬충돌)