[C]선형탐색 방법을 이용한 해시 테이블(Linear Probing)

22 Apr 2021 in C on ETC

1️⃣ 해시 테이블 구현(배열 이용)

(1) 배열을 사용한 간단한 해시 테이블 예시

#define BUCKET_SIZE (29)
#define INIT (-1)
#define FALSE (-1)
#define TRUE (1)

/* 해시로 만들어주는 함수 */
int hash(int value)
{
    int hs;

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

    return (hs);
}

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

/* 해시테이블에서 값을 찾는 함수 */
int find_value(int value, int *hashtable)
{
    int i;
    int start_index;

    start_index = hash(value);
    i = start_index;

    do {
        if (hashtable[i] == value)
            return (i);
        else if (hashtable[i] == INIT)
            return (FALSE);
        i = (i + 1) % BUCKET_SIZE;
    } while (i != start_index);

    return (FALSE);    
}

/* 해시테이블에 값을 추가하는 함수 */
int add_value(int value, int *hashtable)
{
    int i;
    int start_index;

    start_index = hash(value);
    i = start_index;

    do {
        if (hashtable[i] == value || hashtable[i] == INIT)
        {
            hashtable[i] = value;
            return (TRUE);
        }
        i = (i + 1) % BUCKET_SIZE;
    } while (i != start_index);

    return (FALSE);
}

입력값또한 데이터(문자열 등..)을 해쉬함수를 통해 생성된 값입니다.
그렇기 때문에 위의 예에서 입력값을 해시 값이라고 볼 수도 있습니다.
해시 값을 정해진 리소스안에 담기위해 %연산을 사용하여 크기를 줄여준 것 입니다.

< 사용 예(main함수) >

#include <stdio.h>

int main(void)
{
    int hashtable1[BUCKET_SIZE];

    init_hashtable(hashtable1);

    add_value(233, hashtable1);
    add_value(377, hashtable1);
    add_value(322, hashtable1);
    add_value(1, hashtable1);
    add_value(130, hashtable1);
    add_value(623, hashtable1);
    add_value(762, hashtable1);
    add_value(445, hashtable1);
    add_value(923, hashtable1);
    add_value(142, hashtable1);
    add_value(888, hashtable1);

    for (int i = 0; i < BUCKET_SIZE; i++)
    {
        if (hashtable1[i] == INIT)
            continue;
        printf("%d: %d\n", i, hashtable1[i]);
    }
    printf("\n");
}

/* 출력 */
0: 377
1: 233
2: 1
3: 322
8: 762
10: 445
14: 130
15: 623
18: 888
24: 923
26: 142

위의 예시와 아래 그림을 비교해봤을 때 색인값이 중복될 경우 다음 빈칸으로 순차적으로 배정됨을 확인할 수 있습니다.

(2) 해시 테이블에 문자열 저장하기

지금까지 해시 테이블의 간단한 예시 몇가지를 알아봤고 간단한 해시함수를 이용해봤습니다. 하지만 데이터는 다양한 자료형이 존재합니다.
대표적으로 문자열(char *)의 형식의 데이터를 해시값으로 만드는 해시 함수가 있습니다.
char형의 크기는 1byte로 이 데이터를 해시값으로 바꾸는 해시함수라면 왠만한 자료형들을 다룰 수 있을 것입니다.
자세한 내용은 다음 포스트에서 정리하도록 하겠습니다.
>>>>>해시 테이블에 문자열 저장하기