선형탐색, 이진 탐색은 모두 키값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 그렇다면 O(1)만큼 더 빠른 검색,탐색 방법은 없을까?
해싱 : 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하다.
해시 테이블 : 키에 대한 연산에 의해 직접 접근이 가능한 구조
해싱은 해시 테이블을 이용한 탐색이다.
이해하기 어려우면 예를 살펴보자.
정리 정돈을 잘하는 사람은 물건들을 항상 제자리에 둔다. 열쇠는 항색 책상 위에 두는 식처럼 열쇠가 필요하면 바로 그 위치를 찾아가면 되는 느낌이다.
사전(dictionary) - map, table
사전은 (키, 값) 쌍의 집합이다.
-
키(key) : 사전의 단어처럼 항목과 항목을 구별시켜주는 것 - 영어 단어
-
값(value) : 단어의 설명에 해당한다. - 단어의 뜻,설명
물론 리스트에도 키를 같이 넣어서 저장할 수 있겠지만 근본적으로 위치에 의하여 관리되는 자료 구조이다. 반면 사전은 오직 키에 의해서만 관리된다.
사전 추상형 자료형
- 객체 : 일련의 (key, value) 쌍의 집합
- 연산 :
- add(key, value) -> (key, value)를 사전에 추가한다.
- delete(key) -> key에 해당되는 (key, value)를 찾아서 삭제한다. 관련된 value를 반환하고 만약에 탐색에 실패하면 NULL를 반환한다.
- search(key) -> key에 해당되는 value를 찾아서 반환한다. 만약 탐색이 실패하면 NULL를 반환한다.
해싱의 구조
해시 함수 : 키를 입력을 받아 해시 주소를 생성하고 이 해시 주소를 해시 테이블의 인덱스로 사용한다.
이 배열의 인덱스 위치에 자료를 저장할 수도 잇고 거기에 자장된 자료를 꺼낼 수 도 있다.
해시 테이블에 존재하는 버킷의 수가 M일때 -> 모든 키에 대하여
서로 다른 두 개의 키 k1, k2에 의하여 h(k1) = h(k2)인 경우 -> 충돌
충돌이 발생하면 같은 버킷에 있는 다른 슬롯에 항목을 저장하게 되고, 버킷 내부에서의 순차 탐색 시간이 길어져서 탐색 성능이 저하될 수 있음.
충돌이 버킷에 할당된 슬롯 수보다 많이 발생하게 되면 더이상 항목을 저장할 수 없게 되는 오버플로우가 발생하게 된다.
해시 함수
해싱에서는 키값을 해시테이블의 주소로 변환하는 해시 함수가 잘 설계되어야만 탐색의 효율이 증되된다.
- 충돌이 적어야 한다.
- 해시함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
- 계산이 빨라야한다.
제산 함수
= k mod M
여기서 M은 해시 테이블의 크기로서 해시 함수의 값의 범위는 0~(m-1)이 된다.
왜 M의 선택이 중요할까?
M이 짝수라면 .. 메모리의 주소는 보통 2의 배수임으로 해시 주소가 한쪽으로 편향된다면 해시 테이블을 골고루 사용하지 않는 것이 되서 이는 결과적으로 좋지 않다. 따라서 테이블의 크기인 M은 항상 홀수여야한다. 일반적인 이상적인 값은 소수이며 결과적으로 0~(m-1)을 골고루 사용하는 값을 만들어낸다.
만약 나머지 연산을 수행했을 때 음수가 나올 가능성도 있으므로 M을 더해서 결과값이 항상 0~(m-1)이 되도록 하여야한다.
int hash_function(int key)
{
int hash_index = key % M;
if(hash_index < 0)
hash_index += M;
return hash_index;
}-
중간 제곱 함수
키를 제곱한 다음, 중간의 몇 비트를 취해서 해쉬 주소를 생성한다. -
비트 추출 방법
해시 테이블의 크기가 일때 키를 이진수로 간주하여 임이의 위치에 k개의 비트를 해시 주소로 사용하는것. -
숫자 분석 방법
키의 각각의 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법 -
탐색키가 문자열일 경우
보편적인 방법은 각 문자의 아스키 코드값을 모두 더하는 것인데 "cup", "puc"같은 키들은 구분할 수 없기에 더 좋은 방법은 글자들의 아스키 코드 값에 위치에 기초한 값을 곱하는 것이다.
int hash_function(char *key)
{
int hash_index = 0;
while(*key) // '/0'일때까지 반복
hash_index = g * hash_index + *key++; // 문자열을 아스키코드값으로 변환해서 더하고 다음 문자열로 이동
return hash_index;
}오버 플로우를 효과적으로 해결하는 방법
- 개방 주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다.
- 체이닝 : 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다.
개방 주소법 - 선형조사법
선형 조사법에서는 만약 충돌이 ht[k]에서 충돌이 발생했다면 ht[k+1], ht[k+2], ht[k+3]...이 비어 있는지를 살펴본다. 이런 식으로 비어있는 공간이 나올 때까지 계속하여 조사하는 방법이다.
선형 조사법의 구현
#define KEY_SIZE 10
#define TABLE_SIZE 13
typedef struct
{
char key[KEY_SIZE];
// 다른 필요한 필드들
}element;
element hash_table[TABLE_SIZE]; //해싱 테이블해시 테이블의 각 요소들은 초기화 과정을 거쳐야 한다. 각 버킷들을 공백상태로 만드는것!! 문자열이 키이므로 키의 첫 번째 문자가 NULL값이면 버킷이 비어있다는 것으로 생각한다.
void init_table(element ht[])
{
int i;
for(int i = 0; i < TABLE_SIZE; i++) {
ht[i].key[0] = NULL:
}
}해시 테이블에 키를 삽입하기 위해서는 먼저 키를 정수로 바꾸어주는 해시 함수가 필요하다.
문자열을 먼저 정수로 바꾸고 여기에 다시 제산함수를 적용시켰다.
// 문자로 된 키를 숫자로 변환
int transform(char * key)
{
int number = 0;
while ( *key)
number = number + *key++; // 문자열의 각 아스키 코드를 더함
return number;
}삽입함수에서는 먼저 키에 대한 해시 주소를 계산한다. 주소가 비어 있는지를 검사해서 비어 있지 않으면 먼저 그 주소에 저장된 키와 현재 삽입하려고 하는 키가 동일한지를 체크한다. 동일하면 키가 중복되었다는 것을 출력하고 복귀한다. 키가 중복되지 않았다면 i를 증가하여 다음 버킷을 가르키도록 한다. 증가된 주소가 만약 시작 주소로 되돌아온 경우에는 더 이상 삽입이 불가능한 오류 상태임을 알리고 복귀한다.
#define empty(item) (strlen(item.key) == 0) //현제 버킷이 비어있는지를 검사
#define equal(item1, item2) (!strcmp(item1.key, item2.key)) //두 개의 항목이 동일한지 검사
// 선형 조사법을 이용하여 테이블에 키를 삽입하고,
// 테이블이 가득 찬 경우는 종료
void hasg_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 hasg_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, "탐색 %s\n: 위치 = %d\n", item.key, i);
return;
}
i = (i+1) % TABLE_SIZE ; // 버킷이동
if( i == hash_value) { // 시작 주소로 되돌아온 경우 탐색 실패
fprintf(stderr, "찾는 값이 테이블에 없음.\n");
return;
}
}
fprintf(stderr, "찾는 값이 테이블에 없음\n");
}전체 프로그램
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#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;
}선형 조사법은 간단하다는 장점이 잇으나, 오버플로우가 자주 발생하면 집중과 결합에 의해 탐색의 효율이 크게 저하될 수 있다.
개방 주소법 - 이차 조사법
선형 조사법과 유사하지만, 다음 조사할 위치의 식이 조금 다르다. 집중과 결합을 크게 완화시킬 수 있지만 동일한 위치로 사상되는 여러 키들이 같은 순서에 의하여 빈 버킷을 조사하기 때문에 2차 집중 문제를 일으킬 수 있다. 이 문제는 이중 해싱법으로 해결 할 수 있다.
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;
}개방주소법 - 이중 해싱법
오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. 이중 해싱법에서는 키를 참조하여 더해지는 값이 결정된다. 따라서 해시 함수값이 같더라도 키가 다르면 서로 다른 조사 순서를 갖는다. --> 2차 집중을 피할 수 있다.
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;
}선형 조사법의 문제점은 한 번도 사용되지 않은 위치가 있어야 만이 탐색이 빨리 끝나게 된다는 것. 만약 거의 모든 위치가 사용되고 있거나 사용된 적이 있는 위치라면 실패하는 탐색인 경우 테이블의 거의 모든 위치를 조사해야 한다. 체이닝은 이러한 문제를 보안했다.
체이닝
오버플로우 문제를 연결 리스트로 해결한다. 즉 버킷에 고정된 슬롯을 할당하는 것이 아니라 각 버킷에, 삽입과 삭제가 용이한 연결 리스트를 할당한다.
체인법 구현
#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;
}
전체 프로그램
#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;
}해시 테이블을 연결 리스트로 구성하므로 필요한 만큼의 메모리만 사용하게 되어 공간적 사용 효율이 매우 우수하다. 또한 오버플로우가 발생하더라도 해당 버켓이 할당된 연결 리스트만 처리하게 되므로 수행 시간 면에서도 매우 효율적이다.
추가함수 - 체인법 삭제 함수
void hash_chain_delete(element item, struct list* ht[])
{
struct list* node;
int hash_value = hash_function(item.key);
struct list* node_before = NULL;
if (ht[hash_value]->item.key == item.key) { // 첫 노드가 삭제할 노드일때
ht[hash_value] = ht[hash_value]->link;
return;
}
for (node = ht[hash_value]; node; node_before = node, node = node->link) {
if (node->item.key == item.key) {
if (node->link == NULL) { // 마지막 노드가 삭제할 노드일때
node_before->link = NULL;
free(node);
return;
}
else { // 중간 노드가 삭제할 노드일때
node_before->link = node->link;
free(node);
return;
}
}
}
}
포인터의 위치만 바까주면 탐색 후 간단하게 삭제할 수 있다.
