[Data Structure] Hash (해시)
Dictionary (딕셔너리)
딕셔너리는 사실 C++보다는 파이썬에서 더 익숙할 것이라 생각된다. 실제로 딕셔너리라고 아예 명확하게 말을 하기도 하니까...
자료구조에서 딕셔너리는 key와 value를 함께 저장하는 entry 저장 자료구조이다. 대신 key의 중복을 허용한다.
시간 복잡도
딕셔너리의 시간복잡도는 딕셔너리를 리스트 구현을 기준으로 얘기를 해보겠다. 딕셔너리의 ADT는 우선적으로 put, find, erase정도각 대표적이다.
put 함수는 리스트에서 바로 맨 뒤나 맨 앞에 저장하는 방식을 활용한다. 당연히 이 함수는 \(O(1)\)의 시간복잡도를 갖는다. 보통 doubly-linked list나 배열로 구현을 한다.
find와 erase는 doubly linked list를 기준으로 우선 탐색을 진행해야한다. 결국 \(O(n)\)의 시간을 갖는다.
이런 점에서 보통 딕셔너리로 저장을 하는 경우에는 삽입은 자주 이루어지지만 검색과 삭제는 적은 경우의 데이터 구조에서 활용한다. 그래서 보통 로그 파일에서 자주 사용되는 방식이다.
Search Table (탐색 테이블)
탐색 테이블은 정렬된 배열로 만든 딕셔너리 자료구조로 구현한다. 정렬된 배열로 구현하는 이유가 있다. 그 이유는 조금 뒤에 얘기를 하겠다.
우선 탐색 테이블의 ADT는 일반적인 딕셔너리의 ADT와 동일한 ADT를 가진다. 대신 시간복잡도가 다르게 나타난다.
put과 erase는 \(O(n)\)의 시간이 소요된다. 배열로 구현했는데 상수시간이 아닌 이유는 맨 처음에 배열 구현에서 한 것처럼 남은 데이터들을 옆으로 옮겨주는 shift연산이 필요하기 때문이다.
find는 \(O(\log{n})\)시간이 소요된다. 이는 정렬된 배열로 구현한 이유와 동일한 맥락이다.
Binary Search (이진 탐색)
이진 탐색은 탐색 테이블에서 정렬된 배열이 활용돼야하고 find연산 시간 \(O(\log{n})\)의 시간이 소요되는 이유이다.
이진 탐색은 계속해서 중앙 값을 판단 기준으로 삼는 탐색방법이다.
- 만약에 현재 데이터 범위의 중앙 값이 자신이 찾고자 하는 값보다 크면 기준 값의 왼쪽 범위는 탐색 범위에서 제외한다.
- 찾고자하는 값이 중앙 값보다 작으면 기준 값의 오른쪽 범위는 탐색 범위에서 제외한다.
- 위의 방법을 계속해서 반복하고 결국 1개의 데이터가 남았을 때, 해당값이 탐색 값과 같으면 특정 결과를 반환해준다.
- 만약 값이 없다면 조건에 맞춰 출력해준다.
이 방식은 계속해서 중앙을 기준으로 범위를 줄여나가기 때문에 전체 크기의 절반씩 줄여나간다. 결국 전체 탐색 횟수는 \(\log_{2}{n}\)만큼을 진행한다. 그래서 탐색 시간은 \(O(\log{n})\)시간이 걸리게 되는 것이다.
Hash Table (해시 테이블)
해시 테이블은 딕셔너리의 형태로 구현을 진행한다. 딕셔너리는 중복을 처리하는 것이 가능하다고 했는데, 중복이 발생하는 것을 충돌(collisions)이라고 한다. 이렇게 충돌이 발생했을 때, 처리 방법은 separate chaining방법을 활용한다. 그리고 딕셔너리 형태는 리스트 기반의 딕셔너리로 진핸한다.
시간복잡도
해시 테이블의 시간복잡도는 worst case로 나타내면 list based dictionary이므로 \(O(n)\)시간이다. 하지만 해시 테이블의 특성때문에 구현자가 어떤 방식으로 해시 테이블을 구현하느냐에따라 모든 함수의 기대 시간복잡도 (expected time)은 \(O(1)\)시간이 소요된다. 왜 시간복잡도를 다른 것들과 다르게 기대할 수 있는 시간복잡도를 말하는 지는 앞으로 나오는 해시 함수와 관련이 깊다.
Hash function (해시 함수)
해시에는 값이 저장되는 위치를 기록해줄때 해시 함수를 활용한다. 정확히 말하면 해시 함수의 역할은 key 정보를 활용해서 [0, N-1]의 범위 안에 해당 value를 매핑시켜주는 역할을 한다.
그래서 해시함수는 \(h(x) = x\mod N\)로 활용한다. 이때 N은 꽤 큰 소수로 설정을 해야 데이터의 충돌을 줄일 수 있다. 해시 함수에 값을 넣고 나온 결과를 hash value라고 한다.
근데 왜 해시 함수와 기대하는 시간복잡도가 \(O(1)\)인 것과 관련이 깊은 것일까?
해시 함수를 설정할 때 조건 중 가장 중요한 관점은 entry들을 가능한 골고루 흩어지게 하는 것이 좋다는 것이다. 그래서 해시 함수를 2개로 활용하는 경우도 있다.
일단 1개의 해시 함수로 설명을 해보면 충분히 큰 소수로 나누게 될 경우 소수의 특성상 1과 자신을 제외하고는 들어오는 모든 숫자는 나머지로 그대로 빠져나가게 된다.
\[
\text{if n < N and N is enoughly big prime number }\
n \mod N = n
\]
즉 N이 충분하게 큰 소수인 경우에는 자신의 key값이 결국 해시 값이 되게 되고 숫자가 클수록 N-1의 범위가 넓어지게 되어 데이터가 1개가 들어가는 범위가 넓어진다. 정말 최악의 경우가 진짜 우연하게 들어온 모든 데이터의 나머지가 다 동일한 경우이다.
이는 확률적으로 보면 굉장히 작은데, 나머지의 범위는 0~N-1까지 N개이다. 즉 하나의 값에 적용될 확률은 \(1/N\)이다. 사실상 N이 충분히 크다면 2개가 연속할 확률도 굉장히 작아지게 된다. 결국 데이터 중복이 적어지게 되므로 모든 데이터가 분산되어진다. 그래서 기대하는 탐색시간은 \(O(1)\)이다.
충돌 처리 (Collision handling)
Separate Chaining
앞에서 충돌 처리 방식을 Separate Chaining이라고 했다. 정확하게 설명하면 배열로 만들어진 해시 테이블의 특정 인덱스에 중복이 발생하면 링크드 리스트로 연결해 나가는 방식이다. 간단한 방식이지만 메모리가 추가적으로 요구된다는 점이 단점이다.
Open addressing
Open addressing 방식은 간단하게 말하면 충돌이 발생하면 링크드 리스트로 추가적인 연결을 진행하는 것이 아닌 같은 해시 테이블에서 다른 인덱스로 이동해서 값이 없다면 해당 위치에 값을 넣어주는 방식이다. 이러한 방식은 2가지 방식이 있다.
- Linear probing
- Double hashing
Linear Probing
Linear probing 방식은 해시 함수를 1개 활용하는 방식이다. 최초의 해시 값이 할당되는 곳에서부터 1씩 증가시켜서 해시 값을 이동해서 빈 공간을 찾아내는 방식이다. 그래서 빈 공간이 발생하면 그 공간에 데이터를 삽입한다. 그래서 Linear Probing의 가장 큰 단점이라면 특정 지점은 연속적인 데이터가 저장된 덩어리 형태를 띄게되어 데이터의 수가 늘어날수록 데이터의 충돌 횟수가 늘어나게 된다.
open addressing의 모든 방식에서 중요한 점은 데이터가 있는 공간 뿐만 아니라 있었던 공간은 비어 있으면 안된다.
이게 정확히 무슨 말이냐면, 해시에서도 당연히 제거 함수가 존재한다. 제거를 하게 되는 경우 해당 테이블의 값이 제거되거나 없는 것과 같이 표시를 해주는데, 해시의 해시 테이블은 총 3가지 상태가 존재한다.
- NO ITEM
- IS ITEM
- AVAILABLE
모든 해시 테이블은 NO ITEM에서 시작한다. 하지만 데이터가 삽입된 공간은 상태가 IS ITEM으로 변경된다. 즉 삽입을 진행할 때, IS ITEM인 공간은 넘어가게 되는 것이다. 하지만 데이터가 삭제되었다면 어떻게 할까?
위에서 데이터가 연속적으로 덩어리를 이루게 된다고 했는데, 만약 중간에 특정 값을 지워버리고 NO ITEM으로 표시해버린다면 탐색을 멈춰버리기 때문에 중간에 끊긴 부분 이후의 값을 탐색할 방법이 없다. 그래서 탐색이 중간에 멈춰버리는 일을 막기 위해 데이터를 제거한 후에는 상태를 AVAILABLE로 바꿔준다.
앞서서 간단히 말했지만 데이터가 많아질수록 덩어리가 만들어지므로 충돌 가능성이 늘어나게 된다. 이렇게 되면 \(O(1)\)을 기대할 수 있지만 가능성이 낮아질 수 있다.
Double Hashing
Double Hashing은 해시 함수를 2개 활용한다. 즉 인덱스의 이동범위를 좀 더 넓혀준다. 해시 함수를 2개 활용하면 다음과 같이 식의 구조를 형성한다.
\[
(h(x) + j \times d(k) ) \mod N
\]
여기서 \(h(x)\)는 기존에 쓰던 1차 해시함수, \(d(x)\)는 2차 해시함수이다. 2차 해시 함수는 \((q-(k\mod q))\)로 정의된다. 이때, \(q\)는 N보다 작은 소수로 설정해준다. 전체 값에서 나머지를 빼주기 때문에 2차 해시값은 1~\(q\) 값을 갖게된다. 여기서도 \(q\)가 소수가 아니라면 특정 숫자에 한해서는 인덱스를 특정 구간만 반복할 위험이 있다.
이렇게 데이터의 덩어리 형성을 막아준다면 우리가 기대했던 것처럼 \(O(1)\)의 시간복잡도를 가질 수 있다.
Hash implementation (해시 구현)
#include <iostream>
using namespace std;
#define MAX 353333
#define NOITEM 0
#define ISITEM 1
#define AVAILABLE 2
class cell {
private:
int key;
int value;
int flag;
public:
cell() {
key = -1;
value = -1;
flag = NOITEM;
}
~cell() {}
}
cell Hashtable[MAX];
int sz = 0;
int hashfunc1(int key) {
return key % MAX:
}
int hashfunc2(int key) {
return (17 - (key % 17));
}
void LinearInsert(int key);
void LinearSearch(int key);
void LinearDelete(int key);
void DoubleInsert(int key);
void DoubleSearch(int key);
void tableClear() {
for (int i = 0; i < MAX; i++) {
if (HashArr[i].flag) {
HashArr[i].key = -1;
HashArr[i].flag = NOITEM;
HashArr[i].value = -1;
sz--;
}
if (sz == 0) break;
}
}따로 클래스로 해시를 구현할 필요는 없다. 전체적으로 데이터를 저장할 클래스정도만 만들고 나머지는 일반적인 함수로 구현해준다.
1차 해시함수와 2차 해시함수를 위와 같이 설정해줬다.
Linear Insert function
void LinearInsert(int key) {
int probing = 1;
while (Hashtable[hashfunc1(key + probing - 1)].flag) {
probing++;
}
Hashtable[hashfunc1(key + probing - 1)].key = key;
Hashtable[hashfunc1(key + probing - 1)].flag = ISITEM;
sz++;
}Linear Probing방식에서 설명한대로 구현을 진행했다. 현재 해시테이블의 상태가 NO ITEM인 경우만 확인하면 되므로 0으로 설정된 NOITEM은 조건에서 false로 인식해서 반복문을 돌려준다. 만약 값이 있다면 probing이라는 탐색횟수를 올려준다.
값을 찾으면 찾았다는 표시를 해주고 데이터를 넣어준다. 그리고 전체 해시의 개수도 늘려준다.
Linear Search function
void LinearSearch(int key) {
int probing = 1;
while (Hashtable[hashfunc1(key + probing - 1)].flag) {
if (Hashtable[hashfunc1(key + probing -1)].key == key) {
cout << 1 << " " << probing << "\n";
return;
}
probing++;
}
cout << 0 << " " << probing << "\n";
}탐색도 전체적인 흐름은 동일하다 플래그를 확인하고 값이 있는 경우에는 해당 값이 찾는 값과 동일한 지 확인하면된다.
Linear Delete function
void LinearDelete(int key) {
int probing = 1;
while (Hashtable[hashfunc1(key + probing - 1)].flag) {
if (Hashtable[hashfunc1(key + probing -1)].key == key) {
Hashtable[hashfunc1(key + probing -1)].flag = AVAILABLE;
Hashtable[hashfunc1(key + probing -1)].key = -1;
cout << 1 << " " << probing << "\n";
sz--;
return;
}
probing++;
}
sz--;
cout << 0 << " " << probing << "\n";
}삭제는 탐색에서 플래그 상태와 벨류만 상황에 맞게 설정해주면 된다.
Double Insert function
void DoubleInsert(int key) {
int probing = 1;
while (Hashtable[hashfunc1(key) + (probing - 1) * hashfunc2(key)].flag) {
probing++;
}
Hashtable[hashfunc1(key) + (probing - 1) * hashfunc2(key)].flag = ISITEM;
Hashtable[hashfunc1(key) + (probing - 1) * hashfunc2(key)].key = key;
sz++;
}사실 이전에 있는 linear에서 해시 함수만 건드려준 것이다. Double search도 동일하게 진행해주면 된다.
'Computer Science > 자료구조' 카테고리의 다른 글
| [Data Structure] Graph (그래프) (0) | 2021.06.24 |
|---|---|
| [Data Structure] Binary Search Tree (이진 탐색 트리) (0) | 2021.06.24 |
| [Data Structure] Priority Queue (우선순위 큐) (0) | 2021.06.24 |
| [Data Structure] Binary Tree (이진트리) & Tree 구현 (0) | 2021.06.24 |
| [Data Structure] Tree (트리) (0) | 2021.06.24 |