c++ map 과 hash_map 의 차이

map 은 정렬된 상태로 자료를 저장할 때 사용하고

hash_map 은 정렬이 필요하지않고 많은 자료를 저장하고 빠른 검색을 원할 때 사용한다.

 

map

- 자료를 정렬하여 저장

- 데이터를 순회 할때 넣은 순서가 아닌 정렬된 순서로 순회

- 이진탐색트리 탐색 속도 O(log n) 보장

hash_map

- 자료를 정렬하지 않고 저장

- 배열로 접근 탐색 속도 O(1) 이상

- 많은 자료를 저장하고 있어도 검색이 빠르다.

- 적은 자료를 저장하고 있을 때는 메모리 낭비와 검색 시 오버헤드가 발생한다.

 

컨테이너 추가 삭제

list, vector, deque > hash_map 보다 빠르다

적은 요소를 저장하고 검색

list, vector > hash_map 훨씬 빠르다

 

hash_map은 표준 STL은 아니다.

- STL의 공식 컨테이너에 속하지 않는다.

- 해쉬키가 충돌이 나게 되면 계속 충돌이 발생하여 탐색 성능의 안정성을 보장 못한다.

- c++에서 지원을 하긴 한다.