해싱(hashing)
- 키에 산술적인 연산을 적용하여 항목이 저장되어 잇는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라 부르며, 해시 테이블을 이용한 탐색을 해싱이라고 한다.
- key: 항목과 항목을 구별시켜 주는 것(사전의 단어 같은 것)
- value: 단어의 설명
- 해싱의 구조
> 현실적으로 탐색키들이 문자열이거나 매우 큰 숫자이기 때문에 탐색 키를 직접 배열의 인덱스로 사용하기에는 무리가 있다. 각 탐색 키를 작은 정수로 맵핑시키는 함수가 필요하다.
> 해싱에는 자료를 저장하는 배열을 사용한다. 배열은 단점도 있지만, 만약 원하는 항목이 들어 있는 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 배열의 다른 요소들에는 전혀 접근할 필요가 없다.
- 해싱이란 이런 식으로 어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정하는 기법이다.
- 해시함수는 키를 입력으로 받아 해시 주소를 생성하고 이 주소를 해시테이블의 인덱스로 사용한다. 배열의 인덱스 위치에 자료를 저장할 수도 있고 거기에 저장된 자료를 꺼낼 수도 있다.
> 해시테이블 ht는 M개의 버킷으로 이루어지는 테이블로서 ht[M-1]의 원소를 가진다. 하나의 버킷은 s개의 슬롯을 가질 수 있으며 하나의 항목이 저장된다. 하나의 버킷에 여러 개의 슬롯을 두는 이유는 서로 다른 두 개의 키가, 해시함수에 의해 동일한 해시주소로 변환될 수 있으므로 여러 개의 항목을 동일한 버킷에 저장하기 위함이다. 그러나 대부분의 경우 하나의 버킷은 하나의 슬롯을 가진다.
> 충돌이 버킷에 할당된 슬롯수보다 많이 발생하게 되면 버킷에 더이상 항목을 저장할 수 없게 되는 오버플로우가 발생한다. 만약 버킷 당 슬롯의 수가 하나이면 충돌이 곳 오버플로우를 의미한다.
해싱 알고리즘
add(key,value):
index <- hash_function(key)
ht[index] = value
search(key):
index <- hash_function(key)
return ht[index]
- 실제 해싱
> 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 키당 해시테이블에서 하나의 공간을 할당할 수 없다. 보통의 경우에 키는 매우 많고, 해시 테이블의 크기는 상당한 제약을 받는 것이 일반적이다.
> 일반적인 경우에는 키에 비해 해시 테이블의 크기가 작다. 그리고 키 중에 일부만 사용되기 때문에 전체를 위한 공간을 항상 준비할 필요는 없다. 따라서 더 작은 해시테이블을 사용하는 해시함수를 고안해야 한다
h(k)= k mod M -> 해시테이블의 크기로 나눠서 그 나머지를 해시 테이블의 주소로 하는 해시함수
- 실제의 해싱에서는 충돌과 오버플로우가 빈번하게 발생한다. 따라서 시간복잡도는 O(1)보다 낮다.
해시함수
- 해시 함수의 좋은 조건
- 충돌이 적다
- 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포된다
- 계산이 빨라야 한다
- 제산함수
> 제산함수는 나머지 연산자(mod)를 사용해서 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법이다
k (k) = k mod M
> M은 해시 테이블의 크기로서 해시 함수의 값의 범위는 0~(M-1)이 된다. 해시 테이블의 인덱스로 사용하기에는 이상적인 값이다. 이는 가장 일반적인 해시함수로서 해시 테이블의 크기 M은 주로 소수로 선택된다.
- 폴딩함수
> 폴딩함수는 주로 키가 해시테이블의 크기보다 더 큰 정수일 경우에 사용한다
hash_index=(short)(key^(key>>>16))> 폴딩 함수는 키를 여러 부분으로 나누어 모두 더한 값을 해시 주소로 사용한다. 키를 나누고 더하는 방법에는 이동폴딩과 경계폴딩이 대표적이다. 이동폴딩은 키를 여러 부분으로 나눈 값들을 더하여 해시 주소로 사용하고, 경계폴딩은 키의 이웃한 부분을 거꾸로 더하여 해시 주소를 얻는다
> 폴딩방법을 구현할 때 키 값을 해시 테이블 크기만큼 수를 가지는 부분으로 분할한 후 분할된 부분을 합하여 해시 주소를 만든다
- 중간제곱함수
> 중간 제곱함수는 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 제곱한 값의 중간 비트들은 대개 키의 모든 문자들과 관련이 있기 때문에 서로 다른 키는 몇 개의 문자가 같을 지라고 서로 다른 해싱 주소를 갖게 된다. 키 값을 제곱한 값의 중간 비트들의 값은 비교적 고르게 분산된다.
- 비트추출법
> 비트 추출방법은 해시 테이블의 크기가 M=2^k 일 때 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것이다. 이 방식은 간단하나 키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 높다
- 숫자 분석법
> 숫자 분석 방법은 숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용하다. 키의 각각의 위치에 있는 숫자 중에서 편중되지 않은 수들의 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법이다.
- 탐색키가 문자열인 경우
> 키들이 정수일 때는 비교적 쉽게 해시 주소로 변환이 가능했지만, 많은 경우 키들은 대게 문자열이었다. 따라서 문자열로부터 좋은 해시 주소를 생성하는 것이 중요하다. 대게 문자열 안의 문자에 정수를 할당하여 바꾸면 된다.
충돌(collsion) & 오버플로우
- 충돌이란 서로 다른 키를 갖는 항목들이 같은 해시 주소를 가지는 현상이다. 충돌이 발생하고, 해시 주소에 더 이상 빈 버킷이 남아있지 않으면 오버플로우가 발생한다. 오버플로우가 발생하면 해시테이블에 항목을 더 이상 저장하는 것이 불가능해진다.
> 오버플로우를 해결하는 방법
- 개방주소법: 충돌이 일어난 항목을 해시테이블의 다른 위치에 저장한다.
- 체이닝: 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다.
- 선형 조사법
> 개방 주소법은 특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾는 방법이다. 이 비어있는 버킷을 항목에 저장하게 된다. 해시테이블에서 비어있는 공간을 찾는 것을 조사(probling)이라고 한다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define KEY_SIZE 10 // 탐색키의 최대길이
#define TABLE_SIZE 13 // 해싱 테이블의 크기=소수
// 선형조사법 구현 #1
typedef struct
{
char key[KEY_SIZE];
} element;
element hash_table[TABLE_SIZE];
// 선형조사법 구현 #2
void init_table(element ht[])
{
int i;
for (i = 0; i<TABLE_SIZE; i++) {
ht[i].key[0] = NULL;
}
}
// 선형조사법 구현 #3
// 문자로 된 키를 숫자로 변환
int transform1(char *key)
{
int number = 0;
while (*key)
number = number + *key++;
return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char *key)
{
// 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
return transform1(key) % TABLE_SIZE;
}
// 선형조사법의 구현 #4
#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;
}
// 선형 조사법의 구현 #4.plus
// 선형조사법을 이용하여 테이블에 저장된 키를 탐색
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");
}
// 선형조사법의 구현 #5
// 해싱 테이블의 내용을 출력
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;
}
- 이차조사법
> 이차 조사법은 선형 조사법과 유사하지만 다음의 식에 의해 결정된다.
(h(k)+inc*inc) mod M for inc = 0, 1,.. , M-1
> 여기서 모든 위치를 조사하게 만들려면 테이블의 크기를 소수로 해야 한다. 이 방법은 선형 조사법에서의 문제점인 집중과 결합을 완화시킬 수 있다.
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;
}
- 이중해시법
> 이중해시법, 재해싱은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. 이 방법은 항목들을 해시 테이블에 보다 균일하게 분포시킬 수 있으니 효과적인 방법이라 할 수 있다.
> 선형 조사법과 이차 조사법은 충돌이 발생했을 경우에 해시 함숫값에 어떤 값을 더해서 다음위치를 얻는다. 선형 조사법에서 더해지는 값이 1이고 이차 조사법에서는 inc*inc가 된다. 따라서 해시 함숫값이 같으면 차후에 조사되는 위치도 같다.
void hash_dh_add(element item, element ht[])
{
int i, hash_value, inc;
hash_value = i = hash_function(item.key);
inc = hash_function2(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;
}
체이닝
> 선형조사법이 탐색 시간이 많이 걸리는 이유는 충돌 때문에 해시 주소가 다른 키 하고도 비교를 하는 데 있었다. 만약 해시 주소가 같은 키 만을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 된다. 리스트는 그 크기를 예측할 수 없으므로 연결 리스트로 구현하는 것이 가장 바람직하다.
> 충돌을 해결하는 다른 방법은 해시 테이블의 구조를 변경하여 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 것이다. 버킷은 여러 가지 방법으로 구현될 수 있다.
> 연결리스트의 어디에다 새로운 항목을 삽입할 것인가를 결졍해야 한다. 키들의 중복을 허용하지 않는다면 연결 리스트의 처음에다 삽입하는 것이 가장 능률적이다. 만약 중복이 허용되지 않는다면 연결 리스트를 처음부터 탐색해야 하므로 어차피 연결 리스트의 뒤로 가야 하고 이곳에다 삽입하는 것이 자연스럽다.
#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_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;
}
- 해싱의 응용
- 데이터베이스 인덱싱에 사용된다. 일부 데이터베이스 관리 시스템은 별도의 인덱스 파일을 사용한다. 데이터가 파일에서 추출되어야 할 때 탐색키는 먼저 인덱스 파일에서 검색되고, 검색 결과로부터 데이터베이스 파일에서의 정확한 위치를 알 수 있다. 인덱스 파일의 키정보는 종종 해시 테이블로 구현된다
- 해싱 기술은 컴파일러에서 심벌 테이블을 구현하는데 사용된다. 컴파일러는 소스 프로그램에서 사용자가 정의한 모든 심볼 기록을 유지하기 위해 심볼 테이블을 사용한다. 심볼 테이블에서 해싱을 사용하여 변수의 이름이나 함수의 이름을 빠르게 찾을 수 있다