4. 해시 맵(hash_map)

시퀸스 컨테이너와 연관 컨테이너

---

시퀸스 컨테이너는 vector, list, deque와 같이 순서 있게 자료를 보관한다.

연관 컨테이너는 어떠한 Key와 짝을 이루어 자료를 보관한다.

그래서 자료를 넣고, 빼고, 찾을 때는 Key가 필요하다.

- 시퀸스 컨테이너는 많지 않은 자료를 보관하고 검색 속도가 중요한 경우에 사용한다.

- 연관 컨테이너는 대량의 자료를 보관하고 검색을 빠르게 하고 싶을 때 사용한다.

 

 

연관 컨테이너의 종류

---

연관 컨테이너로 map, set, hash_map, hash_set이 있다. 이것들은 Key로 사용하는 값이 중복되지 않은 때 사용한다. 만약 중복되는 key를 사용할 때는 컨테이너의 앞에 'multi'를 붙인 multi_map, multi_set, hash_multimap, hash_multiset을 사용한다.

 

 

 

가. map, set 과 hash_map, hash_set 의 차이점

---

hash 라는 단어가 있느냐 없느냐의 차이다. 'hash'는 정말 큰 차이다.

 

map과 set 컨테이너는 자료를 정렬하여 저장한다. 그래서 반복자로 저장된 데이터를 순회할 때 넣은 순서로 순회하지 않고 정렬된 순서대로 순회한다.

hash_map, hash_set은 정렬 하지 않으며 자료를 저장한다. 또 hash라는 자료구조를 사용함으로 검색 속도가 map, set에 비해 빠르다.

 

map, set을 사용하는 경우 : 정렬된 상태로 자료 저장을 하고 싶을 때.

hash_map, hash_set : 정렬이 필요 없으며 빠른 검색을 원할 때.

 

 

 

 

나. hash_map, hash_set은 표준이 아니다.

---

map과 set은 STL 표준 컨테이너지만 hash_map, hash_set은 표준이 아니다. 그래서 보통 STL 관련 책을 보시면 hash_map과 hash_set에 대한 설명은 없다. hash_map, hash_set을 쓰려면 라이브러리를 설치해야 할까? 그럴 필요는 없다. STL 표준은 아니지만 오래되지않은 C++ 컴파일러에서는 대부분 지원한다. 윈도우에서는 Visual Studio.NET 이후의 보든 번전에서 지원하다.

 

C++11 이전 버전에서는 TR1 이라는 이름으로 일부 공개했다. TR1에서는 unordered_map, unordered_set이 준비되어있다.

 

 

 

 

hash_map의 자료구조

---

hash_map의 자료구조는 해시 테이블 이다. 해시 테이블에 자료를 저장할 때는 Key 값을 해시 함수에 대입하여 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장한다.

Key 값을 해시 함수에 입력하여 나오는 버킷 번호에 자료를 넣으므로 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정하다.

 

 

 

hash_map을 사용할 때와 사용하지 않을 때

---

해시 테이블은 많은 자료를 저장하고 있어도 검색이 빠르다. 그러나 저장한 자료가 적을 때는 메모리 낭비와 검색 시 오버헤드가 생긴다.

 

Key 값을 해시 함수에 넣어 알맞은 버킷 번호를 알아 내는 것은 마법 같은 것이 아니다. 그러므로 hash_map은 해시 테이블을 사용하므로 검색이 빠르다라는 것만 생각하고 무분별하게 hash_map을 사용하면 안된다. 컨테이너에 추가나 삭제를 하는 것은 list나 vector, deque가 hash_map보다 빠르다. 또 적은 요소를 저장하고 검색할 때는 vector나 list가 훨씬 빠를 수 있다. 

수천의 자료를 저장하여 검색을 하는 경우에 hash_map을 사용하는 것이 좋다.

 

hash_map을 사용하는 경우

1. 많은 자료를 저장하고, 검색 속도가 빨라야 한다.

2. 너무 빈번하게 자료를 삽입, 삭제 하지 않는다.

 

 

 

 

 

hash_map 사용방법

---

hash_map 헤더파일

#include <hash_map>

 

hash_map이 속한 namespace는 표준 STL과 다른 'stdext'이다.

using namespace stdext;

 

hash_map 선언은 아래와 같다.

stdext::hash_map<Key 자료형, Value 자료형 > 변수이름

stdext::hash_map<int, float> hash1;

 

다른 컨테이너와 같이 동적 할당을 할 수 있다.

stdext::hash_map<int, float>* hash1 = new stdext::hash_map<int, float>;

 

 

 

 

 

가. 추가

---

<insert>

 

 

 

나. 삭제

---

<erase>

 

  

 

 

 

다. 검색

---

hash_map에서 검색은 Key를 사용하여 같은 Key를 가지고 있는 요소를 찾는다. Key와 같은 요소를 찾으면 그 요소의 반복자를 리턴하고, 찾지 못한 경우에는 end()를 가리키는 반복자를 리턴한다.

 

 

 

 

라. hash_map을 사용한 유저 관리

---

 

 

 

 

마. lower_bound와 upper_bound

---

hasp_map에 저장한 요소 중에서 Key 값으로 해당 요소의 시작 위치를 얻을때 사용하는 멤버들이다. Key값의 비교는 크기가 아닌 저장되어 있는 요소의 순서이다. 23, 4, 5, 18, 14, 30 이라는 순서로 Key 값을 가진 요소가 저장되어 있으며 Key 값 18과 같거나 큰 것을 찾으면 18, 14, 30이 된다.

 

lower_bound와 upper_bound는 hash_map에 저장된 요소를 일부분씩 나누어 처리를 할 때 유용하다. 예를 들면 hash_map에 3000개의 게임 캐릭터 정보가 저장되어 있으며 이것을 100개씩 나누어 처리하고 싶을 때 사용하면 좋다.

 

 

 

 

번외

---

Visual C++의 hash_map은 map보다 빠르지도 않고 특히 hash_map과 같은 자료구조를 사용하는 컨테이너로 마이크로소프트사에서 만든 CAtlMap에 비해 속도가 아주 느리다.

 

성능이 중요한 곳에 hash_map을 사용한다면 VC++에 있는 것을 사용하지 말고 자체적으로 잘 만들어진 hash 함수롤 사용하거나, C++ 오픈 소스 라이브러리인 boost에 있는 unordered_map을 사용하는 것이 좋을 것 같다. 

Windows 플랫폼에서만 사용한다면 CAtlMap을 사용하는 것도 좋다.

 

 

출처 : Thinking About C++ STL 프로그래밍 (최홍배 지음)