[C]연결리스트를 이용한 해시 테이블(hash table/chaining)

in C on ETC


1️⃣ 해시 테이블 구현(연결리스트 사용)

(1) 연결리스트 해시 테이블의 특징

  • 연결리스트를 이용하면 해시충돌의 걱정없이 값을 해시테이블에 저장할 수 있습니다.
  • 그 대신 연결리스트를 이용한 해시테이블은 값을 추가할 때마다 노드를 동적할당을 이용하여 추가해주어야 하기 때문에 메모리 관리, 속도면에서 효율이 떨어질 수 있습니다.
  • 또한 리소스사용에 대한 효율이 떨어진다는 큰 단점이 있습니다.
  • 먼저 간단한 연결리스트를 이용한 해시테이블을 구현해 보도록 하겠습니다.

(2) 연결리스트를 사용한 간단한 해시 테이블 예시

#include <stdlib.h>
#include <stdio.h>

#define BUCKET_SIZE (23)
#define FALSE (-1)
#define TRUE (1)

/* 해시테이블 연결리스트 구조체 */
typedef struct hash_s{
    struct hash_s   *next;
    int             value;
}   hash_t;

/* 해시테이블 초기화 함수 */
void init_hashtable(hash_t **hashtable)
{
    for (int i = 0; i < BUCKET_SIZE; i++)
        hashtable[i] = NULL;
}

/* 해시테이블 메모리해제 함수 */
void node_free(hash_t **hashtable)
{
    for (int i = 0; i < BUCKET_SIZE; i++)
    {
        free(hashtable[i]);
        hashtable[i] = NULL;
    }
}

/* 지정된 해시값으로 변경하는 함수 */
int hash(int value)
{
    int hs;

    hs = value % BUCKET_SIZE;
    if (hs < 0)
        hs += BUCKET_SIZE;
    return (hs);
}

/* 새로운 노드를 생성하여 value를 삽입하는 함수(add_value함수 내부에 존재) */
void add_index(hash_t **hashtable, int val)
{
    hash_t *new_node;

    new_node = (hash_t *)malloc(sizeof(hash_t));
    new_node->value = val;
    new_node->next = *hashtable;
    *hashtable = new_node;
}

/* value를 해시테이블에서 찾아주는 함수 */
int find_value(hash_t **hashtable, int val)
{
    int hs;
    hash_t *finder;

    hs = hash(val);
    finder = hashtable[hs];
    while (finder != NULL)
    {
        if (finder->value == val)
            return (TRUE);
        finder = finder->next;
    }
    return (FALSE);
}

/* 새로운 value를 해시테이블에 추가해주는 함수 */
int add_value(hash_t **hashtable, int val)
{
    int hs;

    if (find_value(hashtable, val) == TRUE)
        return (FALSE);
    hs = hash(val);
    while (*hashtable != NULL)
        *hashtable = (*hashtable)->next;
    add_index(&hashtable[hs], val);
    return (hs);
}

/* 해당 색인에 저장된 모든 value를 출력하는 함수 */
void print_index(hash_t **hashtable, int index)
{
    hash_t *finder;

    finder = hashtable[index];
    if (finder == NULL)
    {
        printf("존재하는 요소가 없습니다.\n");
        return ;
    }
    printf("%d색인 요소: ", index);
    while(finder != NULL)
    {
        printf("%d ", finder->value);
        finder = finder->next;
    }
    printf("\n");
}

/* 해당 value가 저장된 노드를 삭제하는 함수 */
int delete_value(hash_t **hashtable, int val)
{
    int hs;
    hash_t *temp;
    hash_t *finder;

    hs = hash(val);
    finder = hashtable[hs];
    if (finder == NULL)
        return (FALSE);
    if (hashtable[hs]->value == val)
    {
        temp = hashtable[hs]->next;
        free(hashtable[hs]);
        hashtable[hs] = temp;
        return (TRUE);
    }
    while (finder->next != NULL)
    {
        if ((finder->next)->value == val)
        {
            temp = (finder->next)->next;
            free(finder->next);
            finder->next = temp;
            return (TRUE);
        }
        finder = finder->next;
    }
    return (FALSE);
}

