Hash Table 구현

Hash Table을 구현해 보자

 

Hash Table 이란 자료를 저장하기 위한 여러가지 자료구조중 하나로 복잡도가 O(n) 이다.

 

Hash Table을 대략 그림으로 표현 하면 다음과 같다.

data 및 Hash key를 만드는 함수에 따라 Hash Key 가 중복 될수 있지만 추후 다루고 현재는 중복되지 않는다는 가정에 작업한다.

 

Hash Table 에 자료를 저장할 변수는 void 형 이중 포인터로 한다.

void로 한 이유는 저장 할 데이터 구조가 어떻게 저장하냐에 따라 저정할 데이터 구조가 매번 바뀌기 때문에 범용성을 위해 void 형을 사용 했고 저장하는 데이터 역시 데이터 자체를 저장하기 보다 데이터를 나타내는 포인터를 저장하기 위해 이중 포인터를 사용했다.

 

따라서 HashTable를 사용하기 위한 함수 및 저장할 데이터 구조는 다음과 같다.

typedef struct _hashTable                                                                                                                                                                                          
{                                                                                                                                                                                                                  
    /* == hash table member == */                                                                                                                                                                                  
    void **slot_pp;                                                                                                                                                                                                
    /* == hash table work func == */                                                                                                                                                                               
    int (*insert)(struct _hashTable *ht, void *data_p);                                                                                                                                                            
    int (*remove)(struct _hashTable *ht, int key_val);                                                                                                                                                             
    void **(*get)(struct _hashTable *ht, int key_val);                                                                                                                                                             
    /* == hash table make key func == */                                                                                                                                                                           
    int (*makeKey)(struct _hashTable *ht, int val);                                                                                                                                                                
    /* == hash table member struct func == */                                                                                                                                                                      
    int (*keySrc)(void *arg_p);                                                                                                                                                                                    
    int (*delData)(void *arg_p);                                                                                                                                                                                   
                                                                                                                                                                                                                   
} HashTable;

slot_pp : 데이터를 저장할 포인터

 

 ** Hash Table에 사용되는 함수들

 

insert : 데이터를 삽입할 함수 포인터, 성공 시 사용된 Hash key를 반환. 실패시 음수를 반환한다.

remove: 데이터를 삭제할 함수 포인터, 성공 시 0을, 실패시 음수를 반환한다.

get: HashKey를 받아 해당 데이터를 반환한다. 데이터를 저장하는 멤버가 이중포인터이므로 이중포인터로 반환한다.

 

** Hash Table 내부에 사용되는 함수들

 

makeKey: Hash Key를 생성하는 함수 포인터

keySrc: Hash Key를 만들때 사용하는 Resource를 Return 해주는 함수 포인터.

이 함수는 Hash Table을 사용하고자 하는 사용자가 저장하는 데이터에 맞게 등록해줘야 한다.

delData: Hash Table에서 데이터를 삭제 후 저장했던 데이터를 삭제 할 때 사용하는 함수 포인터.

이 함수는 Hash Table을 사용하고자 하는 사용자가 저장하는 데이터에 맞게 등록해줘야 한다.

 

코드 구현

 

먼저 Hash Table을 초기화 하는 함수를 구현하자.

 

Hash Table 초기화(init)

 

HashTableInit()

HashTable *HashTableInit(int (*getSrc_func)(void *arg_p), 
        int (*delData_func)(void *arg_p))
{
    TR_FUNC(TRACE);

    HashTable *ret = (HashTable *)malloc(sizeof(HashTable));
    ret->slot_pp = (void **)malloc(sizeof(void *) * TABLE_SIZE);

    for (int index = 0; index < TABLE_SIZE; index++) {
        ret->slot_pp[index] = (void *)NULL;
    }
    /* Hash Table Work Func */
    ret->insert = HashTableInsert_Func;
    ret->remove = HashTableDel_Func;
    ret->get = HashTableGet_Func;
    ret->makeKey = HashKey_Func;
    /* member Struct Func */
    ret->keySrc = getSrc_func;
    ret->delData = delData_func;

    return ret;
}

Hash Table을 사용하기 위해선 당연히 초기화를 해야 한다.

초기화 함수 구현 할때 위에 적혀있는 것처럼 Hash Key를 계산하기 위한 자원, HashTable을 삭제 할때 데이터를 어떻게 삭제 할것인지에 대한 함수를 Arg로 받고 있다.

 

