해시 (Hash)
해시는 주어진 데이터를 고정 길이의 불규칙한 숫자로 변환하는 함수를 가리킨다.
불규칙한 숫자는 데이터를 요약한 것으로, 다양한 상황에 사용된다.
•
번호로 주어진 index가 아닌 문자열 같은 다른 것으로 접근할 수 있는 자료구조
해시 테이블 (Hash Table)
•
저장 공간
해시 버킷 (Hash Bucket)
•
해시 테이블 안의 각 칸
해시 (Hash)
•
key들이 해시 테이블의 어디 위치에 있을지 정해서 값들을 저장하는 구조
해시 함수 (Hash Function)
•
key들이 몇번째 칸에 들어가야 하는지 결정하는 것
◦
가급적 서로 다른 칸에 들어갈 수 있도록 함
C++ STL에서 Hash Table
언어 자체에 key:value 쌍을 나타낼 수 있는 데이터 타입이 존재하지 않음
그렇지만, 많은 사람들이 필요로 할 것 같은 자료구조는 STL로 제공!
→ map, unordered_map 이 존재
std::map
•
O(logN)
•
binary search tree
std::unordered_map
•
O(1)
•
hash table
예제 1) 프로그래머스 - 베스트 앨범
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
map<string, int> music;
map<string, map<int, int>> musiclist;
for (int i = 0; i < genres.size(); i++) {
music[genres[i]] += plays[i];
musiclist[genres[i][i] = plays[i];
}
while (music.size() > 0) {
string genre{};
int max{0};
for (auto mu : music) {
if (max < mu.second) {
max = mu.second;
genre = mu.first;
}
}
// 장르별 value값이 가장 큰 장르와, value
for (int i = 0; i < 2; i++) {
int value = 0, index = -1;
for (auto ml: musiclist[genre]) {
if (value < ml.second) {
value = ml.second;
index = ml.first;
}
}
if (index == -1) break;
answer.push_back(index);
musiclist[genre].erase(index);
}
music.erase(genre);
}
return answer;
// for (auto i : musiclist) {
// cout << i.first << '\n';
// for (auto j : i.second) {
// cout << j.first << ", " << j.second << '\n';
// }
// }
}
C++
복사