선형 탐색이나, 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 이런 방법도 좋은 방법이지만, 가끔 다른 경우에는 더 빠른 탐색 알고리즘을 요구한다. 예로 전화번호로 주소를 확인하는 긴급 출동 시스템에서는 선형, 이진 탐색보다 더 빠른 탐색 알고리즘은 필수적일 것이다. 이러한 경우에 필요한 탐색 알고리즘이 바로 해싱(Hashing)이다. 해싱은 O(1)의 시간 안에 탐색을 끝마칠 수도 있다.
해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하다. 이렇게 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라고 하고, 해시 테이블을 이용한 탐색을 해싱(Hashing)이라고 한다. 해싱을 일상생활에서 비유하자면 정리정돈과 비슷하다고 할수 있다. 물건을 정리하는 사람은 각 물건마다 고유한 위치가 있고 그 위치에 물건을 정리한다. 또 어떤 물건이 필요하다 싶으면 해당 위치에 찾아가서 물건을 가져온다. 이런 점이 해싱과 비슷하다고 할 수 있다. 해싱은 보통 "사전"이라는 자료 구조를 구현할 때에 가장 좋다. 예로 영어 사전의 경우, 영단어가 키(key)가 되고 단어에 대한 설명이 값이 된다.
해싱은 자료 저장에 배열을 사용한다. 해싱은 다른 요소들에 접근할 필요없이 원하는 항목의 키만을 가지고 배열의 인덱스를 결정하므로 배열이 가장 최적이다.
해쉬 테이블 구조
해시 함수
- 충돌이 적어야 한다.
- 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포 되어야 한다.
- 계산이 빨라야 한다.
1. 제산 함수
나머지 연산자(mod)를 이용하여 키를 테이블의 크기로 나눈 나머지를 주소로 사용. -> 가장 일반적임.
2. 폴딩 함수
키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용된다. 키를 여러 부분으로 나누어 모두 더한 값을 주소로 사용한다. 키를 나누고 더하는 방법에는 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 대표적.
1. 이동 폴딩 : 키를 여러 부분으로 나눈 값들을 더하여 사용
2. 경계 폴딩 : 키의 이웃한 부분을 더하여 주소를 얻는다.
3. 중간 제곱 함수
키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 비교적 고르게 주소가 분산된다.
4. 비트 추출 방법
테이블의 크기가 2의 제곱일 때 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용한다. 이 방법은 키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 높다.
5. 숫자 분석 방법
숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용하다. 예를 들어, 1712345가 학생의 학번이라 하면 앞의 17은 입학년도를 의미하므로 가급적 사용하지 않고 나머지 수를 조합하여 해시 주소로 사용하는 것이다.
6. 탐색키가 문자열일 경우 주의할 점
문자열일 경우 해시 주소를 만들 경우 가장 간단한 방법은 아스키 코드값을 주소로 사용하는 것이다. 그러나 'cup'과 'car'는 구별이 불가능하므로 충돌을 막기 위해서는 문자열안의 모든 문자를 골고루 사용하는 것이 가장 좋다. 그러나 이 방법 또한 문자열안의 문자들이 모두 동일한 문자로 이루어져 있을 경우 구분하기 힘들다. 이러한 충돌을 없애기 위해 글자들의 아스키 코드 값에 위치에 기초한 값을 곱하는 것이다.
충돌 대처
1. 선형 조사법(Linear Probing)
특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾아 항목을 저장하는 방법이다. 만약 hashtable[i]에서 충돌이 발생했다면 hashtable[i+1]로 가서 비어있는지 보고 비어있으면 항목을 넣고 비어있지 않으면 또 다시 i+2가 되서 빈 상태인지 확인을 반복한다. 이럼에도 아무 곳에도 빈 곳이 없다면 table resizing을 통해 해시 테이블 크기를 늘려서 이미 존재하는 데이터들을 재 정렬하고 기존에 넣을 곳을 찾고 있었던 데이터를 가지고 빈 공간을 계속 찾는 작업을 한다.
코드 ( 대학교수님의 수업 자료 )
#define _CRT_SECURE_NO_WARNINGS
#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)
{
const 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;
}
2. 체이닝(Chaining)
선형 조사법이 탐색 시간이 많이 걸리는 이유는 충돌 때문에 해시 주소가 다른 키하고도 비교를 해야 하는데에 있다. 체이닝은 이러한 오버플로우를 리스트로 구현함으로써 해결한다. 리스트는 크기를 예측할 수 없으므로 연결리스트로 구현한다. 물론 버킷 내에서 원하는 항목을 찾을 경우 연결 리스트를 순차 탐색한다.
