해시 테이블(Hash Table)은 키-값(key-value) 쌍을 저장하는 대표적인 자료구조입니다. 해시 함수(Hash Function)는 저장하거나 검색할 요소가 위치할 배열의 인덱스를 계산하는 역할을 담당합니다.
이 글에서는 단일 연결 리스트(singly linked list)를 체이닝(chaining) 방식으로 활용해 해시 테이블을 구현하는 C++ 프로그램을 단계별로 살펴보겠습니다.
해시 테이블과 체이닝 방식의 이해
서로 다른 키가 동일한 해시 값을 가지는 현상을 충돌(Collision)이라고 합니다. 체이닝 방식은 각 버킷(bucket)에 연결 리스트를 두어 충돌이 발생한 요소들을 같은 버킷에 연속적으로 연결하는 기법입니다. 이렇게 하면 하나의 인덱스에 여러 개의 데이터를 저장할 수 있어 충돌 문제를 효과적으로 해결할 수 있습니다.
알고리즘
1. 삽입(Insert)
Begin
Declare Function Insert(int k, int v)
int hash_v = HashFunc(k)
HashTableEntry* p = NULL
HashTableEntry* en = ht[hash_v]
while (en!= NULL)
p = en
en= en->n
if (en == NULL)
en = new HashTableEntry(k, v)
if (p == NULL)
ht[hash_v] = en
else
p->n= en
else
en->v = v
End.삽입 과정은 다음과 같이 진행됩니다.
- 해시 함수로 키의 해시 값을 계산합니다.
- 해당 버킷의 연결 리스트를 끝까지 순회합니다.
- 동일한 키가 없으면 새 노드를 생성해 리스트 끝에 연결하고, 이미 키가 존재하면 값(v)만 갱신합니다.
2. 삭제(Remove)
Begin
Declare Function Remove(int k)
int hash_v = HashFunc(k)
HashTableEntry* en = ht[hash_v]
HashTableEntry* p= NULL
if (en == NULL or en->k != k)
Print “No Element found at key”
return
while (en->n != NULL)
p = en
en = en->n
if (p != NULL)
p->n = en->n
delete en
Print “Element Deleted”
End.삭제 과정은 다음과 같습니다.
- 키의 해시 값에 해당하는 버킷을 확인합니다.
- 버킷이 비어 있거나 첫 번째 노드의 키가 일치하지 않으면 "요소를 찾을 수 없다"는 메시지를 출력하고 종료합니다.
- 노드를 찾으면 이전 노드(p)와 다음 노드를 연결한 뒤 해당 노드의 메모리를 해제(delete)합니다.
3. 검색(SearchKey)
Begin
Declare function SearchKey(int k)
int hash_v = HashFunc(k)
bool flag = false
HashTableEntry* en = ht[hash_v]
if (en != NULL)
while (en != NULL)
if (en->k == k)
flag = true
if (flag)
Print “Element found at key”
Print en->v
en = en->n
if (!flag)
Print “No Element found at key”
End.검색 과정은 다음과 같습니다.
- 키의 해시 값으로 버킷을 찾습니다.
- 연결 리스트를 순회하며 키가 일치하는 노드를 확인합니다.
- 일치하는 노드가 있으면 해당 값을 출력하고, 끝까지 못 찾으면 "요소를 찾을 수 없다"는 메시지를 출력합니다.
예제 코드
#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
int v, k;
HashTableEntry *n;
HashTableEntry *p;
HashTableEntry(int k, int v) {
this->k = k;
this->v = v;
this->n = NULL;
}
};
class HashMapTable {
public:
HashTableEntry **ht, **top;
HashMapTable() {
ht = new HashTableEntry*[T_S];
for (int i = 0; i < T_S; i++)
ht[i] = NULL;
}
int HashFunc(int key) {
return key % T_S;
}
void Insert(int k, int v) {
int hash_v = HashFunc(k);
HashTableEntry* p = NULL;
HashTableEntry* en = ht[hash_v];
while (en!= NULL) {
p = en;
en = en->n;
}
if (en == NULL) {
en = new HashTableEntry(k, v);
if (p == NULL) {
ht[hash_v] = en;
} else {
p->n = en;
}
} else {
en->v = v;
}
}
void Remove(int k) {
int hash_v = HashFunc(k);
HashTableEntry* en = ht[hash_v];
HashTableEntry* p = NULL;
if (en == NULL || en->k != k) {
cout<<"No Element found at key "<<k<<endl;
return;
}
while (en->n != NULL) {
p = en;
en = en->n;
}
if (p != NULL) {
p->n = en->n;
}
delete en;
cout<<"Element Deleted"<<endl;
}
void SearchKey(int k) {
int hash_v = HashFunc(k);
bool flag = false;
HashTableEntry* en = ht[hash_v];
if (en != NULL) {
while (en != NULL) {
if (en->k == k) {
flag = true;
}
if (flag) {
cout<<"Element found at key "<<k<<": ";
cout<<en->v<<endl;
}
en = en->n;
}
}
if (!flag)
cout<<"No Element found at key "<<k<<endl;
}
~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;
hash.SearchKey(k);
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;
}코드 핵심 포인트
- 테이블 크기(T_S = 200): 해시 테이블의 버킷 개수를 200개로 설정합니다.
- 해시 함수:
key % T_S나눗셈 방식으로 간단하게 인덱스를 계산합니다. - HashTableEntry 구조체: 키(k), 값(v), 다음 노드 포인터(n)를 멤버로 가집니다.
- 소멸자: 프로그램 종료 시
delete[]로 할당된 배열 메모리를 해제하여 메모리 누수를 방지합니다.
실행 결과
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: 2 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: 3 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: 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: 8 Enter key at which element to be inserted: 9 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 found 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: 2 Enter key of the element to be searched: 7 No Element found at key 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: 9 Element Deleted 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 4
시간 복잡도 정리
| 연산 | 평균 시간 복잡도 | 최악 시간 복잡도 |
|---|---|---|
| 삽입(Insert) | O(1) | O(n) |
| 검색(Search) | O(1) | O(n) |
| 삭제(Remove) | O(1) | O(n) |
해시 함수가 데이터를 고르게 분산시키면 평균적으로 O(1)의 성능을 기대할 수 있지만, 모든 키가 동일한 버킷으로 몰리는 최악의 경우 연결 리스트 전체를 순회해야 하므로 O(n)이 됩니다. 따라서 실무에서는 테이블 크기 조절(rehashing)과 좋은 해시 함수 선택이 중요합니다.