해싱(hashing)?
해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다.
슬롯이 한개일 경우 무조건 충돌이 일어나며 우리는 충돌은 피할 수 없으므로 최대한 적게 일어나는 쪽으로 설계 해야 한다.
슬롯이 한개일 경우에는 오버플로우와 충돌은 같다.
Hashing Fuction( h(x) ) 를 통해 해시테이블에 파싱해줘야하는데 입력값을 해시테이블 크기만큼 나눈 나머지에 파싱된다.
h(k) = k mod D
k : 입력값 D: 해시테이블 크기
오버플로우 핸들링(Overflow Handling)
대표적으로 두가지 오버플로우 핸들링이 있는데 Open addressing(개방 주소법) 과 Chaining(체인법) 이 있다.
Open addressing 은 다시 4가지 방법들이 있는데 Linear Probing(선형조사법) , Quadratic Probing(이차 조사법) , Rehashing(재해싱), Random Probing (임의 조사법) 등이 있으며, Linear probing(선형 조사법)을 알아볼 것이다.
선형 조사법 (Linear Probing)
선형 조사법에서는 키 값이 k인 새로운 쌍 하나를 삽입할 때 ht[h(k)+i]%b의 순서에 따라 해시 테이블 버킷을 검색한다. 여기서 h는 해시 함수이고 b는 버킷의 수이며 0<=i<=b-1 이다. 다 채워지지 않은 버킷을 만나면 검색이 끝나고 새로운 쌍이 그 버킷으로 삽입된다. 빈 자리가 있는 버킷이 없다면 해시 테이블이 만원이라는 뜻이므로 테이블 크기를 늘러야 한다.
쉽게 정리 하면
1.) h(k)를 계산한다.
2.) 다음과 같은 경우 중 어느 하나가 발생할 때까지 ht[h(k),ht[h(k)+1)%b],..,ht[h(k)+j)%b]의 순서로 해시 테이블 버킷을 조사한다.
(a) 버킷 (ht[h(k)+j)%b]에 값이 k인 키 쌍이 있는 경우; 이 경우 원하는 쌍이 발견되었음.
(b) ht[h(k)+j]가 비어 있는 경우; k는 테이블에 없음.
(c) 시작 위치 ht[h(k)]로 돌아온 경우; 테이블은 만원이고 k 는 테이블에 없음.
문제 예시
1. 다음을 만족하는 Hash를 구현하라
1) 입력 데이터는 다음과 같은 형식을 가지는 파일(input.txt)로부터 입력받는다.
D N M K 1 K 2 K 3 … K N
S 1 S 2 … S M
D: Hash Table의 크기이다. Ki 는 Hash의 입력 데이터로 양수이며 Si 는 Hash에 해당 키가 있는지 찾기 위한 양수이다. 단 D, N, M≤1000이다.
2) 주어진 Ki 를 차례대로 Hash Table에 저장하고, 최종 완성된 Hash Table을 출력한다.
단, Hash Table이 가득찰 경우는 없다고 가정한다 (D>N).
3) Hash function으로 Division을 사용한다.
4) Overflow Handling으로 Linear Probing을 사용한다.
5) 주어진 Si 를 Hash Table에서 찾아서 찾았으면 S, 못찾았으면 F를 차례대로 출력한다.
예시
input.txt
10 6 3
8 15 91 2 88 41
4 41 15
코드
/*
Description : 해시 테이블 - 선형 조사법(linear hashing 구현
*/
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
typedef struct element
{
int key;
int empty;
}element;
void open();
void COLOR(int);
void InitTable(element *ht);
int hash_Function(int key); //h(x)
int hash_Insert(element item, element *ht);
int HashSearch(element item, element *ht);
element item;
element *hash_table;
int *find;
int D, M, N;
int main(void)
{
open();
element linear;
COLOR(15);
for (int i = 0; i < D; i++) {
if (hash_table[i].key == 0)
printf("%d: \n",i);
else
printf("%d: %d\n", i, hash_table[i].key);
}
COLOR(14);
printf("\nSearch :\n");
COLOR(15);
for (int i = 0; i < N; i++)
{
linear.key = find[i];
HashSearch(linear, hash_table);
}
printf("\n");
return 0;
}
void open() //파일오픈
{
FILE *fp = fopen("input.txt", "r");
fscanf(fp, "%d %d %d", &D, &M, &N);
hash_table = (element*)malloc(sizeof(element) * D);
find = (int*)malloc(sizeof(int)*N);
InitTable(hash_table);
for (int i = 0; i < M; i++) {
fscanf(fp, "%d\n", &item.key);
hash_Insert(item, hash_table);
}
for (int i = 0; i<N; i++)
fscanf(fp, "%d", &find[i]);
fclose(fp);
}
void COLOR(int color)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
void InitTable(element *ht) // 해시테이블 초기화
{
int i;
for (i = 0; i < D; i++)
{
memset(&ht[i].key, 0, sizeof(ht[i].key));
ht[i].empty = -1;
}
}
int hash_Function(int key) //h(x)
{
return key % D;
}
int hash_Insert(element item, element *ht)
{
int i, value;
value = i = hash_Function(item.key);
while (ht[i].empty == 1)
{
if (item.key == ht[i].key)
{
return;
}
i = (i + 1) % D; //충돌일어나면 그다음 테이블에 삽입
if (i == value)
return ;
}
item.empty = 1;
ht[i] = item;
}
int HashSearch(element item, element *ht) // 키 탐색
{
int i, value;
value = i = hash_Function(item.key);
while (!(ht[i].empty == -1)) // 버켓이 비어있지 않다면
{
if (item.key == ht[i].key)
{
printf("S ");
return ;
}
i = (i + 1) % D; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.
if (i == value)
{
return ;
}
}
printf("F ");
return ;
}출력값
단점
클러스터 확장현상이 있음