C++ Hash와 Map의 차이점

Hash와 Map의 차이점

STL에 보면 Map이라는 컨테이너가 있습니다.

이전에 정리한걸 다시 보면..

 

map

 - 특정 키(key)로 데이터를 접근하고 관리할 수 있다.

 - 키로 값에 접근하며 삽입과 삭제가 빠르다.

이와 같이 정리를 했었습니다.

 

 - 키로 값에 접근한다고 했는데 이것은 이진 탐색 트리(Binary Search Tree)에서 사용되는 키값을 의미합니다.

 - 이진 탐색 트리(BST)입니다. 이진 트리 아닙니다. (최근엔 Red-Black Tree를 사용한다고 합니다)

Map에서 자료를 접근하려 할 때 이진 탐색 트리를 사용한다는 점에서 차이가 있습니다.

 - 이진 탐색 트리는 O(log n)의 속도를 보여줍니다. 하지만 이것보다 더 빠른 탐색 시간을 원할 때 Hash Map을 사용하게 됩니다. (Hash Map의 탐색 속도는 O(1)입니다. 배열로 접근하기 때문입니다.)

 - Map은 자료가 정렬되어 보관됩니다. (Set도 마찬가지입니다.) 반면, Hash Map은 자료를 정렬하지 않습니다.

 

그런데 STL 컨테이너를 보면 Hash Map은 없습니다. 이렇게 속도가 빠른데도 말이죠.

단지 자료가 정렬되지 않아서 그런걸까요?

아닙니다. Hash Map은 STL의 공식 컨테이너에는 속하지 않고 따로 구현된 STL 라이브러리를 사용하셔야합니다.

공식 컨테이너에 들어가지 못한 이유는 바로 탐색 성능이 안정적이지 못해서 입니다.

 - map, set : 삽입, 삭제, 탐색 모두 O(log n) 보장

 - list : 삽입, 삭제 O(1), 탐색, 임의 원소 접근 O(n) 보장

 - vector : 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1) 보장