TABLE_SIZE 는 런타임이 아닌 컴파일 타임에 결정되며 현재 100으로 설정해 놓았다.

사용할 Hash Table 및 저장할 수있는 포인터를 Malloc으로 할당 한 후 hashTable 구조체의 멤버 함수 포인터들을 모두 등록한다.

 

Hash Table 데이터 삽입(Insert)

 

HashTableInsert_Func()

static int HashTableInsert_Func(HashTable *ht, void *data_p)
{
    TR_FUNC(TRACE);

    int err = 0;
    int key_src;
    int hash_key;

    if (!(ht) || !(data_p)) {
        ERR_SET_OUT(err, ENOMEM);
        return -err;
    }
    /* get resource for make hash key */
    if ((key_src = ht->keySrc(data_p)) < 0) {
        ERR_SET_OUT(err, EINVAL);
        return -err;
        /* get Hash Key */
    } else if ((hash_key = ht->makeKey(ht, key_src)) < 0) {
        ERR_SET_OUT(err, EINVAL);
        return -err;
    } else {
        if (!(ht->slot_pp)) {
            ERR_SET_OUT(err, EINVAL);
            return -err;
        } else if (!(ht->slot_pp[hash_key])) {
            /* Insert Data */
            ht->slot_pp[hash_key] = data_p;
        }
    }

    return hash_key;
}

Insert 함수는 Arg 로  Hash Table 구조체 포인터와 void 포인터(data_p)를 가지고 온다.

 

data_p는 저장하고자 하는 데이터의 포인터이다.

데이터를 삽입하기 위해서는 Hash Key 및 Hash Table 구조체의 slot_pp를 알아야 한다.

따라서 Arg를 Hash Table 구조체 포인터를 가지고 와서 Hash Key 를 생성할 수 있는 함수를 호출 할 수 있고

slot_pp의 포인터를 알 수 있다.

 

먼저 ht->keySrc를 호출하여 Hash Key를 만들고자 하는 함수를 호출하고 return 값으로 key에 사용할 데이터를 가지고 온다. (ht->keySrc는 사용자가 어떤 값을 key로 설정할지 함수로 만들어 Init에 등록했다. keySrc의 Arg를 data_p를 넘겨 줌으로써 data_p 를 활용 하여 사용하고자 하는 Hash Key의 Resource를 반환한다. )

 

가지고 온 resource를 활용하여(Arg로) ht->makeKey를 통해 Hash Key를 만들어 준다.

Hash Key는 Hash Table의 Index 이므로 해당 슬롯에 데이터를 저장한다. (ht->slot_pp[hash_key] = data_p)

 

저장 후 Hash Key를 반환 한다.

 

Hash Table 데이터 가져오기(Get)

 

HashTableGet_Func()

static void **HashTableGet_Func(HashTable *ht, int key_val)
{
    TR_FUNC(TRACE);

    int err = 0;
    void **ret = NULL;

    if (!(ht) || key_val < 0 || key_val > TABLE_SIZE) {
        ERR_SET_OUT(err, EINVAL);
        return NULL;
    }

    if (!(ret = &(ht->slot_pp[key_val])) 
                || !(ht->slot_pp[key_val])) {
        ERR_SET_OUT(err, EINVAL);
    }

    return ret;
}

데이터를 가져오는 함수는 간단히 체크후 Hash Key의 slot을 return 한다.

해당 slot이 비워져 있을 경우 Error를 print 한 후(ERR_SET_OUT) return한다.

 

Hash Table 데이터 삭제하기(remove)

 

HashTableDel_Func()

static int HashTableDel_Func(HashTable *ht, int hash_key)
{
    TR_FUNC(TRACE);

    int err = 0;

    if (!(ht) || !(ht->slot_pp[hash_key])) {
        ERR_SET_OUT(err, EINVAL);
        return err;
    }

    if ((ht->delData(ht->slot_pp[hash_key])) < 0) {
        ERR_SET_OUT(err, EINVAL);
    } else {
        ht->slot_pp[hash_key] = NULL;
    }

    return err;
}

데이터를 지우는 함수는 사용자가 등록한 데이터 Del 함수를 호출 할때 Arg로 Hash Key에 맞는 데이터를 넣어준다.

지우는데 실패하면 등록 함수에서 마이너스 값을 return 하여 Error를 Print하고 err를 return 한다.

