[C++] STL unordered_set, unordered_map (Hash) 정리 및 사용법

안녕하세요 기회개발자 기개입니다.

오늘은 Hash로 사용할 수 있는 unordered_set과 unordered_map에 대해서 알아보려고 합니다.

 

Hash는 빠른 검색을 할 때 사용하기 매우 유용합니다.

검색을 할 때, 해시충돌이 많이 일어나지 않는 이상

O(1)의 시간이 걸리게 되니 코딩테스트할 때 값이 존재하는지 안하는지를 파악하는데 좋습니다.

 

set과 map의 차이 처럼 차이는 한 가지 밖에 없습니다.

unordered_set은 key만 가지고, unordered_map은 key와 value를 가지고 있습니다.

 

Hash에 대해서 알아보고, unordered_set과 unordered_map의 사용법에 대해서 알아보도록 하겠습니다.

 

 

1. Hash란

1) 검색과 삽입 및 삭제가 매우 빠르다. Hash 함수가 잘 설계되어 있다면, 검색과 삽입 및 삭제 하는데 O(1)의 시간이 걸리게 됩니다. Key(index)와 value(실제 데이터)가 한 쌍으로 존재하기 때문입니다. 2) 해시함수 설계 문자열이 실제 데이터라면, 문자 하나하나를 값으로 변경해 key를 얻어내는 것이 해시함수의 역할입니다. 입력되는 실제 데이터에 따라 해시함수를 적절하게 수정하는 작업이 필요합니다. 여러 데이터에서 같은 key 값이 나오게 되면 같은 key에 여러 value들이 연결될 수 있기 때문입니다. 3) 충돌 새로 입력되는 데이터를 해쉬함수에 돌렸을 때 이미 데이터를 차지하고 있는 key 값과 같은 값이 나올 경우 충돌이라고 합니다. 이런 충돌이 많아질 경우 검색과 삭제의 속도가 느려지니 해시함수를 다시 설계해야 합니다.

 

2. unordered_set과 unordered_map의 사용법(내장함수)

데이터의 검색과 삽입 및 삭제 등을 편하게 하기 위한 내장함수들이 존재합니다.

unordered_set과 unordered_map은 가지고 있는 내장함수가 동일합니다.

기본적으로 unordered_set과 unordered_map을 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

 

#include <unordered_set>
#include <unordered_map>
#include <string>

#define MAX 50000

using namespace std;

unordered_set<string> s;
unordered_map<string> m;

s.reserve(MAX); // 삽입될 데이터의 총량을 알고 있다면, 미리 공간을 확보해
m.reserve(MAX); // 사이즈를 늘릴때마다 재배치하는 시간을 줄일 수 있다.

 

 

 

1) 데이터의 삽입

데이터를 삽입하면 내부에서 해쉬함수를 돌려나온 key에 데이터를 저장합니다.

s.insert("abc");
m.insert({"def", 3});

 

2) 데이터의 삭제

해당 데이터의 key에 접근해 삭제를 합니다.

s.erase("abc");
m.erase("def");

 

 

3) 데이터의 검색

unordered_set과 unordered_map은 순서가 없기 때문에 인덱스로 접근이 불가능합니다.

검색을 할 때는 find() 내장함수를 사용하여 접근할 수 있습니다.

 

find() | 찾고자 하는 데이터의 위치를 찾습니다.

auto it = s.find(id);
if(it == s.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

auto it2 = m.find(id);
if(it2 == m.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

 

 

4) 이외에 유용한 내장함수

s.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
s.size(); // 데이터의 갯수 반환
s.clear(); // 초기화 | 결과 {}

 

 

5) 응용

typedef struct st{ // value에 넣어줄 정보
    int grade;
    int gender;
    int score;
}DATA;

unordered_map<int, DATA> db; // 선언

db.clear(); // 초기화
db.reserve(ADD_MAX); // ADD_MAX 만큼 공간을 늘려줌

db.insert({mId, {mGrade, gender, mScore}}); // 삽입

auto it = db.find(mId); // mId라는 key를 가지고 있는지 검색
if(it == db.end()) // 찾지 못했을 때 처리

// 찾았을 때 value에 넣어둔 정보 가져와 사용하기
int grade = it->second.grade;
int gender = it->second.gender;
int score = it->second.score;

db.erase(mId); // 삭제