[Basic C++] #1 Map, Unordered_map, 해쉬 테이블

[Basic C++] #1 Map, Unordered_map, 해쉬 테이블

 

자료구조 중 해쉬 테이블(Key-Value-Pair)과

C++ STL이 제공하는 컨테이너 "map" , 그리고 "unordred_map"에 대해서 알아보겠습니다.

 

 

---

 

Hash Table(해쉬 테이블), key-value 쌍, 자료 구조

해쉬 테이블이란, "키"를 해쉬 값으로 매핑하여, 이 해쉬 값을 인덱스 혹은 주소 삼아 "값"을 "키"와 함께 쌍으로 저장하여 검색이 빠른 연관 배열 자료구조입니다 -"키"와 "값"의 1대 1 연관 관계를 형성하는 자료구조입니다. 쉽게 말하자면, "Key-Value"를 한 쌍으로 저장하는 자료구조입니다.

이때, 키 값을 입력으로 받는 해쉬 함수는 한 쌍으로 저장될 "값"의 저장 위치, 혹은 bucket slot의 인덱스를 반환하며, 최종적으로 "키"와 "값"의 매칭을 가능하게 합니다.

 

---

1. 장점

• 다량의 데이터를 적은 리소스만을 사용해서 관리할 수 있다.
• "키"를 통해 "값"에 빠르게 접근할 수 있습니다. 평균 시간 복잡도는 O(1)입니다.
• 해쉬 값을 통해 "키"를 복원할 수 없기 때문에, 정보 보호 기술로도 활용됩니다.
• 길이가 서로 다른 "키" 값에 대해서, 일정한 길이의 "해쉬"를 만들기 때문에, 효율적입니다.

2. 단점

•  충돌 문제가 존재합니다. 다른 키 값에 대한 Hash Funciton의 출력 값이 같을 경우를 의미합니다.
• 해쉬 함수에 대한 의존도가 높다.
• 공간 복잡도가 높다.
• 연속적인, 혹은 순서가 존재하는 배열에는 비효율적이다. "캐시의 지역성"은 캐쉬 메모리의 Hit Rate를 최대화하기 위해, 데이터의 지역성을 원칙으로 했을 때 생기는 비효율성과 일맥상통합니다.

 

---

std::map, 트리 자료구조

 

Map은 키와 값의 쌍으로 이루어진 데이터의 집합입니다. 각 노드는 "Key"와 "Value"로 이루어져 있으며, 중복을 허용하지 않습니다.

C++의 STL은 "map"이라는 연관 컨테이너를 제공합니다. map은 각 원소가 "Key"와 "Value"를 하나로 묶는 pair <Key, Value>의 형태로 이루어져 있으며, 이와 관련된 실행 동작들(삽입, 삭제, 검색)은 O(log n)의 시간 복잡도를 가지고 있습니다. 

Map의 주요 특징은 자료를 저장할 때 항상 내부에서 정렬 작업을 실행합니다. 이 정렬 작업은 Key값을 기준으로 오름차순으로 진행됩니다. Default 정렬 방법은 오름차순이며, 내림 차순으로 정렬을 원할 경우, map <Key, Value, greater>를 사용합니다.

예제 코드를 통해 map의 사용 방법에 대해서 알아보겠습니다.

 

코드

#include <map> 	// 헤더파일 추가
#include <utility> 	// pair 클래스 사용을위해 헤더파일 추가
using namespace std;

int main ()
{
    map<string, int> map1;
    
    // 삽입
    map.insert(make_pair("Alice", 100));
    map.insert(make_pair("Ben", 200));
    
    // 검색
    if(map.find("Alice") != map.end())
    {
    	cout << "Alice is found!" << endl;
    }
    
    // 반복문을 통해 검색
    for(auto it = map.begin(); it != map.end(); it++)
    {
    	cout << it->first << ' ' << it->second << endl;
    }
    
    // 범위 기반 반복문
    for(auto it : map)
    {
    	cout << it.first << ' ' << it.second << endl;
    }
    
    // 특정 요소 삭제
    map.erase(map.begin()+2);
    map.erase("Alice");
    // 모든 요소 삭제
    map.erase(map.begin(), map.end());
    map.clear();
}

 

---

Unordered map, 해쉬 테이블 자료구조

Unordered map은 데이터를 저장할 때, 정렬 작업을 수행하지 않습니다. 따라서, map보다 빠른 검색을 가능하게 합니다. map과 같이, 중복된 데이터를 허용하지 않으면서, map보다 더 많은 데이터를 다룰 때 더 좋은 성능을 보여줍니다.

map과 사용방법은 크게 다르지 않으므로, 바로 예제 코드를 살펴보겠습니다.

 

코드

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
    
    unordered_map<string,int> um;
    
    // 공백 unordered_map
    if(um.empty()){
        cout<<"unordered_map은 비어있습니다"<<endl;
    }
    
    // 삽입
    um.insert(make_pair("Key",1));
    um["Key2"]=2;
    um.insert({"Key3",3});
    
    // 검색 (반복문)
    for(pair<string, int> pair : um)
    	cout << pair.first << ' ' << pair.second << endl;
    
    // 검색 (iterator)
    for(auto it = um.begin(); it != um.end(); it++)
    	cout << it->first << ' ' << it->second << endl;
    
    // find() 사용
    if(um.find("Key1" != um.end())
    	cout << Key1 is found! << endl;
    
    // 범위 기반 검색
    for(auto pair : um)
    	cout << pair.first << ' ' << pair.second << endl;