[자료구조] 체이닝 해시 테이블(Chaining Hash Table) 구현 -C/C++

해시테이블(Hash Table)이란?

Key값에 Value를 저장하는 데이터 구조로 key값을 통해 데이터에 접근하게 됩니다.
그렇기 때문에 상수시간에 접근이 가능하여, 탐색이 빠르단 장점을 갖고있습니다.

만약 10개의 데이터 순서대로 0~10의 id값을 갖는 데이터를 해시테이블에 저장한다면,
table[1] = id(1)
table[2] = id(2)
table[3] = id(3)
table[4] = id(4)
 ...
table[9] = id(9)

와 같이 순차적으로 저장이 되서 id 5인 값을 찾을 때 table[5]의 값을 주면됩니다.

코드로 간단히 구현하면 id에 따라 아래와 같이 table에 저장하면 되겠죠.

#include<iostream>
#define MAX_HASH 10
using namespace std;
 
typedef struct Node
{
    int id;
}Node;
 
Node* hashTable[MAX_HASH];
 
int main()
{
    for (int i = 0; i < MAX_HASH; i++)
    {
         Node* node= (Node*)malloc(sizeof(Node));
         node->id = i;
         hashTable[i] = node;
    }
 
    return 0;
}

문제는 저장해야할 데이터가 딱 떨어지지 않아 테이블 범위보다 넘어설 경우,
예를 들어 ~100, ~10000까지 저장해야 되는 경우입니다.

이럴 경우 key(id)값을 hash table의 최대 사이즈(MAX_HASH)로 나눠준 키값으로 테이블에 저장이 가능하나,  ->key%MAX_HASH

동일한 key값이 생겨 충돌이 발생하게 됩니다.

1, 11, 21, 31, 101.. ->  key값이 1로 동일

이 경우 Chaining 방식을 이용하여 구현하면 해결이 가능합니다.

Chaining 방식은 Linked List를 이용하는 방법으로 저장하려는 해시테이블에 이미 같은 키값의 데이터가 있다면,
노드를 추가하여 다음 노드를 가르키는 방식으로 구현하는 것입니다.

hashTable[1] :(1)->(11)->(21)->(31)->(101)
hashTable[2] :(2)->(12)->(42)->(62)
...
hashTable[9] :(9)->(19)->(99)

구현해야 하는 함수는 이렇습니다.

-데이터 추가 : key값을 구해 해시테입블에 삽입, 데이터가  이미 있는 경우 링크드리스트로  노드간 연결해준다.
-데이터 삭제 : key값에 따라 해시테이블에 접근, 연결된 노드를 탐색해 삭제하려는 데이터를 찾은 후, 연결을 끊어준다.
-데이터 찾기 : 삭제와 마찬가지로 해시테입블에 접근->리스트 순차탐색

이제 구현, 먼저 아래와 같이 기본 코드를 준비합니다

#include<iostream>
#define MAX_HASH 10
#define HASH_KEY(key) key%MAX_HASH
 
using namespace std;
 
typedef struct Node
{
    int id;
    Node* hashNext;
}Node;
 
Node* hashTable[MAX_HASH];
 
int main()
{
 
    return 0;
}

line 3 : hash table에 저장할 key값을 구한다. -> key%MAX_HASH
line 10 : 해시테이블에서 key가 중복될 경우 가르킬 다음 노드.

다음 hash를 추가할 AddHashData함수, 키로 만들 id값과 저장할 node를 파라미터로 넘겨줍니다.

void  AddHashData(int key, Node* node)
{
    int hash_key = HASH_KEY(key);
    if (hashTable[hash_key] == NULL)
    {
        hashTable[hash_key] = node;
    }
    else
    {
        node->hashNext = hashTable[hash_key];
        hashTable[hash_key] = node;
    }
}

먼저 hashTable에 저장할 key값을 구한다.(line 3)
HashTable[hash_key]에 값이 없다면 데이터가 처음 들어온 것이므로 바로  데이터 저장(line 4~6)

값이 이미 들어있다면,
현재 추가하는 노드의 hashNext는 hashTable[hash_key]을 가르키게 합니다.
이후 hashTable[hash_key]값은 새로 추가될 노드를 가르키면 자연스럽게 기존에 추가된 노드들이 연결이 됩니다.

삭제는 아래와 같이 구현합니다.

void DelHashData(int id)
{
    int hash_key = HASH_KEY(id);
    if (hashTable[hash_key] == NULL)
        return;
 
    Node* delNode = NULL;
    if (hashTable[hash_key]->id == id)
    {
        delNode = hashTable[hash_key];
        hashTable[hash_key] = hashTable[hash_key]->hashNext;
    }
    else
    {
        Node* node = hashTable[hash_key];
        Node* next = node->hashNext;
        while (next)
        {
            if (next->id == id)
            {
                node->hashNext = next->hashNext;
                delNode = next;
                break;
            }
            node = next;
            next = node->hashNext; 
        }
    }
    free(delNode); 
}

hashTable[hash_key]의 값이 바로 찾는 데이터라면,
hashTable[hash_key]데이터를 삭제할 노드로 만들고 hashTable[hash_key]는 hashNext로 설정합니다.(line 8~12)
만약아니라면, hashTable[hash_key]를 기준으로 선형탐색을 하게 됩니다.(liine 15~24)
이후 찾은 데이터를 free.

데이터를 찾는 것은 같은 로직에서 free대신 리턴을 해주면 됩니다.  연결 상태는 그대로 두고.

Node* FindHashData(int id)
{
    int hash_key = HASH_KEY(id);
    if (hashTable[hash_key] == NULL)
        return NULL;
 
    if (hashTable[hash_key]->id == id)
    {
        return hashTable[hash_key];
    }
    else
    {
        Node* node = hashTable[hash_key];
        while (node->hashNext)
        {
            if (node->hashNext->id == id)
            {
                return node->hashNext;
            }
            node = node->hashNext;
        }
    }
    return  NULL;
}

테스트를 위해 hashTable의 모든데이터를 출력하는 함수도 만듭니다.

void PrintAllHashData()
{
    cout << "###Print All Hash Data###" << endl;
    for (int i = 0; i < MAX_HASH; i++)
    {
        cout << "idx:" << i << endl;
        if (hashTable[i] != NULL)
        {
            Node* node = hashTable[i];
            while (node->hashNext)
            {
                cout << node->id << " ";
                node = node->hashNext;
            }
            cout << node->id << endl;
        }
    }
    cout << endl << endl;;
}

아래와 같이  테스트해보면 됩니다.

1000까지 랜덤한 id값을 만든 후 hashtable에 저장, 모든 데이터를 출력.
저장된 데이터를 삭제해 본 후 다시 출력.

 
int main()
{
    int saveidx[101] = { 0, };
    for (int i = 0; i < 100; i++)
    {
        Node* node = (Node*)malloc(sizeof(Node));
        node->id = rand() % 1000;
        node->hashNext = NULL;
        AddHashData(node->id, node);
        saveidx[i] = node->id;
    }
    PrintAllHashData();
 
 
    for (int i = 0; i < 50 ; i++)
    {
        DelHashData(saveidx[i]);
    }
    PrintAllHashData();
 
    for (int i = 50; i < 100; i++)
    {
        DelHashData(saveidx[i]);
    }
    PrintAllHashData();
    return 0;
 
}

아래와  같이 해시테이블에  잘  저장되는 것을 볼 수있습니다.