[해시] Hash Chaining 기법 구현

[해시] Hash란?에 작성한 Hash를 구현하는 방식 중 하나인

체이닝(Chaining) 기법을 구현하였습니다.

Hash 개념이 필요하신 분은 먼저 [해시] Hash란?을 참고해주세요

Chaining 기법

Hash Function이나 주어지는 Input Data에 따라 key간 Hash Index 충돌이 일어날 수 있다.

아래 그림과 같이 ▶ Hash Function = key mod 11 일 때, 

data = {8, 19, 30}은 동일한 Hash Index = "8" 을 가진다.

- 동일한 Hash Index를 가질 때, 연결리스트(Linked List)를 구현해서 처리할 수 있다.

- Hash Index마다 연결리스트를 지닌 형태

  Hash Index가 연결리스트에서 Header 역할을 한다고 보면된다.

- 연결리스트에서 Head 혹은 Tail 어느쪽에 Data를 추가할지는 구현하기 나름.

- 추가 / 삭제 / 탐색에 있어서 해당 Hash Index에서 연결리스트를 제어하면 된다.

- 추가적인 메모리 공간 할당 필요

 

구현 설명

Init

void Init(void)
{
    for (int i = 0; i < HASH_SIZE; i++)
    {
        hTbl[i].next = (Node*)0;
    }
}

- Hash Table에서 Header에 해당되는 곳의 next를 Null 처리

- Hash Index의 연결리스트를 비워주는 처리

- 아래와 같이 표시한 영역을 끊어주는 것이다.

 

PrintHash

void PrintHash(void)
{
    for (int i = 0; i < HASH_SIZE; i++)
    {
        printf("[%2d]: ", i);
        Node* p = hTbl[i].next;
        for (;;)
        {
            if (p == (Node*)0)
                break;
            printf("%d - ", p->value);
            p = p->next;
        }
        printf("\n");
    }
    puts("");
}

- Hash Table과 연결리스트를 보기 좋게 출력하기 위함

- Hash Index값과 연결된 원소만큼 줄줄이 출력해준다.

 

Insert

int Insert(Node* data)
{
    Node* p = &hTbl[GetKey(data->value)];
    Node* q = (Node*)calloc(1, sizeof(Node));
    if (q == NULL) return -1;
    *q = *data;
    for (;;)
    {
        if (p->next == NULL) break;
        p = p->next;
    }
    p->next = q;
    q->next = NULL;
    return 1;
}

- 새로운 Node를 추가하기 위해 메모리를 추가할당 한다. (calloc)

  할당받지 못하는 경우를 위한 예외처리

- 구현한 코드에서는 연결리스트에서 Tail 쪽에 추가되도록 하였다.

  연결리스트를 계속 따라가다가 끝 지점(p->next == NULL)에 도달한 경우

  아래와 같이 연결리스트를 처리해준다.

  

 

Search

Node* Search(int value)
{
    Node* p = hTbl[GetKey(value)].next;
    if (p == NULL)
        return NULL;
    for (;;)
    {
        if (p->value == value) return p;
        if (p->next == NULL) return NULL;
        p = p->next;
    }
}

특정 Hash Index에 위치한 연결리스트를 차례대로 탐색한다.

찾고자 하는 대상 value를 찾거나 연결리스트 끝(p->next == NULL)에 도달한 경우 멈춘다.

 

Remove

int Remove(int value)
{
    Node *prev = &hTbl[GetKey(value)];
    Node *p = prev->next;
    for (;;)
    {
        if (p == NULL) return 0;
        if (p->value == value)
        {
            prev->next = p->next;
            free(p);
            return 1;
        }
        prev = p;
        p = p->next;
    }
}

- 연결리스트에 존재하는 원소를 삭제할 때는

   Head / Tail / 중간에 위치한 원소를 삭제할 때, 좌/우로 연결되어 있는 원소를 주의해야 한다.

- 구현한 연결리스트에서는 이중(양방향) 연결리스트가 아니기 때문에

   대상을 찾은 경우, 이전 주소를 가리키는 *prev가 뒤따라서 삭제 후 연결처리를 도와준다.

 

전체 코드

- 이름 name[]과 같은 다양한 정보를 담을 수 있도록 구조체로 구현

#include <stdio.h>
#include <malloc.h>
const int MAX_N = 7;
const int HASH_SIZE = 11;
struct Node
{
    int value;
    Node* next;
}hTbl[HASH_SIZE];
Node data[] = { {44}, {13}, {15}, {8}, {21}, {19}, {30} };
int GetKey(int id)
{
    return id % HASH_SIZE;
}

void Init(void)
{
    for (int i = 0; i < HASH_SIZE; i++)
    {
        hTbl[i].next = (Node*)0;
    }
}

void PrintHash(void)
{
    for (int i = 0; i < HASH_SIZE; i++)
    {
        printf("[%2d]: ", i);
        Node* p = hTbl[i].next;
        for (;;)
        {
            if (p == (Node*)0)
                break;
            printf("%d - ", p->value);
            p = p->next;
        }
        printf("\n");
    }
    puts("");
}

int Insert(Node* data)
{
    Node* p = &hTbl[GetKey(data->value)];
    Node* q = (Node*)calloc(1, sizeof(Node));
    if (q == NULL) return -1;
    *q = *data;
    for (;;)
    {
        if (p->next == NULL) break;
        p = p->next;
    }
    p->next = q;
    q->next = NULL;
    return 1;
}

Node* Search(int value)
{
    Node* p = hTbl[GetKey(value)].next;
    if (p == NULL)
        return NULL;
    for (;;)
    {
        if (p->value == value) return p;
        if (p->next == NULL) return NULL;
        p = p->next;
    }
}

int Remove(int value)
{
    Node *prev = &hTbl[GetKey(value)];
    Node *p = prev->next;
    for (;;)
    {
        if (p == NULL) return 0;
        if (p->value == value)
        {
            prev->next = p->next;
            free(p);
            return 1;
        }
        prev = p;
        p = p->next;
    }
}

void main(void)
{
    Init();
    for (int i = 0; i < MAX_N; i++)
    {
        Insert(&data[i]);
    }
    PrintHash();
    int target = 19;
    if (Node* p = Search(target))
    {
        printf("탐색 결과 %d 는 존재.\n", p->value);
    }
    else
    {
        printf("탐색 결과 존재하지 않습니다.\n", target);
    }
    printf("\n=== 삭제 후 상태===\n");
    if (Remove(19))
    {
        PrintHash();
    }
    if (Node* p = Search(target))
    {
        printf("탐색 결과 %d 는 존재.\n", p->value);
    }
    else
    {
        printf("%d를 탐색 결과 존재하지 않습니다.\n\n", target);
    }
}

 

Reference

- [해시] Hash란?