[Coding Test] Coding Tips 7 : hash
삼성B형을 위한 코딩 팁 시리즈
Python 개발자의 PRO 취득을 위한 C++ 공부 여정
- [Coding Test] Coding Tips 1 : ABS(x) macro used in DFS
- [Coding Test] Coding Tips 2 : Priority Queue, Bit Operator
- [Coding Test] Coding Tips 3 : Iterator
- [Coding Test] Coding Tips 4 : algorithm library
- [Coding Test] Coding Tips 5 : 잡-Skill
- [Coding Test] Coding Tips 6 : vector, deque, list
- [Coding Test] Coding Tips 7 : hash
Hash
해시 알고리즘은 인덱스(Index, 색인)를 사용하는 검색 알고리즘으로 검색 성능이 O(1) 이기 때문에 데이터의 양과 관계없이 빠른 성능이 장점.
unordered_map(Hash)
템플릿 구성
template
< class Key, // unordered_map::key_type
class T, // unordered_map::mapped_type
class Hash = hash<Key>, // unordered_map::hasher
class Pred = equal_to<Key>, // unordered_map::key_equal
class Alloc = allocator<pair<const Key, T>> // unordered_map::allocator_type
> class unordered_map;
Custom Hash
기존에 작성된 자료형이 아닌 개별 자료구조는 아래와 같은 방법으로 활용할 수 있다.
/***************************************************************************
default : unordered_map<Data, value, hash<Data>, equal_to<Data>> hMap;
****************************************************************************/
struct Data {
int x, y;
bool operator==(const Data& r) const {
return x == r.x && y == r.y;
}
};
struct MyHash {
// size_t : unsigned long long
// * N : N 진법
size_t operator()(const Data& key) const {
return (size_t)key.x * N + key.y;
}
};
unordered_map<Data, int, MyHash> hMap;
좌표해시
특정 좌표의 id 값, 특정 좌표의 이름(문자열) 등을 관리할 때 다음과 같은 방법으로 활용 가능하다.
좌표 값이 배열의 범위를 넘어가는 경우 편리하게 사용할 수 있다.
unordered_map<int, unordered_map<int, string>> hMap;
int r = 1000000;
int c = 1257569;
hMap[r][c] = string("hello");
중복 데이터 처리
일반적으로 Key + 여러 데이터 는 unordered_multimap 을 사용해야 한다.
하지만 unordered_map 에서 사용할 수 있는 [ ] 연산자를 사용할 수 없으며, data 탐색을 위해 range 검색을 수행해야 하는 번거로움이 있다.
따라서 저장하려는 값을 vector<> 에 감싸 넣는 방법을 활용한다.
// unordered_map<string, int> → unordered_map<string, vector<int>>
만약 중복된 Key 에 중복 없이, 정렬된 상태로 저장하고 싶다면 vector 대신 set 을 사용한다.
직접 구현
아래는 Hash 를 직접 구현해 사용하는 방법이다. unordered_map<string, int> 로 동일한 기능을 더 편리하게 사용할 수 있지만, 성능으로는 직접 구현해 사용하는 방법이 압도적인 성능차를 보이는 경우가 많다는 것을 알아두자.
#define TableSize 50000
#define MaxKeySize 11
struct Node {
int data;
char key[MaxKeySize];
Node* child;
Node* parent;
};
void mstrcpy(char* dest, const char* src) {
int idx = 0;
while ((dest[idx] = src[idx]) != '\0') ++idx;
}
int mstrcmp(char* str1, char* str2) {
int idx = 0;
while (str1[idx] != '\0' && str1[idx] == str2[idx]) ++idx;
return str1[idx] == str2[idx] ? true : false;
}
struct Hash {
int hashNum;
Node node[100'005];
Node* hashTable[TableSize];
void init() {
hashNum = 0;
for (int i = 0; i < 100'005; i++) {
node[i].child = nullptr;
node[i].parent = nullptr;
}
for (int i = 0; i < TableSize; i++)
hashTable[i] = nullptr;
}
unsigned long getHash(char* str) {
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = (hash << 5) + hash + c;
return hash % TableSize;
}
void add(char* key, int data) {
Node* n = &node[hashNum++];
unsigned long hKey = getHash(key);
// Key, Value 삽입
mstrcpy(n->key, key);
n->data = data;
// 충돌 조치
Node* prev = hashTable[hKey];
n->child = prev;
if(prev != nullptr)
prev->parent = n;
hashTable[hKey] = n;
}
int get(char* key) {
unsigned long hKey = getHash(key);
for (Node* n = hashTable[hKey]; n != nullptr; n = n->child) {
// Key 값 일치하면 반환
if (mstrcmp(n->key, key)) return n->data;
}
return -1;
}
int remove(char* key) {
unsigned long hKey = getHash(key);
int data = -1;
for (Node* n = hashTable[hKey]; n != nullptr; n = n->child) {
// Key 값 일치하지 않으면 Pass
if (!mstrcmp(n->key, key)) continue;
// 삭제하는 데이터
data = n->data;
if (n->parent == nullptr) {
// 삭제하는 데이터의 parent 노드가 존재하지 않는 경우
hashTable[hKey] = n->child;
if (n->child != nullptr) n->child->parent = nullptr;
break;
}
else {
// 삭제하는 데이터의 parent 노드가 존재하는 경우
n->parent->child = n->child;
if (n->child != nullptr) {
n->child->parent = n->parent;
}
break;
}
}
return data;
}
};
Hash cHash;
Leave a comment