해싱은 "탐색 알고리즘"에 대한 공부를 전제로 합니다. 선형 탐색, 이진 탐색 등 탐색 알고리즘에 대해서 잘 알지 못한다면 이번 포스팅의 이해가 쉽지 않을 것입니다. 그렇기에 해시 알고리즘을 공부하기 전 탐색 알고리즘을 먼저 공부하고 그 후에 이 포스팅을 읽으시는 것을 추천합니다. (탐색 알고리즘 공부하기)
해싱 개요
탐색 알고리즘을 공부하면 배우는 "선형 탐색"이나 "이진 탐색"과 같은 방법들은 어떤 데이터가 어떤 인덱스에 있는지에 대한 정보를 전혀 알지 못할 때 진행하는 방식이며, 키를 저장된 키값과 반복적으로 비교하는 방식으로 탐색합니다. 이러한 방식은 아주 빨라야 $O(\log n)$의 시간 복잡도를 가집니다. 이 정도 시간 복잡도만 가지더라도 괜찮지만 더욱 빠른 탐색을 필요로 하는 경우, 더욱 빠른 탐색 알고리즘가 필요합니다. 이러한 문제점을 해결하는 것이 바로 "해싱"입니다.
해싱은 키(Key)에 특정 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하는 방식입니다. 이렇게 해싱을 이용하여 데이터를 저장하는 자료구조를 "해시 테이블"이라고 합니다.
해시 테이블 (Hash Table)
해시 알고리즘을 위한 자료구조인 해시 테이블에 대해서 더 자세히 알아보도록 하겠습니다. 해시 테이블은 (Key, Value)로 저장되는 자료구조로 아주 빠른 데이터 검색 속도를 제공합니다. 해시 테이블은 "해시 함수"를 통하여 만들어진 해시 주소를 해시 테이블의 인덱스(Index)로 사용하는데 이 인덱스(Index)를 통하여 자료를 저장하고 자료에 접근할 수 있습니다.
해시 함수 (Hash Function)
해시 테이블의 정의에서 "해시 함수"라는 것이 있었는데, 해시 함수는 무엇일까요? 바로 해시 함수는 "키값을 해시 테이블의 주소로 변환하는 함수"입니다. 해시 테이블에서 사용하는 인덱스는 "해시 주소"인데 해시 주소가 바로 해시 함수를 통하여 만들어집니다. 그렇기에 해시 함수가 잘 설계가 되어야 탐색의 효율이 높아지는 것입니다. 잘 설계된 해시 함수의 조건은 다음과 같습니다.
- 충돌이 적어야 한다.
- 해시함수 값이 해시 테이블의 주소 영역 내에 고르게 분포되어야 한다.
- 계산이 빨라야 한다.
이를 위해서 예시를 들어보겠습니다. 영어로 된 식당의 이름의 첫 번째 글자를 취해 해시함수를 사용한다고 합시다. 이는 해시 함수로 적합하지 않습니다. A, B 등 이니셜로 주로 사용하는 알파벳의 경우 많은 값들이 모이겠지만 X, Z 등 이니셜로 잘 사용하지 않는 알파벳의 경우 값들이 잘 모이지 않아 해시 테이블의 값들이 고르게 분포되지 않을 것입니다. 이러한 경우는 해시 함수가 잘 짜여있지 않은 것입니다. 이는 탐색의 속도에 영향을 끼치게 반드시 잘 설계된 해시 함수를 사용해야 합니다. 주로 사용하는 해시 함수들은 다음과 같은 것들이 있습니다.
- 제산 함수: 나머지 연산자(mod)를 사용하여 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법
- 폴딩 함수: 키를 여러 부분으로 나누어 더하거나 비트별로 XOR과 같은 부울 연산을 한 값을 해시 주소로 사용하는 방법
- 중간 제곱 함수: 키를 제곱한 다음, 중간의 몇 비트를 취한 값을 해시 주소로 사용하는 방법
- 비트 추출 방법: 해시 테이블의 크기가 $M = 2^k$일 때, 키를 이진수로 여겨 임의의 위치의 $k$개의 비트를 해시 주소로 사용하는 방법
- 숫자 분석 방법: 키의 각각의 위치에 있는 숫자 중에 편중되지 않은 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법
- 문자열의 경우: 키들이 정수일 때는 쉽게 해시 함수로 변환할 수 있기에, 문자열을 아스키 코드나 유니코드 값으로 변환하여 해시 주소로 사용한다.
충돌과 오버플로우 (Collision & Overflow)
위의 좋은 해시 함수의 조건으로 "충돌이 적어야 한다"가 있었는데, 이것이 의미하는 것은 무엇일까요?
충돌이란 서로 다른 키를 가지는 항목들이 같은 해시주소를 가지는 현상입니다. 그리고 충돌이 발생하고 해시 주소에 더 이상 빈 버킷이 남아 있지 않으면 오버플로우가 발생합니다. 충돌과 오버플로우가 발생할 경우, 해시 테이블에 항목을 저장하는 것이 불가능해지며 또한 더 이상 정확한 값을 탐색할 수 없게 됩니다. 그렇기에 충돌과 오버플로우를 효과적으로 해결하는 것이 중요합니다. 해결책으로는 다음의 2가지가 있습니다.
- 개방 주소법(Open Adderessing): 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다. 즉, 해시테이블의 빈 공간을 찾는 것(조사)이다.
- 체이닝(Chaining): 해시 테이블의 하나의 위치가 여러 개의 항목을 저장하도록 해시 테이블의 구조를 변경한다.
개방 주소법 (Open Addressing)
개방 주소법의 종류로는 "선형 조사법", "이차 조사법", "이중 해싱법", "임의 조사법" 등이 있습니다.
선형 조사법 (Linear Probing)
먼저 선형 조사법에서는 충돌이 HashTable[k]에서 발생했다면 HashTable[k+1]이 비었는지를 살펴보고, 비어있지 않다면 HashTable[k+2]를 살펴보며 이러한 방식으로 빈 공간을 찾을 때까지 조사를 진행하는 방식입니다. 테이블의 끝에 도달하면 테이블의 처음으로 돌아갑니다. 선형 조사법에서 조사되는 위치를 수식으로 나타내면 다음과 같습니다.
$$ h(k), h(k)+1, h(k)+2, h(k)+3, \cdots $$
선형 조사법을 C언어 코드로 나타내면 다음과 같습니다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define KEY_SIZE 10 // 탐색키의 최대길이
#define TABLE_SIZE 13 // 해싱 테이블의 크기=소수
typedef struct
{
char key[KEY_SIZE];
// 다른 필요한 필드들
} element;
element hash_table[TABLE_SIZE]; // 해싱 테이블
void init_table(element ht[])
{
int i;
for (i = 0; i<TABLE_SIZE; i++) {
ht[i].key[0] = NULL;
}
}
// 문자로 된 키를 숫자로 변환
int transform1(char *key)
{
int number = 0;
while (*key)
number = number + *key++;
return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char *key)
{
// 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
return transform1(key) % TABLE_SIZE;
}
#define empty(item) (strlen(item.key)==0)
#define equal(item1, item2) (!strcmp(item1.key,item2.key))
// 선형 조사법을 이용하여 테이블에 키를 삽입하고,
// 테이블이 가득 찬 경우는 종료
void hash_lp_add(element item, element ht[])
{
int i, hash_value;
hash_value = i = hash_function(item.key);
//printf("hash_address=%d\n", i);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색키가 중복되었습니다\n");
exit(1);
}
i = (i + 1) % TABLE_SIZE;
if (i == hash_value) {
fprintf(stderr, "테이블이 가득찼습니다\n");
exit(1);
}
}
ht[i] = item;
}
// 선형조사법을 이용하여 테이블에 저장된 키를 탐색
void hash_lp_search(element item, element ht[])
{
int i, hash_value;
hash_value = i = hash_function(item.key);
while (!empty(ht[i]))
{
if (equal(item, ht[i])) {
fprintf(stderr, "탐색 %s: 위치 = %d\n", item.key, i);
return;
}
i = (i + 1) % TABLE_SIZE;
if (i == hash_value) {
fprintf(stderr, "찾는 값이 테이블에 없음\n");
return;
}
}
fprintf(stderr, "찾는 값이 테이블에 없음\n");
}
// 해싱 테이블의 내용을 출력
void hash_lp_print(element ht[])
{
int i;
printf("\n===============================\n");
for (i = 0; i<TABLE_SIZE; i++)
printf("[%d] %s\n", i, ht[i].key);
printf("===============================\n\n");
}
// 해싱 테이블을 사용한 예제
int main(void)
{
char *s[7] = { "do", "for", "if", "case", "else", "return", "function" };
element e;
for (int i = 0; i < 7; i++) {
strcpy(e.key, s[i]);
hash_lp_add(e, hash_table);
hash_lp_print(hash_table);
}
for (int i = 0; i < 7; i++) {
strcpy(e.key, s[i]);
hash_lp_search(e, hash_table);
}
return 0;
}이차 조사법 (Quadratic Probing)
이차 조사법에서는 해시 테이블의 빈 공간을 조사할 때, 해시 키값에 충돌 횟수의 제곱을 한 수를 더한 값을 확인하며 조사를 진행합니다. 이차 조사법에 의해 조사되는 위치는 다음과 같습니다.
$$ h(k), h(k)+1, h(k)+4, h(k)+9, \cdots $$
이차 조사법을 C언어 코드로 나타내면 다음과 같습니다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define KEY_SIZE 10 // 탐색키의 최대길이
#define TABLE_SIZE 13 // 해싱 테이블의 크기=소수
#define empty(item) (strlen(item.key)==0)
#define equal(item1, item2) (!strcmp(item1.key,item2.key))
typedef struct
{
char key[KEY_SIZE];
// 다른 필요한 필드들
} element;
element hash_table[TABLE_SIZE]; // 해싱 테이블
// 해시테이블 초기화
void init_table(element ht[])
{
int i;
for (i = 0; i<TABLE_SIZE; i++) {
ht[i].key[0] = NULL;
}
}
// 문자로 된 키를 숫자로 변환
int transform1(char *key)
{
int number = 0;
while (*key)
number = number + *key++;
return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char *key)
{
// 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
return transform1(key) % TABLE_SIZE;
}
void hash_qp_add(element item, element ht[])
{
int i, hash_value, inc = 0;
hash_value = i = hash_function(item.key);
//printf("hash_address=%d\n", i);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색키가 중복되었습니다\n");
exit(1);
}
i = (hash_value + inc*inc) % TABLE_SIZE;
inc = inc + 1;
if (i == hash_value) {
fprintf(stderr, "테이블이 가득찼습니다\n");
exit(1);
}
}
ht[i] = item;
}이중 해싱법 (Double Hashing)
이중 해싱법은 오버플로우로 인해 항목을 저장할 다음 위치를 결정해야 할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법입니다. 즉, 함수를 2개를 이용하여 충돌을 해결하는 것입니다. 이때 첫 번째 해시 함수는 키를 근거로 저장 위치를 정하기 위함이고, 두 번째 해시 함수는 충돌 발생 시 몇 칸 뒤를 조사할지를 정하기 위함입니다. 두 번째 해시 함수의 일반적인 형태는 다음과 같습니다. (이때, C는 보통 테이블의 크기인 M보다 약간 작은 소수(Prime Number)입니다.)
$$h'(k) = C - (k % C)$$
그러면 충돌이 발생했을 경우, 이중 해싱법에 따라 조사되는 위치는 다음과 같습니다.
$$ h(k), h(k)+h'(k), h(k)+2h'(k), h(k)+3h'(k), \cdots $$
이중 해싱법을 C언어 코드로 나타내면 다음과 같습니다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define KEY_SIZE 10 // 탐색키의 최대길이
#define TABLE_SIZE 13 // 해싱 테이블의 크기=소수
#define empty(item) (strlen(item.key)==0)
#define equal(item1, item2) (!strcmp(item1.key,item2.key))
typedef struct
{
char key[KEY_SIZE];
// 다른 필요한 필드들
} element;
element hash_table[TABLE_SIZE]; // 해싱 테이블
// 해시테이블 초기화
void init_table(element ht[])
{
int i;
for (i = 0; i<TABLE_SIZE; i++) {
ht[i].key[0] = NULL;
}
}
// 문자로 된 키를 숫자로 변환
int transform1(char *key)
{
int number = 0;
while (*key)
number = number + *key++;
return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char *key)
{
// 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
return transform1(key) % TABLE_SIZE;
}
void hash_dh_add(element item, element ht[])
{
int i, hash_value, inc;
hash_value = i = hash_function(item.key);
inc = hash_function(item.key);
//printf("hash_address=%d\n", i);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색키가 중복되었습니다\n");
exit(1);
}
i = (i + inc) % TABLE_SIZE;
if (i == hash_value) {
fprintf(stderr, "테이블이 가득찼습니다\n");
exit(1);
}
}
ht[i] = item;
}체이닝 (Chaining)
충돌을 해결하는 두 번째 방법은 바로 "체이닝"입니다. 체이닝은 해시 테이블의 구조를 변경하여 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 것입니다. 체이닝은 오버플로우 문제를 연결 리스트를 통하여 해결합니다. 각 버킷에 삽입과 삭제가 쉬운 연결 리스트를 할당하여 원하는 항목을 찾을 때는 연결 리스트를 순차적으로 돌면서 탐색합니다.
체이닝을 C언어 코드로 나타내면 다음과 같습니다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 해싱 테이블의 내용을 출력
#define TABLE_SIZE 7 // 해싱 테이블의 크기=소수
typedef struct {
int key;
} element;
struct list
{
element item;
struct list *link;
};
struct list *hash_table[TABLE_SIZE];
// 제산 함수를 사용한 해싱 함수
int hash_function(int key)
{
return key % TABLE_SIZE;
}
// 체인법을 이용하여 테이블에 키를 삽입
void hash_chain_add(element item, struct list *ht[])
{
int hash_value = hash_function(item.key);
struct list *ptr;
struct list *node_before = NULL, *node = ht[hash_value];
for (; node; node_before = node, node = node->link) {
if (node->item.key == item.key) {
fprintf(stderr, "이미 탐색키가 저장되어 있음\n");
return;
}
}
ptr = (struct list *)malloc(sizeof(struct list));
ptr->item = item;
ptr->link = NULL;
if (node_before)
node_before->link = ptr;
else
ht[hash_value] = ptr;
}
// 체인법을 이용하여 테이블에 저장된 키를 탐색
void hash_chain_search(element item, struct list *ht[])
{
struct list *node;
int hash_value = hash_function(item.key);
for (node = ht[hash_value]; node; node = node->link) {
if (node->item.key == item.key) {
fprintf(stderr, "탐색 %d 성공 \n", item.key);
return;
}
}
printf("키를 찾지 못했음\n");
}
// 해시 테이블의 내용을 출력
void hash_chain_print(struct list *ht[])
{
struct list *node;
int i;
printf("\n===============================\n");
for (i = 0; i<TABLE_SIZE; i++) {
printf("[%d]->", i);
for (node = ht[i]; node; node = node->link) {
printf("%d->", node->item.key);
}
printf("\n");
}
printf("===============================\n");
}
#define SIZE 5
// 해싱 테이블을 사용한 예제
int main(void)
{
int data[SIZE] = { 8, 1, 9, 6, 13 };
element e;
for (int i = 0; i < SIZE; i++) {
e.key = data[i];
hash_chain_add(e, hash_table);
hash_chain_print(hash_table);
}
for (int i = 0; i < SIZE; i++) {
e.key = data[i];
hash_chain_search(e, hash_table);
}
return 0;
}해시 알고리즘의 시간 복잡도 분석
마지막으로 해시 알고리즘의 시간 복잡도를 분석해보도록 하겠습니다.
해시 테이블에 자료를 추가하고 접근하고 삭제하는 연산들은 모두 탐색을 통히여 이루어집니다. 해시 테이블은 (Key, Value)로 이루어진 자료구조이고 해시함수를 1번만 사용하여 모든 연산을 진행할 수 있기에 해시 알고리즘의 시간 복잡도는 $O(1)$입니다.
그러나, 이는 충돌이 전혀 일어나지 않는다는 전제에서만 가능합니다. 해시 알고리즘에서 충돌이 없다는 것은 사실상 불가능합니다. 충돌이 일어날 경우에는 해시의 탐색 연산은 $O(1)$보다 느려지게 됩니다. 데이터의 충돌이 일어나면 체이닝으로 연결된 리스트들을 모두 탐색해야 하므로 시간 복잡도가 $O(n)$까지 늘어나게 됩니다.
해시 알고리즘의 시간 복잡도를 표로 정리하면 다음과 같습니다.
| 탐색 방법 | 탐색 | 삽입 | 삭제 | |
| 해싱 (Hashing) |
최선의 경우 | $O(1)$ | $O(1)$ | $O(1)$ |
| 최악의 경우 | $O(n)$ | $O(n)$ | $O(n)$ | |
