자료구조 - 해싱(Hashing)

1. 해싱이란?

  해시(Hash)란 데이터를 다루는 기법 중 하나이며, 해시 함수(Hash function)는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑 전 원래 데이터의 값을 Key, 매핑 후 데이터의 값을 Hash Value 또는 해시 코드라고 하며 키와 값으로 매핑되는 과정 자체를 해싱이라고 한다.

  탐색, 삽입, 삭제 연산 모두 해시 함수를 거치는 시간만 소요되기 때문에 일반적으로 O(1)의 시간복잡도를 가진다.

 

2. 해시 테이블이란?

  해시 테이블(Hash table)은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. Hash table은 Hash 함수를 사용하여 색인(index, Key)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

  버킷 수는 해시 함수를 통해 나오는 주소 값의 범위, 슬롯 수는 각 버킷에 저장할 수 있는 데이터의 개수이다.

 

[예시문제]

주어진 N개의 key, data쌍을 Hash table에 입력한 후, Q개의 key를 입력 받아 key에 해당하는 data를 각 줄에 출력하시오. (1<=N, Q<=4096)
* Key : 최대 64개의 문자열
* Data : 최대 128개의 문자열

 

[Reference Code]

#include <stdio.h>
#include <string.h>
#include <memory.h>
 
#define MAX_KEY 64
#define MAX_DATA 128
#define MAX_TABLE 4096
 
typedef struct
{
    char key[MAX_KEY + 1];
    char data[MAX_DATA + 1];
}Hash;
Hash tb[MAX_TABLE];
 
unsigned long hash(const char *str)
{
    unsigned long hash = 5381;
    int c;
 
    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c) % MAX_TABLE;
    }
 
    return hash % MAX_TABLE;
}
 
int find(const char *key, char *data)
{
    unsigned long h = hash(key);
    int cnt = MAX_TABLE;
 
    while (tb[h].key[0] != 0 && cnt--)
    {
        if (strcmp(tb[h].key, key) == 0)
        {
            strcpy(data, tb[h].data);
            return 1;
        }
        h = (h + 1) % MAX_TABLE;
    }
    return 0;
}
 
int add(const char *key, char *data)
{
    unsigned long h = hash(key);
 
    while (tb[h].key[0] != 0)
    {
        if (strcmp(tb[h].key, key) == 0)
        {
            return 0;
        }
 
        h = (h + 1) % MAX_TABLE;
    }
    strcpy(tb[h].key, key);
    strcpy(tb[h].data, data);
    return 1;
}
 
 
int main(int argc, char* argv[])
{
    int T, N, Q;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        memset(tb, 0, sizeof(tb));
        scanf("%d", &N);
        char k[MAX_KEY + 1];
        char d[MAX_DATA + 1];
 
        for (int i = 0; i < N; i++)
        {
            scanf("%s %s\n", &k, &d);
            add(k, d);
        }
 
        printf("#%d\n", test_case);
 
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++)
        {
            char k[MAX_KEY + 1];
            char d[MAX_DATA + 1];
 
            scanf("%s\n", &k);
 
            if (find(k, d))
            {
                printf("%s\n", d);
            }
            else
            {
                printf("not find\n");
            }
        }
    }
    return 0;
}