C++로 선형 탐사(Linear Probing) 기반 오픈 어드레싱 해시 테이블 직접 구현하기

해시 테이블(Hash Table)은 키-값(Key-Value) 쌍을 저장하는 자료구조입니다. 해시 테이블은 해시 함수(Hash Function)를 사용하여 배열 내 인덱스를 계산하고, 해당 위치에 요소를 삽입하거나 검색하게 됩니다.

선형 탐사(Linear Probing)는 오픈 어드레싱(Open Addressing) 방식의 해시 테이블에서 충돌(Collision)을 해결하는 기법입니다. 이 방식에서는 해시 테이블의 각 셀이 하나의 키-값 쌍만 저장합니다. 새로운 키를 매핑할 때 해당 셀이 이미 다른 키로 점유되어 있다면 충돌이 발생하는데, 이때 테이블을 순차적으로 탐색하여 가장 가까운 빈 공간을 찾아 새로운 키를 그곳에 삽입합니다.

이 글에서는 C++를 사용하여 선형 탐사 방식의 해시 테이블을 구현하는 방법을 알아보겠습니다.

알고리즘

먼저 요소를 삽입(Insert)하는 알고리즘입니다.

Begin
    Insert(int k, int v) 함수 선언
        정수 포인터 hash_val, init, delindex 선언
            hash_val = HashFunc(k) 로 초기화
            init = -1 로 초기화
            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)
End.

다음은 특정 키 값을 검색(Search)하는 알고리즘입니다.

Begin
    SearchKey(int k) 함수 선언
        정수형 hash_val, init 선언
            hash_val = HashFunc(k) 로 초기화
            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
End.

마지막으로 요소를 삭제(Remove)하는 알고리즘입니다.

Begin
    Remove(int k) 함수 선언
        정수형 hash_val, init 선언
            hash_val = HashFunc(k) 로 초기화
            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()
End.

예제 코드

아래는 위 알고리즘을 실제 C++ 코드로 구현한 전체 예제입니다. 삭제된 노드를 표시하기 위해 싱글톤 패턴으로 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