2021.06.16 - [이론공부/자료구조] - 자료구조 공부 #22 (정렬)
해싱(Hahing)
- 일반적 탐색 : 대부분의 탐색 방법들은 키 값 비교로 탐색하고자 하는 항목에 접근을 한다.
- 해싱 : 키 값에 대한 산술적 연산에 의해 테이블 주소를 계산하여 항목에 접근하는 방법
- 해시 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 구조ㅎ
추상 자료형 사전 구조
- 사전 구조(Dictionary)
- (키, 값) 쌍의 집합
- 키와 관련된 값을 동시에 저장하는 자료구조
- 맵(Map) 또는 테이블(Table)로 불리우고 있다
- 탐색 키와 관련된 값의 2가지 필드로 구성
- 탐색 키(search key) : 사전의 단어처럼 항목과 항목을 구별 시켜주는 것
- 값(value) : 단어의 설명에 해당
해싱의 구조
- 해시 함수(hash function)
- 탐색키를 입력받아 해시 주소(hash address) 생성
- 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스
해시 테이블(hash table) 구조
화일 구조 시간에 배우는 해싱관련 내용도 비슷하게 다루니 확실히 이해해 두자
이상적인 해싱
- 학생 정보를 해싱으로 저장, 탐색 한다 가정할 때
- 5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호
- 같은 학과 학생들만 가정하면 뒤에 3자리만 사용해서 탐색 가능
- 학번이 01023이라면 h(01023) = 23 이므로, 이 학생의 인적사항은 해시테이블 ht[23]에 저장
- 만약 해시 테이블이 1000개의 공간을 가지고 있다면, 이 때 탐색 시간이 O(1)이 되므로 이상적임
- 즉, 함수 계산 시간만 필요하고 저장이나, 탐색에는 동일한 시간이 걸림
실제의 해싱
- 실제로는 해시 테이블의 크기가 제한되므로, 존재 가능한 모든 키에 대해 저장 공간을 할당하기 어렵다.
- h(k) = k mod M 의 예에서 보듯 필연적으로 충돌과 오버플로우가 발생 함
실제 해싱에서는 충돌과 오버플로우가 빈번하게 발생하므로 시간 복잡도는 이상적인 경우의 O(1)과는 거리가 멀다.
해시 함수
- 좋은 해시 함수의 조건
- 충돌이 적어야 한다
- 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포 되어야 한다
- 계산이 빨라야 한다
해시함수의 종류
- 제산 함수
- h(k) = k mod M
- 해시 테이블의 크기 M은 소수(prime number) 선택
- 폴딩 함수
- 주로 키가 해시 테이블 크기보다 더큰 정수일 경우 사용
- 키를 여러부분으로 나누어 더하는 방법으로 해시 값 생성
- 이동폴딩(shift folding)과 경계 폴딩(boundary folding)
- 중간 제곱 함수
- 탐색 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소 생성
- 비트 추출 함수
- ht 크기가 M=2^k 일때, 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시주소로 사용
- 숫자 분석 방법
- 키 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합하게 조합하여 사용
개방 주소법
- 충돌(collision)
- 서로 다른 탐색 키를 갖는 항복들이 같은 해시 주소를 가지는 현상
- 충돌이 발생하면 해시 테이블에 항목 저장이 불가능
- 충돌을 효과적으로 해결하는 방법이 반드시 필요
- 충돌 해결책
- 개방주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
- 선형 조사법, 이차 조사법, 이중 해싱법, 임의 조사법 - 체이닝 : 각 버켓마다 삽입과 삭제가 용이한 연결리스트를 할당
- 개방주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
선형 조사법
- 개방주소법 : 특정 버킷에서 충돌이 발생하면, 비어 있는 버킷을 찾는 방법
- 충돌이 ht[k]에서 발생 했다면,
- ht[k+1]이 비어 있는지 조사
- 만약 비어있지 않다면 ht[k+2] 조사
- 비어있는 공간이 나올 때까지 계속 조사
- 테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사
- 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬것임
- 조사되는 위치 : h(k), h(k)+1, h(k)+2, .....
- 군집화(clustering) 결합(coalescing) 문제 발생
선형 조사법 C++ 구현
더보기
#define KEY_SIZE10 // 탐색키의최대길이
#define TABLE_SIZE13// 해싱테이블의크기=소수
typedefstruct {
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 transform(char *key) {
int number = 0;
while (*key)number = 31 * 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[]) {
inti, 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[]) {
inti, 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 (inti= 0; i< 7; i++) {
strcpy(e.key, s[i]);
hash_lp_add(e, hash_table);
hash_lp_print(hash_table);
}
for (inti= 0; i< 7; i++) {
strcpy(e.key, s[i]);
hash_lp_search(e, hash_table);
}return 0;
}
삽입에는 문제가 없지만 삭제시에 문제가 발생할 수 있다. 버킷 분류가 필요함
15 삭제후 25 삭제시에 중간에 비어있는것을 분류하지 않을시 더이상 삭제를 위한 탐색을 진행 안함
이차 조사법
이중 해싱법
체이닝(chaining)
- 오버플로우 문제를 연결 리스트로 해결
- 각 버켓에 고정된 슬롯이 할당되어 있지 않음
- 각 버켓에, 삽입과 삭제가 용이한 연결 리스트 할당
- 버킷 내에서는 연결 리스트 순차 탐색
체이닝 C++ 구현
더보기
// 제산함수를사용한해싱함수
inthash_function(intkey) {
return key % TABLE_SIZE;
}
// 체이닝이용하여테이블에키를삽입
void hash_chain_add(element item, structlist *ht[]) {
inthash_value= hash_function(item.key);
structlist *ptr;
structlist *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= (structlist *)malloc(sizeof(structlist));
ptr->item = item;
ptr->link = NULL;
if (node_before)node_before->link = ptr;
elseht[hash_value] = ptr;
}
// 체이닝을이용하여테이블에저장된키를탐색
void hash_chain_search(element item, structlist *ht[]) {
structlist *node;
inthash_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");
}
#define SIZE 5
int main(void) {
intdata[SIZE] = { 8, 1, 9, 6, 13 };
element e;
for (inti= 0; i< SIZE; i++) {
e.key= data[i];
hash_chain_add(e, hash_table);
hash_chain_print(hash_table);
}
for (inti= 0; i< SIZE; i++) {
e.key= data[i];
hash_chain_search(e, hash_table);
}
return 0;
}
해싱 성능 분석
해싱과 다른 탐색방법의 비교
전체적으로 해싱의 방법이 탐색에서 제일 무난한 방법이다. (어떻게 해싱함수를 적용하는데 따라 다르겠지만..)
자료구조는 정말 중요한 내용이다... 수업시간 내내 교수님도 그렇고 학교에 행사에 참여할때 마다 지겹도록 듣는 필수 이론이 자료구조이다.. 완벽하게 내가 수업을 이해한건 아니겠지만 어느정도 정리해서 이렇게 적어놓았으니 필요할때마다 찾아서 다시 읽고, 수정하는 절차가 필요할거 같다