효율적인 데이터 관리를 위해, 데이터를 고정된 길이의 데이터로 바꾸어 저장하는 것
- 키에 산술 연산을 적용하여 나온 결과를 주소로 하여 값에 접근하는 방법
- 해시 테이블을 이용한 탐색
- 키와 값을 매핑시키는 과정
해시함수를 사용하여 키를 해시값으로 변환하고, 이 해시값을 인덱스로 하여 데이터를 키와 함께 저장하는 자료구조
- m개의 버킷(bucket)으로 이루어져 있으며, 하나의 버킷은 s개의 슬롯(slot)을 가질 수 있다.
- 자료를 저장하는데 배열을 사용한다.
키값을 고정된 길이의 해시로 변경해주는 함수
-
키값을 그대로 저장소의 색인으로 사용할 경우 키의 길이만큼의 정보를 저장할 공간도 마련해야하기 때문에, 고정된 길이의 해시로 변경한다.
-
좋은 해시함수의 조건
- 충돌 확률이 적은 함수
- 값을 테이블 내에 고르게 분포할 수 있는 함수
- 계산이 빠른 함수
서로 다른 키가 해싱 후 같은 해시 주소를 가지는 현상
- 해시 충돌이 빈번히 일어나서 빈 버킷이 남지 않으면 오버플로우가 일어난다 -> 해시테이블에 값을 저장할 수 없게 된다.
- 해시 충돌을 줄이는 것이 아주 중요
-
원하는 항목이 들어 있는 위치를 알고 있다면 매우 빠르게 자료에 접근 가능하다.
->이상적인 해싱의 경우, O(1)의 시간복잡도를 가진다.
-
키와 값 사이에 연관성이 없어 보안에도 많이 사용된다.
- 데이터가 저장되기 전에 미리 공간을 만들어놔야하기 때문에 공간 효율성이 떨어진다.
- 충돌이 일어날 경우버킷 내부의 순차탐색 시간이 길어져 탐색 성능이 저하될 수 있다.
- 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하게 되면 오버플로우가 발생한다.
-
키와 값의 모든 경우의 수를 버킷으로 가지고 있는 경우
-> 해시 함수를 계산하는 시간만 필요로한다. ( 추가적인 배열 탐색이 필요없다.)
- 해시 테이블의 크기가 제한되어 있기 때문에, 하나의 키당 하나의 공간을 할당하는 것은 불가능하다.
- 공간 낭비를 고려하여, 실제로는 더 작은 해시테이블을 만들어주는 해시함수를 이용한다. -> 충돌이 일어나는 이유
- 실제의 해싱의 경우 오버플로우가 자주 발생하기 때문에 시간복잡도가 O(1)보다 떨어진다.
-
개방 주소법(open addressing): 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장하는 방법. 비어있는 버킷을 찾는다.
-
선형 조사법: 충돌이 일어난 버킷의 다음 버킷이 비어있는지 확인하는 방법
- h(k), h(k)+1, h(k)+2 ... 순으로 탐색
- 조사를 시작했던 곳으로 되돌아올 때까지 확인을 계속한다.
- 키들이 집중되어 저장되는 현상이 자주 발생하며, 최악의 경우 집중된 항ㅁ고이 결합하는 현상도 발생한다.
- 오버플로우가 자주 발생하면 집중과 결합에 의해 탐색 효율이 크게 저하된다.
//선형 조사법을 이용하여 테이블에 키 삽입. 테이블이 가득 찼을 경우 종료 #define empty(item) (strlen(item.key==0)) #define equal(item1, item2) (!strcmp(item1.key, item2.key)) void hash_lp_add(element item, emelent ht[]) { int i, hash_value; hash_value=i=hash_function(item.key); 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; } -
이차 조사법:
(h(k)+inc*inc)mod M for inc=0, 1, ..., M-1의 식을 통해 다음 조사 위치를 결정하는 방법- h(k), h(k)+1, h(k)+4, h(k)+9 ... 순으로 탐색
- 선형 조사법의 집중과 결함을 크게 완화시킬 수 있다.
void hash_qp_add(element item, emelent ht[]) { int i, hash_value, inc=0; hash_value=i=hash_function(item.key); 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){ fprintln(stderr, "테이블이 가득찼습니다.\n"); exit(1); } } ht[i]=item; } -
이중 해싱법(재해싱): 원래의 해시함수와 다른 별개의 해시 함수를 이용해 다음 위치를 정하는 방법
-
h(k), h(k)+h'(k), h(k)+2*h'(k) ... 순으로 탐색. (여기서 h'(k)=C-(k mod C), C는 테이블 크기보다 약간 작은 소수)
-
다른 방법들보다 테이블에 값을 균일하게 분포시킬 수 있어 효과적이다.
->충돌이 발생했을 때 해시값에 일정 값을 더하는 다른 방법들은 조사 위치가 항상 일정한 것에 반해 키를 참조하여 값을 더하는 이중해싱법은 조사 순서가 달라지기 때문.
void hash_dh_add(element item, emelent ht[]) { int i, hash_value, inc; hash_value=i=hash_function(item.key); inc=hash_function2(item.key); while(!empty(ht[i])){ if(equal(item, ht[i])){ fprintf(stderr, "탐색키가 중복되었습니다.\n"); exit(1); } i=(i+inc)%TABLE_SIZE; if(i==hash_value){ fprintln(stderr, "테이블이 가득찼습니다.\n"); exit(1); } } ht[i]=item; } -
-
-
체이닝(chaining): 해시테이블 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경하는 방법.
- 충돌이 발생하면 새로운 노드를 생성하여 저장한다.
typedef struct{ int key; } element; struct list{ element item; struct list *link; }; struct list *hash_table[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; }