Hash Table의 Chaining을 구현 해보자
기존 Hash Table 에서 약간(?) 심화 과정으로써 Hash Table에서 Hash Key가 겹쳤을 경우를 처리하는 자료구조이다.
위와 같은 상황이 놓여졌을 때 Chaining으로 하여 값을 Insert 한다.
Chaining은 Linked List로 구현하기 위해 Hash Table 구조체를 다음과 같이 수정하였다.
typedef struct _storage
{
void *mem_slot_p;
struct _storage *next_p;
} Storage;
typedef struct _hashTable
{
/* == hash table member == */
Storage **data_strge_pp;
/* == hash table work func == */
HashKey (*insert)(struct _hashTable *ht, void *data_p);
Storage *(*strMalloc)();
int (*remove)(struct _hashTable *ht, HashKey key_val);
void *(*get)(struct _hashTable *ht, HashKey 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;Hash Table Chaining 구조
이전에 구현했던 hash Table 과 비교하자면 void slot_pp 에서 data_strge_pp 로 변경되었다.
스토리지 안에는 데이터를 저장할 수 있는 void형 포인터와 linked list로 다음 Chain을 찾을 수 있는
next_p로 구성되어 있다.
또한 strMalloc이라는 멤버 함수 포인터가 추가 되었다.
** Hash Table에 추가된 함수
strMalloc: next_p에 할당 하는 함수 포인터
데이터가 중복되었을 경우 Chaining을 할 때 저장할 데이터 스토리지를 Malloc 해주는 함수이다.
코드 구현
HashTable *HashTableInit(int (*getSrc_func)(void *arg_p),
int (*delData_func)(void *arg_p))
{
TR_FUNC(TRACE);
HashTable *ret = (HashTable *)malloc(sizeof(HashTable));
ret->data_strge_pp = (Storage **)calloc(TABLE_SIZE, sizeof(Storage *));
for (int i = 0; i < TABLE_SIZE; i++) {
ret->data_strge_pp[i] = (Storage *)calloc(1, sizeof(Storage));
}
/* Hash Table Work Func */
ret->insert = HashTableInsert_Func;
ret->remove = HashTableDel_Func;
ret->get = HashTableGet_Func;
ret->strMalloc = HashTableStrMalloc_Func;
/* hash table make key func */
ret->makeKey = HashKey_Func;
/* member Struct Func */
ret->keySrc = getSrc_func;
ret->delData = delData_func;
return ret;
}기존에 구현했던 Init 한수에서 Malloc 함수가 추가되고 함수 네이밍은 크게 바뀐게 없다.
Hash Table Chaining 데이터 삽입(Insert)
HashTableInsert_Func()
static HashKey HashTableInsert_Func(HashTable *ht_p, void *data_p)
{
TR_FUNC(TRACE);
int key_src;
HashKey hash_key = {0,};
Storage *local_str_p = NULL;
if (!(ht_p) || !(data_p)) {
ERR_OUT(ENOMEM);
hash_key.value = -ENOMEM;
return hash_key;
}
/* hash key를 만들 resource를 가져온다. */
if ((key_src = ht_p->keySrc(data_p)) < 0) {
ERR_OUT(EINVAL);
hash_key.value = -EINVAL;
return hash_key;
/* resource를 가지고 hash key를 만든다. */
} else if ((hash_key.value = ht_p->makeKey(ht_p, key_src)) < 0) {
ERR_OUT(EINVAL);
hash_key.value = -EINVAL;
return hash_key;
} else {
if (!(&(ht_p->data_strge_pp[hash_key.value]))) {
ERR_OUT(EINVAL);
hash_key.value = -EINVAL;
return hash_key;
} else if (!(ht_p->data_strge_pp[hash_key.value]->mem_slot_p)) {
/* 스토리지 슬롯이 비워져 있으면 데이터를 추가한다. */
ht_p->data_strge_pp[hash_key.value]->mem_slot_p = data_p;
} else {
/* 비워져 있지 않으면 next_p를 참조하여 더이상 참조 할 수 없거나
슬롯이 비워져 있으면 멈춘다. */
local_str_p = ht_p->data_strge_pp[hash_key.value];
while (local_str_p->next_p != NULL && local_str_p->mem_slot_p != NULL) {
local_str_p = local_str_p->next_p;
hash_key.index++;
}
if (local_str_p->mem_slot_p == NULL) {
/* 슬롯이 비워져 있으면 데이터를 추가하고 끝낸다. */
local_str_p->mem_slot_p = data_p;
} else {
/* 슬롯이 비워져 있지 않으며 새로운 스토리지를 만든 후
해쉬테이블의 마지막 스토리지 next_p에 연결한다. */
local_str_p->next_p = ht_p->strMalloc();
if (local_str_p->next_p < 0) {
ERR_OUT(ENOMEM);
hash_key.value = -ENOMEM;
return hash_key;
} else {
/* 새로운 스토리지로 들어가서 데이터를 추가한다 */
hash_key.index++;
local_str_p = local_str_p->next_p;
local_str_p->mem_slot_p = data_p;
}
}
}
}
return hash_key;
}기존 코드에서 Hash key를 만드는 부분과 비워있는 Hash Table에 데이터를 삽입하는 부분은 똑같다.
(다만 Hash Table의 멤버 변수가 void 형 포인터에서 Storage 형 포인터로 변경되었으므로 삽입하는 부분도 변경되었다. ht->slot_pp[hash_key] = data_p; =>ht_p->data_strge_pp[hash_key.value]->mem_slot_p = data_p;)
이전 Hash Table 에서는 slot_p가 null 인지만 체크하여 만약 값이 있으면 데이터를 테이블에 넣지 못하고 그냥 빠져 나왔었다.
하지만 chaining 에서는 slot_p에 값이 없거나 or next_p에 값이 없을 때 까지 다음 Storage를 계속 찾아 간다.
Data Storage에 일반적으로 데이터를 추가하는 경우
데이터 정상적으로 추가 되었다면, 마지막 끝의 Data Storage에는 next_p의 값이 NULL로 되어있다.
따라서 새로운 Data Storage를 만들어 데이터를 추가하고 next_p에 Data Storage에 연결해 준다.
Data Storage는 있지만 Slot이 비워있는 경우
이 경우는 아래에 Remove 함수에서 언급할텐데 위와 같이 Mem_slot_p에는 값이 없고 next_p에만 값이 있는 storage가 있을 수 있다. 만약 next_p로 마지막 storage를 찾는 중 mem_slot_p가 비워져 있으면 굳이 새로운 Data Storage를 만들 필요 없다. 비워져 있는 slot_p에 데이터를 삽입하고 해당 Hash key 와 Index를 return 하면 된다.
Hash Table Chaining 데이터 삭제(remove)
HashTableDel_Func()
static int HashTableDel_Func(HashTable *ht_p, HashKey hash_key)
{
TR_FUNC(TRACE);
int err = 0;
Storage *local_str_p = NULL;
if (!(ht_p) || !(&(ht_p->data_strge_pp[hash_key.value]))) {
ERR_SET_OUT(err, EINVAL);
return err;
}
if (hash_key.index == 0 ) {
/* hash_key의 index가 0인 경우 데이터를 삭제하고 slot을 NULL로 바꾼다. */
if ((ht_p->delData(ht_p->data_strge_pp[hash_key.value]->mem_slot_p)) < 0) {
ERR_SET_OUT(err, EINVAL);
} else {
ht_p->data_strge_pp[hash_key.value]->mem_slot_p = NULL;
}
} else {
/* index가 0이 아니라면 해당 index까지 스토리지를 찾아간다. */
local_str_p = ht_p->data_strge_pp[hash_key.value];
for (int i = 0; i < hash_key.index; i++) {
local_str_p = local_str_p->next_p;
}
/* 찾은 스토리지의 slot을 삭제 후 NULL로 바꾼다 */
if ((ht_p->delData(local_str_p->mem_slot_p)) < 0) {
ERR_SET_OUT(err, EINVAL);
} else {
local_str_p->mem_slot_p = NULL;
}
}
return err;
}Hash Table chaining 에서 데이터를 삭제 하기 위해 우선 삭제해야 할 슬롯이 있는 Data Storage를 찾는다.
찾은 Data Storage에서 데이터 삭제 및 mem_slot_p를 NULL로 변경한 다음 그대로 두고 종료한다.
비워있는 Storage를 삭제하지 않고 두는 이유
만약 Data Storage를 삭제 후 next_p를 삭제한 Storage가 가리키는 next_p로 바꾼다면 index값이 바뀌게 된다.
즉 사용자가 해당 Hash key와 index를 가지고 데이터를 찾을려고 하면 다른 데이터를 찾게 되어 혼선 또는 hash key에 접근하여 다시 바꿔줘야 한다. (만약 Hash Table의 chaining이 100 ~ 200 개면 다 일일히 바꿔줘야 한다.)
따라서 Data Storage를 전부 삭제하는 것이 아닌 ht_p->delData() 의 콜백함수를 호출하여 저장한 데이터를 삭제하고
NULL로 변경해준다.
Hash Table Chaining 데이터 가져오기(Get)
HashTableGet_Func()
static void *HashTableGet_Func(HashTable *ht_p, HashKey hash_key)
{
TR_FUNC(TRACE);
Storage *local_str_p = NULL;
if (!(ht_p) || hash_key.value < 0 || hash_key.value > TABLE_SIZE) {
ERR_OUT(EINVAL);
return NULL;
}
local_str_p = ht_p->data_strge_pp[hash_key.value];
for (int i = 0; i < hash_key.index; i++) {
if (local_str_p->next_p) {
local_str_p = local_str_p->next_p;
} else {
ERR_OUT(ENOMEM);
return NULL;
}
}
return local_str_p->mem_slot_p;
}get 함수는 index 만큼 next_p를 참조하여 mem_slot_p를 return 해준다.
main 함수
int main(void)
{
printf("Start HashTable Program \r\n");
Person *hyojin = Person_new((char *)"Park HyoJin", (char *)"010-1122-3456", 175);
Person *jitae = Person_new((char *)"Kim JiTae", (char *)"010-2233-4567", 175);
Person *seokha = Person_new((char *)"Kim SeokHa", (char *)"010-3344-5678", 175);
Person *okhee = Person_new((char *)"Chae OkHee", (char *)"010-5566-7890", 175);
Person *suyun = Person_new((char *)"Kim Suyun", (char *)"010-7788-9012", 175);
Person *simba = Person_new((char *)"Kim Simba", (char *)"010-2233-4567", 175);
HashTable *personBook = NULL;
personBook = HashTableInit(Person_keyData, Person_del);
/* == Data Insert Test == */
printf("\r\n");
printf("Start Data Insert Test !!! \r\n");
HashKey k_1 = personBook->insert(personBook, (void *)hyojin);
printf("Insert data => Name: %s, Number :%s, height :%d\r\n", hyojin->name, hyojin->phone, hyojin->height);
printf("k_1: value: %d, index: %d \r\n", k_1.value, k_1.index);
HashKey k_2 = personBook->insert(personBook, (void *)jitae);
printf("Insert data => Name: %s, Number :%s, height :%d\r\n", jitae->name, jitae->phone, jitae->height);
printf("k_2: value: %d, index: %d \r\n", k_2.value, k_2.index);
HashKey k_3 = personBook->insert(personBook, (void *)seokha);
printf("Insert data => Name: %s, Number :%s, height :%d\r\n", seokha->name, seokha->phone, seokha->height);
printf("k_3: value: %d, index: %d \r\n", k_3.value, k_3.index);
HashKey k_4 = personBook->insert(personBook, (void *)okhee);
printf("Insert data => Name: %s, Number :%s, height :%d\r\n", okhee->name, okhee->phone, okhee->height);
printf("k_4: value: %d, index: %d \r\n", k_4.value, k_4.index);
HashKey k_5 = personBook->insert(personBook, (void *)suyun);
printf("Insert data => Name: %s, Number :%s, height :%d \r\n", suyun->name, suyun->phone, suyun->height);
printf("k_5: value: %d, index: %d \r\n", k_5.value, k_5.index);
/* == Data Get Test == */
printf("\r\n");
printf("Start Data Get Test !!! \r\n");
Person *key_1 = (Person *)personBook->get(personBook, k_1);
key_1 ? printf("key_1 => Name: %s , Number: %s, height: %d \r\n", key_1->name, key_1->phone, key_1->height) : printf("none \r\n");
Person *key_2 = (Person *)personBook->get(personBook, k_2);
key_2 ? printf("key_2 => Name: %s , Number: %s, height: %d \r\n", key_2->name, key_2->phone, key_2->height) : printf("none \r\n");
Person *key_3 = (Person *)personBook->get(personBook, k_3);
key_3 ? printf("key_3 => Name: %s , Number: %s, height: %d \r\n", key_3->name, key_3->phone, key_3->height) : printf("none \r\n");
Person *key_4 = (Person *)personBook->get(personBook, k_4);
key_4 ? printf("key_4 => Name: %s , Number: %s, height: %d \r\n", key_4->name, key_4->phone, key_4->height) : printf("none \r\n");
Person *key_5 = (Person *)personBook->get(personBook, k_5);
key_5 ? printf("key_5 => Name: %s , Number: %s, height: %d \r\n", key_5->name, key_5->phone, key_5->height) : printf("none \r\n");
/* == Data Change Test == */
printf("\r\n");
printf("Start Change !! \r\n");
key_5->phone = "010-600-6000";
printf("Change Number: %s\r\n", key_5->phone);
key_5 = (Person *)personBook->get(personBook, k_5);
key_5 ? printf("key_5 => Name :%s , Number: %s, height: %d \r\n", key_5->name, key_5->phone, key_5->height) : printf("none \r\n");
/* == Data remove Test == */
printf("\r\n");
printf("Start Remove !! \r\n");
Person *remove_p = NULL;
remove_p = (Person *)personBook->get(personBook, k_2);
printf("k_2 => value: %d, index: %d \r\n", k_2.value, k_2.index);
remove_p ? printf("Remove => Name :%s , Number: %s, height: %d \r\n", remove_p->name, remove_p->phone, remove_p->height) : printf("none \r\n");
personBook->remove(personBook, k_2);
remove_p = (Person *)personBook->get(personBook, k_2);
remove_p ? printf("Remove => Name :%s , Number: %s, height: %d \r\n", remove_p->name, remove_p->phone, remove_p->height) : printf("none \r\n");
/* == Data remove after insert Test == */
printf("\r\n");
printf("Start Re Insart !! \r\n");
HashKey k_6 = personBook->insert(personBook, (void *)simba);
printf("k_6 => value: %d, index: %d \r\n", k_6.value, k_6.index);
Person *key_6 = (Person *)personBook->get(personBook, k_6);
key_6 ? printf("key_6 => Name :%s , Number: %s, height: %d \r\n", key_6->name, key_6->phone, key_6->height) : printf("none \r\n");
printf("End HashTable Program \r\n");
return 0;
}
main 함수를 위와 같이 실행 하여 Hash Table을 검증하였다.
코드 주소: Data_Structure/HashTable_Chaining at master · KJT9109/Data_Structure (github.com)
'자료구조' 카테고리의 다른 글
| Hash Table 구현 (0) | 2022.05.10 |
|---|---|
| AVL Tree 구현 (0) | 2022.02.09 |
| 이진탐색트리 Search 후 remove 구현 (0) | 2022.01.31 |
| 이진탐색트리 Insert, Search 구현 (0) | 2022.01.02 |
| Radix 정렬 구현 (1) | 2021.12.26 |
