[C++] 해시맵(Hash Map)에 대해 알아보자 (std::unordered_map)

[본론으로 들어가기 전에...]

기존의 map은 요소가 자동으로 오름차순으로 정렬되는 이진 탐색 트리(BST) 기반이었다. 그래서 정렬이 필요하지 않은 경우에도 자동으로 정렬되어 불필요한 오버헤드가 있었다. 즉, 오버헤드를 감수하면서 map을 사용하던지, 비표준 라이브러리인 hash_map을 사용해야 했다.

 

그런데, C++11 부터 이런 불편함을 해소해줄 unordered_map 이 등장했다. map과 달리 이진 탐색 트리가 아니라 '해시 테이블'로 구현되어 있는 자료구조로. unorderd_map은 정렬이 자동으로 되지 않고, 요소 검색/삽입/삭제 연산이 O(1) 시간 안에 가능하다. 그래서 우리가 공부해야할 자료구조는 unordered_map 이다 !

 

[unordered_map(hash_map)의 특징]

우선, map은 key - value 쌍의 구조로 데이터를 저장하는 자료구조이다.

그래서 key를 통해 value를 검색할 수 있다.

 

hash_map은 hash 함수를 통해 key를 특정 값으로 변환시키고 이 값을 value를 저장할 공간의 인덱스로 사용한다. 

이 hash_map의 표준 라이브러리로 unordered_map이 쓰이고 있는 거다.

 

[unordered_map 사용법]

* 헤더: <unordered_map>

* 선언: unordered_map<자료형, 자료형> map;

 

* 자료삽입: map.insert(pair<자료형, 자료형>(value1, value2)); 혹은 map.insert(make_pair(value1, value2)); 혹은 map[key] = value;

* 자료검색: map.find(key)->first;  map.find(key)->second; 혹은 map[key];  (first가 key, second가 value)

* 자료삭제: map.erase(key); 혹은 map.erase(map.find(key));

 

* map 사이즈 구하기: map.size();

* map 비우기: map.empty();

* map 초기화: map.clear();

* key에 해당하는 원소의 개수 구하기: map.count(key);

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
int main()
{
    // Create an unordered_map of three strings (that map to strings)
    unordered_map<string, string> u = {
        {"RED","#FF0000"},
        {"GREEN","#00FF00"},
        {"BLUE","#0000FF"}
    };
 
    cout << "Iterate and print keys and values of unordered_map, being explicit with\n"
                 "the type of the iterator, n:\n";
    for( const pair<string, string>& n : u ) {
        cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    }
 
    cout << "Iterate and print keys and values of unordered_map, using auto:\n";
    for(const auto& n : u ) {
        cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    }
 
    cout << "Iterate and print keys and values using structured binding (since C++17):\n";
    for(const auto& [key, value] : u ) {
        cout << "Key:[" << key << "] Value:[" << value << "]\n";
    }
 
    // Add two new entries to the unordered_map
    u["BLACK"] = "#000000";
    u["WHITE"] = "#FFFFFF";
 
    cout << "Output values by key:\n";
    cout << "The HEX of color RED is:[" << u["RED"] << "]\n";
    cout << "The HEX of color BLACK is:[" << u["BLACK"] << "]\n";
}

output:

Iterate and print keys and values of unordered_map, being explicit with
the type of the iterator, n:
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]
Iterate and print keys and values of unordered_map, using auto:
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]
Iterate and print keys and values using structured binding (since C++17):
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]
Output values by key:
The HEX of color RED is:[#FF0000]
The HEX of color BLACK is:[#000000]

 

[C++ 공식 레퍼런스 참조]

https://en.cppreference.com/w/cpp/container/unordered_map

std::unordered_map - cppreference.com