해시 테이블(Hash Table)은 키-값(key-value) 쌍을 저장하는 자료구조입니다. 해시 테이블은 해시 함수(Hash Function)를 사용하여 요소를 삽입하거나 검색할 배열의 인덱스를 계산합니다.
더블 해싱(Double Hashing)은 개방 주소법(Open Addressing) 기반 해시 테이블에서 충돌(collision)을 해결하는 대표적인 기법입니다. 충돌이 발생하면 두 번째 해시 함수를 사용해 다음 탐색 위치의 이동 간격(step size)을 결정합니다. 이 방식은 선형 조사나 이차 조사에서 발생하는 클러스터링(clusterinng) 문제를 크게 완화할 수 있다는 장점이 있습니다.
이번 글에서는 더블 해싱을 적용한 해시 테이블을 C++로 구현하는 방법을 알고리즘, 예제 코드, 실행 결과 순으로 살펴보겠습니다.
알고리즘
1. 키 검색(SearchKey)
첫 번째 해시 함수로 초기 위치를 정하고, 충돌 시 두 번째 해시 함수로 계산된 이동 간격만큼 위치를 옮기며 빈 슬롯(Emp) 또는 같은 키를 찾을 때까지 반복합니다.
Begin
Declare Function SearchKey(int k, HashTable *ht)
int hashVal = HashFunc1(k, ht->s)
int stepSize = HashFunc2(k, ht->s)
while (ht->t[hashVal].info != Emp and
ht->t[hashVal].e != k)
hashVal = hashVal + stepSize
hashVal = hashVal % ht->s
return hashVal
End2. 삽입(Insert)
SearchKey 함수로 삽입 가능한 위치를 찾은 뒤, 해당 위치에 유효한 데이터(Legi)가 없다면 새 키를 저장합니다.
Begin
Declare Function Insert(int k, HashTable *ht)
int pos = SearchKey(k, ht)
if (ht->t[pos].info != Legi)
ht->t[pos].info = Legi
ht->t[pos].e = k
End3. 테이블 출력(Display)
테이블의 모든 슬롯을 처음부터 끝까지 순회하며 각 위치와 저장된 요소를 출력합니다. 비어 있는 슬롯은 "Null"로 표시합니다.
Begin
Declare function display(HashTable *ht)
for (int i = 0; i < ht->s; i++)
int v = ht->t[i].e
if (!v)
Print "Position: "
Print the position of the pointer
Print " Element: Null"
else
Print "Position: "
Print the position of the pointer
Print " Element: "
Print the element
End.4. 재해싱(Rehash)
테이블이 가득 차면 크기를 2배로 늘린 새 테이블을 생성하고, 기존 테이블의 유효한(Legi) 모든 요소를 새 테이블에 다시 삽입한 후 이전 메모리를 해제합니다.
Begin
Declare function Rehash(HashTable *ht)
int s = ht->s
HashTableEntry *t = ht->t
ht = initiateTable(2*s)
for (int i = 0; i < s; i++)
if (t[i].info == Legi)
Insert(t[i].e, ht)
free(t)
return ht
End.예제 코드
아래는 위 알고리즘을 그대로 구현한 전체 C++ 코드입니다. 첫 번째 해시 함수는 k % s, 두 번째 해시 함수는 (k * s - 1) % s를 사용하며, 메뉴 기반으로 테이블 초기화, 삽입, 출력, 재해싱 기능을 제공합니다.
#include <iostream>
#include <cstdlib>
#define T_S 5
using namespace std;
enum EntryType {Legi, Emp};
struct HashTableEntry {
int e;
enum EntryType info;
};
struct HashTable {
int s;
HashTableEntry *t;
};
int HashFunc1(int k, int s) {
return k % s;
}
int HashFunc2(int k, int s) {
return (k * s - 1) % s;
}
HashTable *initiateTable(int s) {
HashTable *ht;
if (s < T_S) {
cout<<"Table Size is Too Small"<<endl;
return NULL;
}
ht = new HashTable;
if (ht == NULL) {
cout<<"Out of Space"<<endl;
return NULL;
}
ht->s = s;
ht->t = new HashTableEntry[ht->s];
if (ht->t == NULL) {
cout<<"Table Size is Too Small"<<endl;
return NULL;
}
for (int i = 0; i < ht->s; i++) {
ht->t[i].info = Emp;
ht->t[i].e = NULL;
}
return ht;
}
int SearchKey(int k, HashTable *ht) {
int hashVal = HashFunc1(k, ht->s);
int stepSize = HashFunc2(k, ht->s);
while (ht->t[hashVal].info != Emp &&
ht->t[hashVal].e != k) {
hashVal = hashVal + stepSize;
hashVal = hashVal % ht->s;
}
return hashVal;
}
void Insert(int k, HashTable *ht) {
int pos = SearchKey(k, ht);
if (ht->t[pos].info != Legi) {
ht->t[pos].info = Legi;
ht->t[pos].e = k;
}
}
void display(HashTable *ht) {
for (int i = 0; i < ht->s; i++) {
int v = ht->t[i].e;
if (!v)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<v<<endl;
}
}
HashTable *Rehash(HashTable *ht) {
int s = ht->s;
HashTableEntry *t = ht->t;
ht = initiateTable(2*s);
for (int i = 0; i < s; i++) {
if (t[i].info == Legi)
Insert(t[i].e, ht);
}
free(t);
return ht;
}
int main() {
int v, s, pos, i = 1;
int c;
HashTable *ht;
while(1) {
cout<<"1.Initialize size of the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Display Hash Table"<<endl;
cout<<"4.Rehash Hash Table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter size of the Hash Table: ";
cin>>s;
ht = initiateTable(s);
break;
case 2:
if (i > ht->s) {
cout<<"Table is Full, Rehash the table"<<endl;
continue;
}
cout<<"Enter element to be inserted: ";
cin>>v;
Insert(v, ht);
i++;
break;
case 3:
display(ht);
break;
case 4:
ht = Rehash(ht);
break;
case 5:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}실행 결과
아래는 프로그램의 실제 실행 화면입니다. 메뉴 출력이 반복되는 부분은 가독성을 위해 일부 생략했습니다.
- 테이블 크기를 4로 설정하면 최소 크기(T_S = 5)보다 작아 "Table Size is Too Small" 오류가 출력됩니다.
- 크기 10의 테이블에 값 1, 3, 4, 5, 6, 7, 8, 9, 10, 11을 차례로 삽입합니다.
- 테이블이 가득 찬 상태에서 추가 삽입을 시도하면 "Table is Full, Rehash the table" 메시지가 출력됩니다.
Enter your choice: 1 Enter size of the Hash Table: 4 Table Size is Too Small Enter your choice: 1 Enter size of the Hash Table: 10 ... Enter your choice: 2 Enter element to be inserted: 1 ... (값 3, 4, 5, 6, 7, 8, 9, 10, 11을 순서대로 삽입) Enter your choice: 2 Table is Full, Rehash the table Enter your choice: 3 Position: 1 Element: 10 Position: 2 Element: 1 Position: 3 Element: 11 Position: 4 Element: 3 Position: 5 Element: 4 Position: 6 Element: 5 Position: 7 Element: 6 Position: 8 Element: 7 Position: 9 Element: 8 Position: 10 Element: 9 Enter your choice: 4 Enter your choice: 3 Position: 1 Element: Null Position: 2 Element: 1 Position: 3 Element: Null Position: 4 Element: 3 Position: 5 Element: 4 Position: 6 Element: 5 Position: 7 Element: 6 Position: 8 Element: 7 Position: 9 Element: 8 Position: 10 Element: 9 Position: 11 Element: 10 Position: 12 Element: 11 Position: 13 Element: Null Position: 14 Element: Null Position: 15 Element: Null Position: 16 Element: Null Position: 17 Element: Null Position: 18 Element: Null Position: 19 Element: Null Position: 20 Element: Null Enter your choice: 2 Enter element to be inserted: 20 Enter your choice: 3 Position: 1 Element: 20 Position: 2 Element: 1 Position: 3 Element: Null Position: 4 Element: 3 Position: 5 Element: 4 Position: 6 Element: 5 Position: 7 Element: 6 Position: 8 Element: 7 Position: 9 Element: 8 Position: 10 Element: 9 Position: 11 Element: 10 Position: 12 Element: 11 Position: 13 Element: Null Position: 14 Element: Null Position: 15 Element: Null Position: 16 Element: Null Position: 17 Element: Null Position: 18 Element: Null Position: 19 Element: Null Position: 20 Element: Null Enter your choice: 5
마무리
더블 해싱은 두 개의 독립적인 해시 함수를 조합해 충돌 시 탐색 경로를 효율적으로 분산시키는 기법입니다. 위 예제처럼 테이블이 가득 찼을 때 재해싱을 수행하면 크기를 늘려 성능 저하를 방지할 수 있으며, 이러한 구조는 데이터 조회 속도가 중요한 다양한 응용 프로그램에서 유용하게 활용됩니다.