해시 테이블(Hash Table)은 키(Key)-값(Value) 쌍을 저장하는 대표적인 자료구조입니다. 해시 테이블은 해시 함수(Hash Function)를 사용하여 요소를 삽입하거나 검색할 배열의 인덱스를 계산하며, 이를 통해 평균적으로 O(1)의 매우 빠른 속도로 데이터에 접근할 수 있습니다.
이 글에서는 C++를 이용해 해시 테이블을 직접 구현하는 방법을 단계별로 살펴보겠습니다.
구현 알고리즘
시작
테이블 크기 T_S를 임의의 정수 값으로 초기화한다.
키 k와 값 v를 선언하는 구조체 hashTableEntry를 생성한다.
hashMapTable 클래스를 생성한다:
테이블을 생성하는 생성자 hashMapTable을 만든다.
key mod T_S 값을 반환하는 hashFunc() 함수를 만든다.
특정 키 위치에 요소를 삽입하는 Insert() 함수를 만든다.
특정 키 위치의 요소를 검색하는 SearchKey() 함수를 만든다.
특정 키 위치의 요소를 삭제하는 Remove() 함수를 만든다.
생성자가 만든 객체들을 소멸시키는 소멸자 hashMapTable을 호출한다.
main 함수에서 switch 문을 수행하고, 선택에 따라 입력을 받는다.
키와 값을 삽입하려면 insert()를 호출한다.
요소를 검색하려면 SearchKey()를 호출한다.
요소를 삭제하려면 Remove()를 호출한다.
끝.C++ 예제 코드
아래 코드는 선형 탐사(Linear Probing) 방식의 충돌 해결 기법을 사용합니다. 즉, 해시 함수가 계산한 인덱스에 이미 다른 요소가 저장되어 있다면, 비어 있는 슬롯을 찾을 때까지 인덱스를 하나씩 증가시키며 탐색합니다.
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int T_S = 200;
class HashTableEntry {
public:
int k;
int v;
HashTableEntry(int k, int v) {
this->k= k;
this->v = v;
}
};
class HashMapTable {
private:
HashTableEntry **t;
public:
HashMapTable() {
t = new HashTableEntry * [T_S];
for (int i = 0; i< T_S; i++) {
t[i] = NULL;
}
}
int HashFunc(int k) {
return k % T_S;
}
void Insert(int k, int v) {
int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] != NULL)
delete t[h];
t[h] = new HashTableEntry(k, v);
}
int SearchKey(int k) {
int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] == NULL)
return -1;
else
return t[h]->v;
}
void Remove(int k) {
int h = HashFunc(k);
while (t[h] != NULL) {
if (t[h]->k == k)
break;
h = HashFunc(h + 1);
}
if (t[h] == NULL) {
cout<<"No Element found at key "<<k<<endl;
return;
} else {
delete t[h];
}
cout<<"Element Deleted"<<endl;
}
~HashMapTable() {
for (int i = 0; i < T_S; i++) {
if (t[i] != NULL)
delete t[i];
delete[] t;
}
}
};
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. HashTableEntry 구조체
키(k)와 값(v)을 함께 저장하는 노드 클래스입니다. 생성자를 통해 키와 값을 초기화합니다.
2. HashFunc() – 해시 함수
k % T_S 연산으로 키를 테이블 크기(200)로 나눈 나머지를 인덱스로 사용합니다. 이렇게 하면 어떤 키든 항상 유효한 배열 범위 내의 인덱스로 변환됩니다.
3. Insert() – 삽입
해시 함수로 계산한 위치에 이미 다른 키의 데이터가 있다면(충돌 발생), 빈 슬롯을 찾거나 같은 키를 만날 때까지 다음 인덱스로 이동합니다(선형 탐사). 같은 키가 이미 존재하면 기존 값을 삭제하고 새 값으로 갱신합니다.
4. SearchKey() – 검색
키의 해시 위치부터 시작해 선형 탐사 방식으로 해당 키를 찾습니다. 찾으면 값을 반환하고, 빈 슬롯을 만나면 -1을 반환하여 요소가 존재하지 않음을 알립니다.
5. Remove() – 삭제
검색과 동일한 방식으로 키를 찾아 해당 엔트리의 메모리를 해제(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: 1 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: 2 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: 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: 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: 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: 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: 1 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
마무리
이 예제는 해시 테이블의 기본 원리인 해싱(hashing)과 선형 탐사 충돌 해결을 학습하기에 적합합니다. 실무에서는 C++ 표준 라이브러리(STL)의 std::unordered_map을 사용하는 것이 일반적이지만, 이처럼 직접 구현해 보면 해시 함수 설계, 충돌 처리, 메모리 관리 등 자료구조의 핵심 개념을 깊이 이해할 수 있습니다.