자료구조 :: 해싱(4) 충돌 해결책 - 체이닝

# 체이닝(chaining)

체이닝은 오버플로우 문제를 해시테이블의 구조변경을 통해 연결리스트로 해결하는 방법이다. 즉, 각 버켓에
고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가 용이한 연결리스트를 할당한다. 버켓 내에서는
원하는 항목을 찾을때 연결리스트를 순차 탐색하면 된다.

해시테이블은 한개의 노드를 가리킬수 있는 포인터 배열로 선언하고, 탐색 키가 버켓으로 들어올 경우 먼저
동적으로 메모리를 할당하여 연결리스트의 노드를 생성한 다음, 이 새로운 노드에 탐색키를 복사한다.
다음 단계로 버켓에 연결되어 있는 기존의 연결리스트에서 동일한 탐색 키가 있는지를 검사한다.
만약 동일한 탐색 키가 발견되면 오류 메시지를 출력하고 복귀한다. 동일한 탐색 키가 없으면 연결리스트의
맨 끝에 새로운 탐색키를 포함하는 새로운 노드를 연결한다. 만약 기존의 연결리스트가 없으면 해시테이블의
포인터에 새로운 노드를 연결한다.

체이닝에서 항목을 탐색하거나 삽입하고자 하면 키 값의 버켓에 해당하는 연결리스트에서 독립적으로 탐색이나
삽입이 이루어진다. 체이닝은 해시 테이블을 연결리스트로 구성하므로 필요한 만큼의 메모리만 사용하게 되어
공간적 사용 효율이 매우 우수하다. 또한 오버플로우가 발생할 경우에도 해당 버켓에 할당된 연결리스트만 처리
하게 되므로 수행 시간면에서도 매우 효율적이다.

[체이닝을 이용한 해싱]

Hash_Chaining.cpp

#include <string.h> 

#include <stdio.h> 
#include <stdlib.h> 

#define KEY_SIZE    10// 탐색키의 최대길이 
#define TABLE_SIZE    13// 해싱 테이블의 크기=소수 
#define equal(e1,e2) (!strcmp(e1.key,e2.key)) // 문자열 비교

typedefstruct
{    
char key[KEY_SIZE];     
} element; 

typedefstruct list 
{    
    element item; 
    list *link; 
}list; 
list *hash_table[TABLE_SIZE]; 


// 문자로 된 탐색키를 숫자로 변환
int transform(char *key) 
{ 
int number=0; 
// 간단한 덧셈 방식 사용 자연수 생성
while(*key) 
        number += *key++; 
return number; 
} 

// 제산 함수를 사용한 해싱 함수
int hash_function(char *key) 
{ 
// 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
return transform(key) % TABLE_SIZE; 
}  

// 체인법을 이용하여 테이블에 키를 삽입
void hash_chain_add(element item, list *ht[]) 
{ 
int hash_value = hash_function(item.key); 
   list *ptr;  
   list *node_before=NULL, *node = ht[hash_value]; 
for(; node; node_before=node, node=node->link){   
if(equal(node->item, item)){   
         fprintf(stderr,"이미 탐색키가 저장되어 있음\n"); 
return; 
      } 
   } 
   ptr = (list *)malloc(sizeof(list)); 
   ptr->item = item; 
   ptr->link = NULL; 
if(node_before) 
      node_before->link = ptr; 
else
      ht[hash_value] = ptr;  
} 

// 체인법을 이용하여 테이블에 저장된 키를 탐색
void hash_chain_find(element item,list *ht[]) 
{ 
   list *node; 

int hash_value = hash_function(item.key); 
for(node=ht[hash_value]; node; node=node->link){   
if(!strcmp(node->item.key, item.key)){   
        printf("키를 찾았음\n"); 
return; 
      } 
   } 
   printf("키를 찾지못했음\n"); 
} 

// 연결리스트 삭제 함수
void hash_chain_delete(element item,list *ht[]) 
{ 
   list *node; 
   list *before_node=NULL; 
int hash_value = hash_function(item.key); 

for(node=ht[hash_value];node;before_node=node,node=node->link) 
   {   
if(!strcmp(node->item.key, item.key)) 
      { 
if(node->link != NULL) 
             before_node->link=node->link; // 다음 노드를 연결

          free(node); 
          printf("삭제 완료"); 
return ; 
      } 

    } 
   printf("키를 찾지못했음\n"); 
} 

// 해싱 테이블의 내용을 출력
void hash_chain_print(list *ht[]) 
{ 
   list *node; 
int i; 
for(i=0;i<TABLE_SIZE;i++){ 
      printf("[%d]->",i); 
for(node=ht[i]; node; node=node->link){   
         printf("%s->", node->item.key); 
      } 
      printf("\n"); 
   } 
} 

// 해싱 테이블을 사용한 예제 
int main() 
{ 
    element tmp; 
int op; 
while(1){ 
        printf("원하는 연산을 입력하시오(0=입력, 1=삭제, 2=탐색, 3=종료)="); 
        scanf("%d",&op); 
if( op == 3 ) break; 
        printf("키를 입력하시오="); 
        scanf("%s",tmp.key); 
if( op == 0 ){ 
            hash_chain_add(tmp, hash_table); 
        } 
elseif( op == 1) 
        { 
            hash_chain_delete(tmp, hash_table); 
        } 
elseif( op == 2 ) 
        { 
            hash_chain_find(tmp, hash_table); 
        } 

        hash_chain_print(hash_table); 
    } 

return0; 
}