해시 테이블(Hash Table)은 키-값(key-value) 쌍을 저장하기 위해 사용되는 대표적인 자료구조입니다. 해시 테이블은 해시 함수(Hash Function)를 이용해 배열 내의 인덱스를 계산하며, 해당 인덱스 위치에 요소를 삽입하거나 검색하게 됩니다.
선형 탐사(Linear Probing)란?
선형 탐사는 개방 주소법(Open Addressing) 방식의 해시 테이블에서 충돌(Collision)을 해결하는 기법입니다. 이 방식에서는 해시 테이블의 각 셀이 하나의 키-값 쌍만을 저장합니다.
새로운 키를 삽입하려고 할 때, 해시 함수가 계산한 셀이 이미 다른 키에 의해 점유되어 있다면 충돌이 발생합니다. 이때 선형 탐사는 테이블을 순차적으로 탐색하여 가장 가까운 빈 공간을 찾아 새로운 키를 그 자리에 삽입합니다.
이 글에서는 선형 탐사를 활용해 해시 테이블을 구현하는 C++ 프로그램을 소개합니다.
알고리즘
삽입(Insert)
Begin
Declare Function Insert(int k, int v)
int hash_val = HashFunc(k)
intialize init = -1
intialize delindex = -1
while (hash_val != init and
(ht[hash_val]==DelNode::getNode() or ht[hash_val]
!= NULL and ht[hash_val]->k != k))
if (init == -1)
init = hash_val
if (ht[hash_val] == DelNode::getNode())
delindex = hash_val
hash_val = HashFunc(hash_val + 1)
if (ht[hash_val] == NULL || hash_val == init)
if(delindex != -1)
ht[delindex] = new HashTable(k, v)
else
ht[hash_val] = new HashTable(k, v)
if(init != hash_val)
if (ht[hash_val] != DelNode::getNode())
if (ht[hash_val] != NULL)
if (ht[hash_val]->k== k)
ht[hash_val]->v = v
else
ht[hash_val] = new HashTable(k, v)
End.키 검색(Search a key)
Begin
Declare Function SearchKey(int k)
int hash_val = HashFunc(k)
int init = -1
while (hash_val != init and (ht[hash_val]
== DelNode::getNode() or ht[hash_val]
!= NULL and ht[hash_val]->k!= k))
if (init == -1)
init = hash_val
hash_val = HashFunc(hash_val + 1)
if (ht[hash_val] == NULL or hash_val == init)
return -1
else
return ht[hash_val]->v
End.삭제(Delete)
Begin
Declare Function Remove(int k)
int hash_val = HashFunc(k)
intialize init = -1
while (hash_val != init and (ht[hash_val]
== DelNode::getNode() or ht[hash_val]
!= NULL and ht[hash_val]->k!= k))
if (init == -1)
init = hash_val
hash_val = HashFunc(hash_val + 1)
if (hash_val != init && ht[hash_val] != NULL)
delete ht[hash_val]
ht[hash_val] = DelNode::getNode()
End예제 코드
아래 코드는 메뉴 기반으로 동작하며, 요소 삽입·검색·삭제 기능을 제공합니다. 삭제된 자리는 특수 노드(DelNode)로 표시하여, 이후 탐색 시 삭제 마커를 건너뛰고 계속 진행할 수 있도록 처리했습니다.
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int T_S = 5;
class HashTable {
public:
int k;
int v;
HashTable(int k, int v) {
this->k = k;
this->v = v;
}
};
class DelNode:public HashTable {
private:
static DelNode *en;
DelNode():HashTable(-1, -1) {}
public:
static DelNode *getNode() {
if (en == NULL)
en = new DelNode();
return en;
}
};
DelNode *DelNode::en = NULL;
class HashMapTable {
private:
HashTable **ht;
public:
HashMapTable() {
ht = new HashTable* [T_S];
for (int i = 0; i < T_S; i++) {
ht[i] = NULL;
}
}
int HashFunc(int k) {
return k % T_S;
}
void Insert(int k, int v) {
int hash_val = HashFunc(k);
int init = -1;
int delindex = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k != k)) {
if (init == -1)
init = hash_val;
if (ht[hash_val] == DelNode::getNode())
delindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (ht[hash_val] == NULL || hash_val == init) {
if(delindex != -1)
ht[delindex] = new HashTable(k, v);
else
ht[hash_val] = new HashTable(k, v);
}
if(init != hash_val) {
if (ht[hash_val] != DelNode::getNode()) {
if (ht[hash_val] != NULL) {
if (ht[hash_val]->k== k)
ht[hash_val]->v = v;
}
} else
ht[hash_val] = new HashTable(k, v);
}
}
int SearchKey(int k) {
int hash_val = HashFunc(k);
int init = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k!= k)) {
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (ht[hash_val] == NULL || hash_val == init)
return -1;
else
return ht[hash_val]->v;
}
void Remove(int k) {
int hash_val = HashFunc(k);
int init = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k!= k)) {
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && ht[hash_val] != NULL) {
delete ht[hash_val];
ht[hash_val] = DelNode::getNode();
}
}
~HashMapTable() {
delete[] ht;
}
};
int main() {
HashMapTable hash;
int k, v;
int c;
while(1) {
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter element to be inserted: ";
cin>>v;
cout<<"Enter key at which element to be inserted: ";
cin>>k;
hash.Insert(k, v);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>k;
if(hash.SearchKey(k) == -1) {
cout<<"No element found at key "<<k<<endl;
continue;
} else {
cout<<"Element at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
hash.Remove(k);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}실행 결과
1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 10 Enter key at which element to be inserted: 2 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 7 Enter key at which element to be inserted: 6 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 4 Enter key at which element to be inserted: 5 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 12 Enter key at which element to be inserted: 3 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 15 Enter correct option 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 15 Enter key at which element to be inserted: 8 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 2 Enter key of the element to be searched: 6 Element at key 6 : 7 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 3 Enter key of the element to be deleted: 2 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 2 Enter key of the element to be searched: 2 No element found at key 2 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 4
정리
위 예제에서 해시 테이블 크기는 5로 설정되어 있으며, 해시 함수는 단순히 k % T_S(모듈로 연산)를 사용합니다. 실행 결과를 보면 키 6과 8은 각각 인덱스 1과 3으로 매핑되며, 충돌 발생 시 다음 빈 슬롯을 순차적으로 찾아가는 선형 탐사의 동작 방식을 확인할 수 있습니다.
다만 선형 탐사는 데이터가 몰리는 클러스터링(Clustering) 현상이 발생하기 쉬우므로, 실무에서는 테이블 크기를 적절히 조절하거나 이중 해싱(Double Hashing) 같은 다른 충돌 해결 기법을 함께 고려하는 것이 좋습니다.