[C++] Hash 자료구조 / unordered_map 사용법(feat. map)

C++은 해시테이블을 unordered_map 이라는 STL로 구현할 수 있다.

unordered_map 클래스

 

* 시간복잡도

해쉬테이블은 key 값으로 탐색하기 때문에 탐색 시간복잡도는 O(1) 밖에 걸리지 않는다. 또한, 정렬할 필요가 없으므로 데이터 추가, 삭제 시에도 그 성능이 꾸준히 보장된다.

 

* map vs unordered_map

map 은 정렬이 된다. 레드블랙트리기반이므로 탐색, 삽입, 삭제에 O(longN)의 시간복잡도가 걸린다.

unordered_map 은 정렬이 안된다. 해시테이블 기반이므로 탐색, 삽입, 삭제에 평균 O(1), 최악의 경우 O(N) 이 걸린다.

 

* 사용방법

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

int main(){
    unordered_map<string, int> map; //선언

    //데이터 삽입
    map.insert(make_pair("a", 1));
    map.insert(make_pair("b", 2));
    map.insert(make_pair("c", 3));

    //데이터 탐색
    map.find("a");
    cout << "map["a"].first: " << map["a"].first; // a
    cout << "map["a"].second: " << map["a"].second; // 1
    map.count("a");//key가 "a"인 원소의 개수 구하기
    
    //데이터 순회
    for(auto& i: map){
    	if(i.first == "b") i.second ++; // map["b"].second = 2;
    }
    
    //데이터 수정
    map["a"] = 2;
    cout << "map["a"].second: " << map["a"].second; // 2

    //데이터 삭제
    map.erase("a");
    
    //기타
    map.empty(); // 비어있으면 true, 그렇지 않다면 false를 반환
    map.size(); // map의 크기를 반환

    return 0;
}

 

*관련문제

코딩테스트 연습 - 완주하지 못한 선수

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> map;
    
    for(auto& person : participant) map[person]++;
    for(auto& person : completion) map[person]--;
    for(auto& person : map) {
        if(person.second != 0) {
            answer = person.first;
            break;
        }
    }
    
    return answer;
}