[자료구조] Hashtable Implementation in C

원문 링크 :

https://www.youtube.com/watch?v=wg8hZxMRwcw

천재적인 아이디어로 자료를 저장하는 hashtable

 

한 엔지니어 유튜버(포프) 영상에서 자신이 사원 채용을 할 때 hashtable을 간단하게 구현해보라는 질문을 하기도 한다고 말했다.

 

이는 hashtable이 CS에서 기초적이고 중요한 부분이라는 것을 의미하고 이를 구현할 수 있을 정도로 이해하고 있는 것이 중요하다는 것을 시사한다.

 

hashtable 구현을 좀 더 익히기 위해 위의 영상을 참고했다.

 

위의 동영상의 댓글을 확인하던 중 program 종료전 memory free를 해주지 않아 결과적으로 memory leak이 발생한다는 의견을 발견했다.

---

Memory leak : 더이상 필요하지 않은 메모리가 free되지 않은 경우.  메모리할당 관리를 잘 하지 못한 경우 발생한다. 프로그램 종료후 저장된 메모리에 더이상 접근할 수 없을 때에도 이를 memory leak이라고 하기도 한다. (Wikipedia)

---

memory leak 에 대한 의견 링크:

https://github.com/engineer-man/youtube/pull/25

Create ht_destroy routine to properly free up memory. Added call to m… by itsallmathematics · Pull Request #25 · engineer-man/yo

사실 나도 항상 data structure 공부를 할 때 아이디어를 구현하는 데에만 집중했지, memory free하는 부분에 주의를 기울이지 않았다. 이번에는 memory free 함수를 메인함수 종료 전 부분에 삽입했다.

 

외부 도움을 받지 않고 hashtable을 구현하려고 노력했다.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define TABLE_SIZE 100000
        
typedef struct entry_t{
    const char *key;
    const char *value;
    struct entry_t *next;
}entry_t;
 
typedef struct{
    entry_t **entries;
}ht_t;
 
unsigned int hash(const char *key) {
    unsigned long int value = 0;
    unsigned int i = 0;
    unsigned int key_len = strlen(key);
 
    for (; i < key_len; i++) {
        value = value * 37 + key[i];
    }
 
    value = value % TABLE_SIZE;
 
    return value;
}
 
ht_t *createHt(void) {
    ht_t *hashtable = malloc(sizeof(ht_t)*1);
    hashtable->entries = malloc(sizeof(entry_t*)*TABLE_SIZE);
 
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashtable->entries[i] = NULL;
    }
 
    return hashtable;
}
 
entry_t *ht_pair(const char *key, const char *value) {
    entry_t *entry = malloc(sizeof(entry_t) * 1);
    entry->key = malloc(strlen(key) + 1);
    entry->value = malloc(strlen(value) + 1);
 
    strcpy(entry->key, key);
    strcpy(entry->value, value);
 
    entry->next = NULL;
 
    return entry;
}
 
void ht_Set(ht_t *hashtable ,const char *key, const char *value) {
    unsigned int bucket = hash(key);
 
    entry_t *entry = hashtable->entries[bucket];
 
    if (hashtable->entries[bucket] == NULL) {
        hashtable->entries[bucket] = ht_pair(key, value);
        return;
    }
 
    entry_t *prev = NULL;
 
    while (entry != NULL) {
        if (strcmp(entry->key,key)==0) {
            free(entry->value);
            entry->value = malloc(strlen(value) + 1);
            strcpy(entry->value, value);
            return;
        }
        prev = entry;
        entry = entry->next;
    }
    prev->next = ht_pair(key, value);
}
entry_t *ht_Get(ht_t *hashtable, const char *key) {
    unsigned int slot = hash(key);;
 
    entry_t *entry = hashtable->entries[slot];
 
    if (entry == NULL) {
        return NULL;
    }
 
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return NULL;
}
 
void ht_Print(ht_t *hashtable) {
    entry_t *entry = NULL;
 
    int i = 0;
    for (; i < TABLE_SIZE; i++) {
        entry = hashtable->entries[i];
        if (entry == NULL) {
            continue;
        }
        printf("slot [%d] : ", i);
        do{
            printf("%s=%s ", entry->key, entry->value);
            entry = entry->next;
        } while (entry != NULL);
        printf("\n");
    }
}
 
void ht_Free(ht_t *hashtable) {
    if (!hashtable) return;
 
    int i = 0;
    if (hashtable->entries) {
        for (; i < TABLE_SIZE; i++) {
            if (hashtable->entries[i]) {
                if (hashtable->entries[i]->key) {
                    free(hashtable->entries[i]->key);
                    hashtable->entries[i]->key = NULL;
                }
                if (hashtable->entries[i]->value) {
                    free(hashtable->entries[i]->value);
                    hashtable->entries[i]->value = NULL;
                }
                free(hashtable->entries[i]);
                hashtable->entries[i] = NULL;
            }
        }
        free(hashtable->entries);
        hashtable->entries = NULL;
    }
    free(hashtable);
    hashtable = NULL;
    return;
}
 
int main() {
    ht_t *hashtable = createHt();
    ht_Set(hashtable, "name1", "Kimdonggoo");
    ht_Set(hashtable, "name2", "Kimchungui");
    ht_Set(hashtable, "name3", "Kooganghoi");
    ht_Set(hashtable, "name4", "Kimkione");
    ht_Set(hashtable, "name5", "Dodonghoon");
    ht_Set(hashtable, "name6", "Chujeongwoo");
 
    ht_Print(hashtable);
    ht_Free(hashtable);
    return 0;
}

library를 불러오는 부분에서 <limits.h> 의 역할에 의문이 생겨 검색해봤다.

이는 변수타입들의 최대 최소값을 정수형태로 리턴하는 library인데 이 코드에서 어떻게 활용됐는지 모르겠다.

해당 library에 해당하는 term을 사용하지 않은 것으로 보이기 때문이다.

하지만 "#include <limits.h>"를 제외하면 코드가 잘 작동하지 않는다.

더 찾아봐야겠다.

 

*

string비교, 복사

free할 때 안에 있는 컨텐츠 부터 free하고 점차 밖으로 free

typedef 잘 활용하지 않았었는데 생각보다 편리한 거 같다