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) 보장




Hash Map의 경우 Hashing Key를 이용해 데이터에 접근하는데 이 Hashing Key를 생성하는 방법은 여러가지입니다.

 - 예를 들면, 구성하는 모든 자료를 각각의 바이트 별로 더하거나, 자릿수에 가중치를 두는 방법도 생각해 볼 수 있습니다.

 - 이렇게 생성된 키를 이용해 배열의 인덱스로 사용하고 접근하기 때문에 접근 속도가 O(1)이 되는 것입니다.

하지만, Hashing Key가 겹쳐서 충돌이 일어나게 된다면 빈 영역을 찾아서 저장해야 합니다.

 - 충돌이 한번 일어난 지역에서는 계속 충돌이 일어나기 때문에 그 근처에 자료가 몰리게 됩니다.

따라서, Hash Map에서는 Hashing Key를 얼마나 잘 생성하는가에 따라 성능이 좌우됩니다.

 - Hashing Key 값이 랜덤하게 분포되어 있을 때 가장 좋은 성능을 발휘합니다.



 Hash Map

Map 

 자료 탐색에 Hashing 사용

 자료 탐색에 이진 탐색 트리 사용 (최근엔 Red-Black Tree)

 탐색 속도 O(1) 이상 : Key값 분포에 따라 다름

 탐색 속도 O(log n) 보장 

 저장된 내부 자료 정렬하지 않음

 저장된 내부 자료 정렬 


'Programming Language > C/C++' 카테고리의 다른 글

C++ 가상 함수 (virtual) - 기본  (0) 2014.11.07
C++ 상속  (0) 2014.11.07
C++와 Java의 차이점  (0) 2014.10.13
C++ STL  (0) 2014.10.10
C++ 템플릿  (0) 2014.10.10
Posted by 긍정왕오킹