Hash Table(해시 테이블)

해시 테이블(Hash Table)

Key값에 Value를 저장하는 데이터 구조로 key값을 통해 데이터에 접근한다.

그렇기에 데이터 접근 시간 복잡도가 O(1)이 되어 탐색이 빠르다는 장점을 갖는다.

이때 해시 테이블의 문제가 발생할 수 있는데 충돌에 관한 문제이다.

만약 다수의 Value 중 Key값이 겹치는 Value들이 존재하면 충돌이 발생한다.

이를 해결할 수 있는 방법은 다양하다.

첫째로 Chaining 방식은 Linked List를 이용하는 방법으로 저장하려는 해시 테이블에 같은 키 값의 데이터가 존재할 경우,

노드를 추가해 다음 노드를 가리키는 방식으로 체인을 이어서 해시 테이블을 구성하는 방식이다.

둘째로 Open addressing 방식은 index에 대한 충돌 처리에 대해서 Linked List와 같이 추가적인

메모리 공간을 사용하지 않고, 해시 테이블의 배열 중 빈 공간을 사용한다.

이를 구현하는 방법은 다양한데 간단한 Linear Probing을 보겠다.

Linear Probing 방식은 index에 대해 충돌이 발생했을 경우 index의 바로 뒤 버킷 중에서 빈 버킷을 찾아

데이터를 삽입한다. 그러므로 후에 key에 맞는 index를 접근했을 때 키 값이 옳지 않으면 뒤로 한칸씩 검색을 하면서

일치하는 키 값을 찾아간다. (상황이 좋지 않으면 효율이 매우 떨어질 수 있다)

이 둘중에서 Linked List를 이용하는 Chaining 방식으로 해시 테이블을 구성하도록 하겠다. (Open Addressing은 처리할게 많음)

#include<iostream>
 
#define MAX_SIZE 10
#define HASH_KEY(key) key % MAX_SIZE
 
using namespace std;
 
typedef struct Node{
    int id;
    Node* next_Hash;
};
 
Node* hashTable[MAX_SIZE];
 
void AddHashData(int key, Node* node)
{
    int hash_key = HASH_KEY(key);
    if(hashTable[hash_key] == NULL)
    {
        hashTable[hash_key] = node;
    }
    else
    {
        node->next_Hash = hashTable[hash_key];
        hashTable[hash_key] = node;
    }
}
 
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]->next_Hash;
    } else{
        Node* node = hashTable[hash_key];
        Node* next = node->next_Hash;
        while(next)
        {
            if(next->id == id){
                node->next_Hash = next->next_Hash;
                delNode = next;
                break;
            }
            node = next;
            next = node->next_Hash;
        }
    }
    free(delNode);
}
 
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->next_Hash)
        {
            if(node->next_Hash->id == id) return node->next_Hash;
            node = node->next_Hash;
        }
    }
 
    return NULL;
}
 
void printAllHashData()
{
    cout << "Hash Data 출력\n";
    for(int i=0;i<MAX_SIZE;i++){
        cout << "index : " << i << "\n";
        if(hashTable[i] != NULL){
            Node* node = hashTable[i];
            while(node->next_Hash){
                cout << node->id << " ";
                node = node->next_Hash;
            }
            cout << node->id << "\n";
        }
    }
    cout << "\n\n\n";
}

** 참고 : http://huiyu.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%B2%B4%EC%9D%B4%EB%8B%9D-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94Chaining-Hash-Table