해시란?
해시는 key 값을 기반으로 데이터를 저장하는 자료구조로, key와 value가 한 쌍으로 존재한다. key는 value를 찾기 위한 인덱스로 사용되며, 삽입(insert), 삭제(erase), 탐색(find)과 같은 모든 연산이 평균적으로 O(1)의 시간 복잡도를 가진다.
해시의 개념을 쉽게 이해할 수 있는 간단한 예제를 보자.
다음과 같이 번호와 사람 이름이 주어진다
번호 : 153 283 119 -> 이름 : Park
번호 : 237 118 712 -> 이름 : Lee
번호 : 927 221 481 -> 이름 : Kim
이후 번호가 섞이면서 해당 사람의 이름을 매칭해야 한다.
1분 정도 암기 시간이 주어지고 번호에 맞는 이름을 매칭해 보자
번호 : 237 118 712 -> 이름 : ?
번호 : 153 283 119 -> 이름 : ?
번호 : 927 221 481 -> 이름 : ?
정답을 맞추기 위해 모든 번호를 다 외우지 않고 아마도 앞자리나 뒷자리 일부만 외우고 이름과 함께 기억했을 가능성이 높다. 이게 바로 해시의 동작 방식이다.
예를 들어 뒷자리 119, 712, 481을 각각 Park, Lee, Kim에 대칭하여 기억하여 매칭을 했을 것이다. 그렇다면 중복일 경우에는 어떻게 처리하는지도 의문이 든다.
번호 : 622 827 119 -> 이름 : Choi
이렇게 추가로 데이터가 들어온다면 119만 비교할 경우 이게 Park인지 Choi인지 알 방법이 없다.
이렇게 중복된 데이터를 처리하기 위해 해시에는 Chaining 방식과 Open Addressing 방식이 존재한다.
Chaining
Chaining 방식은 각 인덱스에 연결 리스트(linked list)를 두는 방식이다. 충돌이 발생했을 때 해당 인덱스에 여러 데이터를 연결해 저장할 수 있다.
이 방법은 실제로 해시에서 사용하는 방법이며 아래는 진행 방법을 그림으로 나타내었다.
- Insert(622 827 119,Choi)
- Erase(153 283 119)
Chaining은 삽입, 삭제, 탐색이 비교적 직관적으로 이루어진다는 장점이 있다. 하지만 중복이 많아질수록 연결 리스트의 길이가 길어지고, 결국 순차 탐색이 필요해져 최악의 경우 시간 복잡도가 O(N)이 될 수 있다. Open Addressing도 이와 비슷한 단점을 가지고 있다.
Open Addressing
해당 방식은 각 인덱스에 연결리스트를 두는 방식이 아닌 각 인덱스에 Key, Value 값을 바로 쓴다. 그러나 중복(충돌)을 어떻게 처리하냐면 Probing(간격)을 설정하여 채우려는 값이 존재한다면 Probing만큼 옆으로 이동하면서 찾아가는 방법이다.
- Insert(182 793 111, Kim / 634 421 112, Choi / 921 823 111, Bae)
- Find(921 823 111)
- Erase(634 421 112)
Open Addressing을 말로 조금 더 설명하자면 먼저 Insert 부분은 "Kim"을 해시한 위치 111이 이미 차있다면, Probing 규칙에 따라 다음 위치(112)를 확인해 비어 있으면 그곳에 삽입한다. 같은 방식으로 "Choi"는 112가 차있어 113에, "Bae"는 연속적으로 확인하며 114에 삽입된다.
Find의 경우 111을 먼저 탐색하나 차있으므로 112, 113 Probing만큼 이동하며 값을 찾는다.
마지막 Erase이다. 112부터 탐색을 진행하나 이미 있으니 위 설명처럼 Probing만큼 옆으로 이동한다. 그러고 나서 값을 발견했으니 DUMMY값을 넣어준다. 그렇지 않다면 만약 Bae를 찾는 경우 113을 비워둘 시 114로 탐색을 이어가지 못하고 Bae(921 823 111)데이터는 111부터 탐색하고 113이 비어 있으니 데이터가 없다고 생각할 것이기 때문이다.
이러한 방법이 바로 Open Addressing 방법이다.
코드
Chaining
#include <bits/stdc++.h>
using namespace std;
const int M = 1000003;
const int a = 1000;
const int MX = 500005;
int head[M];
int pre[MX];
int nxt[MX];
string key[MX];
int val[MX];
int unused = 0;
int my_hash(string& s)
{
int h =0;
for(auto x : s)
h = (h*a+x)%M;
return h;
}
int find(string k)
{
int h = my_hash(k);
int idx = head[h];
if(idx != -1)
{
if(key[idx] == k) return idx;
idx = nxt[idx];
}
return -1;
}
void insert(string k, int v)
{
int idx = find(k);
if(idx != -1)
{
val[idx] = v;
return;
}
int h = my_hash(k);
key[unused] = k;
val[unused] = v;
if(head[h] != -1)
{
nxt[unused] = head[h];
pre[head[h]] = unused;
}
head[h] = unused;
unused++;
}
void erase(string k)
{
int idx = find(k);
if(idx == -1) return;
if(pre[idx] != -1) nxt[pre[idx]] = nxt[idx];
if(nxt[idx] != -1) pre[nxt[idx]] = pre[idx];
int h = my_hash(k);
if(head[h] == idx) head[h] = nxt[idx];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fill(head, head+M, -1);
fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);
return 0;
}Open Addressing
#include <bits/stdc++.h>
using namespace std;
const int M = 1000003;
const int a = 1000;
const int MX = 500005;
const int EMPTY = -1;
const int OCCUPY = 0;
const int DUMMY = 1;
int status[M];
string key[MX];
int val[MX];
int my_hash(string& s)
{
int h =0;
for(auto x : s)
h = (h*a+x)%M;
return h;
}
int find(string k)
{
int idx = my_hash(k);
while(status[idx] != EMPTY)
{
if(status[idx] == OCCUPY && key[idx] == k) return idx;
idx = (idx+1)%M;
}
return -1;
}
void insert(string k, int v)
{
int idx = find(k);
if(idx != -1)
{
val[idx] = v;
return;
}
idx = my_hash(k);
while(status[idx] == OCCUPY)
idx = (idx+1) % M;
key[idx] = k;
val[idx] = v;
status[idx] = OCCUPY;
}
void erase(string k)
{
int idx = find(k);
if(idx != -1) status[idx] = DUMMY;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fill(status, status+M, EMPTY);
return 0;
}마무리
해시 자료구조 구현은 아직 어렵게 느껴지지만 이번 정리를 통해 이론적인 개념에 대해 익숙해졌다고 생각한다. 앞으로 다양한 문제들을 풀어보며 이해를 더욱 깊게 다질 계획이며 실제 프로젝트나 개발에서 해시를 직접 구현하게 되는 경우 이번 학습 내용을 바탕으로 코드를 집중적으로 복습하고 응용해 보려 한다.
Reference
[실전 알고리즘] 0x15강 해시 - BaaaaaaaarkingDog
