해시 테이블(Hash Table)은 키-값 쌍을 저장하는 데 사용되는 대표적인 자료구조입니다. 해시 함수(Hash Function)는 삽입하거나 검색할 요소가 위치할 배열의 인덱스를 계산하는 역할을 담당합니다.
2차 탐사(Quadratic Probing)는 개방 주소법(Open Addressing) 방식의 해시 테이블에서 충돌(Collision)을 해결하는 기법 중 하나입니다. 이 방식은 원래의 해시 인덱스에 임의의 2차 다항식 값을 순차적으로 더해가며 빈 슬롯을 찾을 때까지 탐색을 진행합니다.
이 글에서는 C++를 활용해 2차 탐사 기법으로 충돌을 처리하는 해시 테이블을 구현하는 방법을 살펴보겠습니다.
알고리즘
1. 키 값 검색 (SearchKey)
시작
SearchKey(int k, HashTable *ht) 함수 선언
pos = HashFunc(k, ht->s) 계산
collisions = 0으로 초기화
while (ht->t[pos].info != Emp && ht->t[pos].e != k)
pos = pos + 2 * ++collisions - 1
if (pos >= ht->s)
pos = pos - ht->s
return pos
끝2. 요소 삽입 (Insert)
시작
Insert(int k, HashTable *ht) 함수 선언
pos = SearchKey(k, ht) 호출
if (ht->t[pos].info != Legi)
ht->t[pos].info = Legi 설정
ht->t[pos].e = k 저장
끝3. 해시 테이블 출력 (Display)
시작
display(HashTable *ht) 함수 선언
for (int i = 0; i < ht->s; i++)
value = ht->t[i].e 가져오기
if (!value)
현재 위치와 "Element: Null" 출력
else
현재 위치와 해당 요소 출력
끝4. 재해싱 (Rehash)
시작
Rehash(HashTable *ht) 함수 선언
s = ht->s 저장
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
끝예제 코드
아래는 위 알고리즘을 실제로 구현한 전체 소스 코드입니다. 메뉴 기반으로 동작하며, 테이블 초기화, 요소 삽입, 출력, 재해싱 기능을 제공합니다.
#include <iostream>
#include <cstdlib>
#define T_S 10
using namespace std;
enum EntryType {
Legi, Emp, Del};
struct HashTableEntry {
int e;
enum EntryType info;
};
struct HashTable {
int s;
HashTableEntry *t;
};
bool isPrime (int n) {
if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
int nextPrime(int n) {
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
int HashFunc(int k, int s) {
return k % 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 = nextPrime(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 pos = HashFunc(k, ht->s);
int collisions = 0;
while (ht->t[pos].info != Emp && ht->t[pos].e != k) {
pos = pos + 2 * ++collisions -1;
if (pos >= ht->s)
pos = pos - ht->s;
}
return pos;
}
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;
}
}
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;
}
void display(HashTable *ht) {
for (int i = 0; i < ht->s; i++) {
int value = ht->t[i].e;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}
}
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 The 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);
cout<<"Size of Hash Table: "<<nextPrime(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;
}코드 설명
이 프로그램은 다음과 같은 핵심 구성 요소로 이루어져 있습니다.
- EntryType 열거형: 각 슬롯의 상태를 나타냅니다.
Legi(유효한 데이터),Emp(비어 있음),Del(삭제됨) 세 가지 상태를 가집니다. - isPrime / nextPrime 함수: 해시 테이블의 크기를 소수로 지정하기 위해 사용됩니다. 소수 크기의 테이블은 충돌 분포를 고르게 만들어 성능을 향상시킵니다.
- HashFunc 함수: 키를 테이블 크기로 나눈 나머지를 반환하는 간단한 나눗셈 해시 함수입니다.
- SearchKey 함수: 2차 탐사 공식인
pos + 2 × i - 1(i는 충돌 횟수)을 적용해 빈 슬롯 또는 일치하는 키를 찾습니다. - Rehash 함수: 테이블이 가득 차면 크기를 두 배로 늘린 새 테이블을 생성하고, 기존 데이터를 모두 재삽입합니다.
실행 결과
프로그램을 실행하면 아래와 같이 메뉴 기반으로 동작합니다. 테이블 크기를 10으로 초기화하면 내부적으로 다음 소수인 11로 설정되며, 요소를 삽입하고 출력할 수 있습니다.
1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 10 Size of Hash Table: 11 Enter your choice: 2 Enter element to be inserted: 1 ... (요소 11까지 순차 삽입) Enter your choice: 2 Table is Full, Rehash the table Enter your choice: 3 Position: 1 Element: 11 Position: 2 Element: 1 Position: 3 Element: 2 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 Enter your choice: 4 (재해싱 수행) Enter your choice: 3 Position: 1 Element: Null Position: 2 Element: 1 Position: 3 Element: 2 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 ~ 23 Element: Null
재해싱 후에는 테이블 크기가 23(다음 소수)으로 확장된 것을 확인할 수 있으며, 기존에 저장된 모든 요소가 새 테이블에 올바르게 재배치됩니다.
마무리
2차 탐사는 선형 탐사(Linear Probing)에서 발생하는 1차 군집화(Primary Clustering) 문제를 완화할 수 있는 효과적인 충돌 해결 기법입니다. 다만 테이블 크기가 적절하지 않으면 빈 슬롯이 있음에도 탐색에 실패하는 경우가 발생할 수 있으므로, 테이블 크기를 소수로 유지하는 것이 중요합니다. 본 예제 코드를 통해 해시 테이블의 기본 동작 원리와 재해싱 과정을 직접 확인해 보시기 바랍니다.