(3) (프로그램이용)main함수

int main(void)
{
    hash_t *hashtable[BUCKET_SIZE];
    hash_t *temp;
    int index;

    init_hashtable(hashtable); 

    index = add_value(hashtable, 333);
    printf("%d가 %d번 색인에 저장되었습니다.\n", 333, index);
    index = add_value(hashtable, 356);
    printf("%d가 %d번 색인에 저장되었습니다.\n", 356, index);
    index = add_value(hashtable, 34);
    printf("%d가 %d번 색인에 저장되었습니다.\n", 34, index);
    print_index(hashtable, 11);
    printf("\n");

    index = delete_value(hashtable, 356);
    if (index == TRUE)
        printf("정상적으로 값이 삭제되었습니다.\n");
    else
        printf("삭제할 값이 존재하지않습니다.\n");
    print_index(hashtable, 11);
    printf("\n");

    index = delete_value(hashtable, 27);  // 존재하지않는 값을 삭제할 시
    if (index == TRUE)
        printf("정상적으로 값이 삭제되었습니다.\n");
    else
        printf("삭제할 값이 존재하지않습니다.\n");
    node_free(hashtable);
}
/* 출력 */
333가 11번 색인에 저장되었습니다.
356가 11번 색인에 저장되었습니다.
34가 11번 색인에 저장되었습니다.
11색인 요소: 34 356 333

정상적으로 값이 삭제되었습니다.
11색인 요소: 34 333

삭제할 값이 존재하지않습니다.

(4) 연결리스트 해쉬 테이블 vs 이차원배열 해쉬 테이블

  • 실행중에 동적메모리의 할당과 해제를 해줘야하며, 배열처럼 위치를 기억하는 index가 없기 때문에 색인이 겹칠경우 처음부터 탐색해야되는 구조입니다. (겹치는 색인이 많을 수록 속도면에서 효율이 떨어집니다. BUCKET_SIZE를 크게하여 색인이 겹치는 경우를 줄이는 것도 한가지 방법입니다.)
  • 또한 연결리스트를 이용하면 값의 삭제, 삽입이 비교적 자유롭고 구조체의 특성을 이용하여 원하는 해시값에 관련된 다른 정보들도 저장할 수 있습니다.
  • 하지만 실행중에 정보를 삭제, 삽입할 일이 적고 이미 데이터에 대해 알고있다면 굳이 동적할당을 하는 것은 비효율 적입니다.
  • 되도록이면 동적할당의 사용을 자제하는 것을 C언어는 지향(?)하기 때문에, 만약 추가할 값들을 이미 알고 있어서 크기를 고정시킬 수 있는 경우라면 연결리스트보다는 이차원배열을 사용하는 것이 좋을 것 같습니다. (실제로 게임업계에서 많이 사용하는 방식이라고 합니다.)
  • 이차원배열로 만든 해시테이블에서 해당해시 값에 추가적으로 정보를 추가하고 싶으면 같은 인덱스의 구조를 가지는 배열을 만들어서 대응되게 값을 저장하면 됩니다.

(5) 선형 탐색(Linear Probing)방식의 해시 테이블

  • 연결리스트를 이용한 해시테이블(chaining)방식은 특정 색인(index)만 사용하게되어 안쓰게되는 Bucket이 생기게 됩니다. (리소스적으로 손실)
  • 그렇기 때문에 선형 탐색 해시 테이블(Linear Probing)을 이용하면 메모리적으로 효율이 올라갑니다.
  • 자세한 내용은 다음 포스트에서 정리하도록 하겠습니다.
    >>>>>선형 탐색 해시 테이블 만들기


© 2021.02. by kirim

Powered by kkrim