해시 테이블(Hash Table)은 키-값(key-value) 쌍을 저장하는 데 사용되는 대표적인 자료구조입니다. 해시 함수(Hash Function)는 삽입하거나 검색할 요소가 위치할 배열의 인덱스를 계산하는 역할을 담당합니다.
이 글에서는 리스트 헤드(List Head)를 이용한 체이닝 방식으로 해시 테이블을 구현하는 C++ 프로그램을 소개합니다. 충돌(Collision)이 발생했을 때 연결 리스트를 통해 여러 요소를 관리하는 방식으로, 실무에서도 널리 사용되는 기법입니다.
알고리즘 개요
1. 삽입(Insert)
Begin
Declare function Insert(int k, int v)
int hash_v = HashFunc(k)
if (ht[hash_v] == NULL)
ht[hash_v] = new ListHead(k, v)
else
ListHead *en = ht[hash_v]
while (en->n != NULL)
en = en->n
if (en->k == k)
en->v = v
else
en->n= new ListHead(k, v)
End.삽입 연산은 먼저 해시 함수로 인덱스를 계산한 뒤, 해당 버킷이 비어 있으면 새로운 노드를 생성하고, 이미 데이터가 있다면 연결 리스트 끝까지 이동하여 같은 키가 존재하면 값을 갱신하고, 없으면 새 노드를 추가합니다.
2. 키 검색(SearchKey)
Begin
Decla Function SearchKey(int k)
int hash_v = HashFunc(k)
if (ht[hash_v] == NULL)
return -1
else
ListHead *en = ht[hash_v]
while (en != NULL and en->k != k)
en= en->n
if (en== NULL)
return -1
else
return en->v
End검색 연산은 해당 인덱스의 연결 리스트를 순회하며 일치하는 키를 찾습니다. 키가 존재하면 그에 대응하는 값을 반환하고, 찾지 못하면 -1을 반환합니다.
3. 삭제(Remove)
Begin
Declare Function Remove(int k)
int hash_v = HashFunc(k)
if (ht[hash_v] != NULL)
ListHead *en = ht[hash_v];
ListHead *p= NULL;
while (en->n != NULL and en->k != k)
p = en
en = en->n
if (en->k== k)
if (p == NULL)
ListHead *n= en->n
delete en;
ht[hash_v] = n
else
ListHead *n= en->n
delete en
p->n = n
End.삭제 연산은 삭제할 노드와 이전 노드를 추적한 뒤, 메모리를 해제하고 앞뒤 노드를 연결합니다. 삭제 대상이 리스트의 헤드인 경우에는 다음 노드가 새로운 헤드가 되도록 처리합니다.
전체 예제 코드
#include <iostream>
using namespace std;
const int T_S = 20;
class ListHead {
public:
int k, v;
ListHead *n;
ListHead(int k, int v) {
this->k = k;
this->v = v;
this->n = NULL;
}
};
class HashMapTable {
private:
ListHead **ht;
public:
HashMapTable() {
ht = new ListHead*[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_v = HashFunc(k);
if (ht[hash_v] == NULL)
ht[hash_v] = new ListHead(k, v);
else {
ListHead *en = ht[hash_v];
while (en->n != NULL)
en = en->n;
if (en->k == k)
en->v = v;
else
en->n= new ListHead(k, v);
}
}
int SearchKey(int k) {
int hash_v = HashFunc(k);
if (ht[hash_v] == NULL)
return -1;
else {
ListHead *en = ht[hash_v];
while (en != NULL && en->k != k)
en= en->n;
if (en == NULL)
return -1;
else
return en->v;
}
}
void Remove(int k) {
int hash_v = HashFunc(k);
if (ht[hash_v] != NULL) {
ListHead *en = ht[hash_v];
ListHead *p = NULL;
while (en->n != NULL && en->k != k) {
p = en;
en = en->n;
}
if (en->k == k) {
if (p == NULL) {
ListHead *n= en->n;
delete en;
ht[hash_v] = n;
}
else {
ListHead *n = en->n;
delete en;
p->n = n;
}
}
}
}
~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;
else {
cout<<"Elements at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
if (hash.SearchKey(k) == -1)
cout<<"Key "<<k<<" is empty"<<endl;
else {
hash.Remove(k);
cout<<"Entry Removed"<<endl;
}
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: 1 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: 10 Enter key at which element to be inserted: 1 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: 12 Enter key at which element to be inserted: 4 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 30 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: 30 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: 2 Enter key of the element to be searched: 6 Elements 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: 1 Entry Removed 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 Elements 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: 4
위 실행 결과에서 볼 수 있듯이, 프로그램은 메뉴 기반으로 동작하며 삽입·검색·삭제 기능을 모두 정상적으로 수행합니다. 잘못된 메뉴 번호를 입력하면 적절한 안내 메시지를 출력하고 다시 선택을 받는 구조입니다.