언제 사용해 ???

• 데이터의 존재 유무 만 궁금할 경우 → set

• 데이터에 대응되는 데이터를 저장하고 싶은 경우 → map

• 속도가 매우매우 중요해서 최적화를 해야하는 경우 → unordered_set, unordered_map

  (insert, erase, find 모두 O(1)O(1). 최악의 경우엔 O(N)O(N) 그러므로 해시함수와 상자 개수를 잘 설정해야 한다!)

hash 함수를 통해 데이터가 저장되는 과정

#include <unordered_map>

Hash Map

// 기본적으로 map의 특징을 갖되 + 해쉬의 특징이 더해진 것임

• hash_table 기반의 hash container
• 시간복잡도 O(1) 보장 //map은 O(log N)
• hash_table을 통해 참조하므로 각 node들을 정렬할 필요 없음
• 충분한 hash_table의 크기만 주어진다면, 데이터 양이 많아지더라도 꾸준히 조회, 삽입, 삭제의 성능을 보장할 수 있음

💡기본 함수

#include <unordered_map>

unordered_map<자료형> m1;
unordered_map<자료형, 자료형> m2;

1. 삽입
insert({key.value});
map_name[key] = value;

2. 삭제
clear() //초기화
erase(key) //key값의 value 삭제

3. 조회
count(key) //key값에 해당하는 원소 개수 반환
find(key) //key값에 해당하는 원소를 찾는 함수
//if key is contained, then iterator else map_name.end()

4. 크기
size()
empty() //map이 비어있는지 확인

구현예시

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

int main(){
    
    unordered_map<string,int> um;
    
    if(um.empty()){
        cout<<"unordered_map은 비어있습니다"<<endl;
    }
    
		//삽입 ex.
    um.insert(make_pair("key",1)); //key-value형태로 넣어야하므로 make_pair(,) 이용
    um["banana"]=2;
    um.insert({"melon",3});
    
    cout<<"unordered_map의 크기는 "<<um.size()<<" 입니다"<<endl;
    
		//조회 ex.
    for(pair<string,int> elem : um){ // auto로 해도 무방
        cout<<"key : "<<elem.first<<" value : "<<elem.second<<endl;
    }
    
    if(um.find("banana")!=um.end()){ // find 대신 count로 확인 가능
        um.erase("banana");
    }
    
    cout<<"unordered_map의 크기는 "<<um.size()<<" 입니다"<<endl;
    for(auto elem : um){
        cout<<"key : "<<elem.first<<" value : "<<elem.second<<endl;
    }
    
    return 0;
}

#include <unordered_set>