만약 정상적으로 지워졌으면 해당 slot을 NULL 로 해줌으로써 Hash Table의 데이터를 삭제한다.

 

Hash Key 만들기(makeKey)

static int HashKey_Func(HashTable *ht, int val)
{
    TR_FUNC(TRACE);

    return val % 100;
}

Hash Key 만드는 방법은 간단히 arg 에서 나누기 100 하여 나머지 를 반환하게 하였다.

 

이제 실제 데이터를 정의 하고 넣어보자

 

넣어야 할 데이터는 다음과 같이 정의 하였다.

 

Person Struct

typedef struct _person
{
    char *name;
    char *phone;
    int height;

} Person;

아까 언급했듯이 Hash Table을 쓰기 위해서는 del_func 과 Hash Key 에 쓸 필요한 자원을 Return해주는 Func이 필요하다.

 

우선 Person 을 만드는 함수를 만들자.

 

Person_new()

Person *Person_new(char *name, char *phone, int height)
{
    Person *ret = (Person *)malloc(sizeof(Person));
    char *input_name = (char *)malloc(strlen(name));
    char *input_phone = (char *)malloc(strlen(phone));

    strcpy(input_name, name);
    strcpy(input_phone, phone);

    ret->name = input_name;
    ret->phone = input_phone;
    ret->height = height;

    return ret;
}

arg 로 기록할 사람의 이름, 핸드폰, 키를 입력한다.

구조체는 메모리 할당받아 사용하고 char *역시 크기가 제각각이므로 메모리를 할당 받는다.

 

만약 Person 기록을 삭제한다면 malloc 한 부분들을 삭제 해주면 된다.

따라서 del 함수는 다음과 같이 만든다.

 

Person_del()

int Person_del(void *arg_p)
{
    int err = 0;

    Person *pers = (Person *)arg_p;
    if (!pers) {
        ERR_SET_OUT(err, ENOMEM);
    } else {
        /* person name member free */
        if (!pers->name) {
            ERR_SET_OUT(err, EINVAL);
        } else {
            free(pers->name);
        }
        /* person phone member free */
        if (!pers->phone) {
            ERR_SET_OUT(err, EINVAL);
        } else {
            free(pers->phone);
        }
        /* person struct free */
        free(pers);
    }

    return -err;
}

hash Table 함수에 등록 할수 있는 함수 포인터는 int 형을 return 하고 void 포인터를 Arg로 가지고 오므로 맞게 작성했다.

또한 문제가 있을 경우 0보다 작은 값을 반환해야하므로 -를 붙여 return 한다.

 

main 함수를 다음과 같이 만들어 검증하였다.

 

#include "HashTable.h"
#include "Person.h"
#include "string.h"
#include "stdio.h"


int main(void)
{
    printf("Start HashTable Program \r\n");

    Person *hyojin = Person_new((char *)"Park HyoJin", (char *)"010-1122-3456", 165);
    Person *jitae = Person_new((char *)"Kim JiTae", (char *)"010-2233-4567", 175);
    Person *seokha = Person_new((char *)"Kim SeokHa", (char *)"010-3344-5678", 172);
    Person *okhee = Person_new((char *)"Chae OkHee", (char *)"010-5566-7890", 161);
    Person *suyun = Person_new((char *)"Kim Suyun", (char *)"010-7788-9012", 174);

    HashTable *personBook = NULL;

    personBook = HashTableInit(Person_keyData, Person_del);

    personBook->insert(personBook, (void *)hyojin);
    personBook->insert(personBook, (void *)jitae);
    personBook->insert(personBook, (void *)seokha);
    personBook->insert(personBook, (void *)okhee);
    personBook->insert(personBook, (void *)suyun);

    Person *key_61 = *(Person **)personBook->get(personBook, 61);
    Person *key_72 = *(Person **)personBook->get(personBook, 72);

    printf("key_61: Name :%s , Number: %s, height: %d \r\n", key_61->name, key_61->phone, key_61->height);
    printf("key_72: Name :%s , Number: %s, height: %d \r\n", key_72->name, key_72->phone, key_72->height);

    personBook->remove(personBook, 72);
    key_72 = *(Person **)personBook->get(personBook, 72);

    printf("End HashTable Program \r\n");

    return 0;
}

 

실행화면

 

코드 참조: https://github.com/KJT9109/Data_Structure/tree/master/HashTable