자료구조 :: 해싱(2) 충돌 해결책 - 선형 조사법

# 충돌(collision)

충돌이란 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소를 가지는 현상이다.
일반적으로 충돌에 대해 제시할 수 있는 해결책으로는 다음과 같은 두 가지 방법이 있다.

(1) 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다.
(2) 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다.

# 선형 조사법(linear probing)

선형조사법은 특정 버켓에서 충돌이 발생하면 해시테이블에서 비어있는 버켓을 찾는 방법이다.
만약 ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어 있는지를 살펴보고 만약 비어 있지 않다면 h[k+2]를 살펴본다.
이런식으로 비어 있는 공간이 나올 때까지 계속 조사하는 방법이다. 만약 테이블의 끝에 도달하게 되면 다시
테이블의 처음으로 간다. 만약 조사를 시작했던 곳으로 다시 돌아오게 된다면 테이블이 가득찬 것으로 간주된다.

한번 충돌이 시작되면 그 위치에 항목들이 집중 되는 현상을 군집화(clustering)현상 이라고 한다.

[선형조사법을 이용한  데이터 삽입,삭제,탐색]

Hash_LinearPorbing.cpp

#include <stdio.h> 
#include <string.h> 

#define KEY_SIZE 10
#define TABLE_SIZE 13// 소수
#define MAX_STRING 30
typedefstruct
{ 
char name[MAX_STRING]; 
char phone[MAX_STRING]; 
int empty; 

}element; 
element hash_table[TABLE_SIZE]; 

void InitTable(element *ht) // 해시테이블 초기화
{ 
int i; 
for(i=0;i<TABLE_SIZE;i++) 
    { 
        memset(&ht[i].name,0,sizeof(ht[i].name)); 
        memset(&ht[i].phone,0,sizeof(ht[i].phone)); 
        ht[i].empty=-1; 
    } 
} 

int Transform(char *key) // 문자를 숫자로 변환
{ 
int number=0; 
while(*key) 
        number+=(*key++); 
return number; 
} 

int HashFunction(char *key) 
{ 
return Transform(key)%TABLE_SIZE; 
} 

int HashAdd(element item, element *ht) // 항목 추가
{ 
int i,value; 
    value = i = HashFunction(item.name); 

while(ht[i].empty==1) // 빈 버켓을 찾는다.
    { 
if(strcmp(item.name,ht[i].name)==0) 
        { 
            printf("이름이 중복되었습니다\n"); 
return -1; 
        } 

        i=(i+1) % TABLE_SIZE; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.

if(i==value) // 테이블 전체가 검사되었을 때
        { 
            printf("테이블이 가득찼습니다\n"); 
return -1; 
        } 
    } 

    item.empty=1; 
    ht[i]=item; // 버켓이 비어있다면 바로 삽입

return1; 
} 

int HashDelete(element item, element *ht) 
{ 
int i,value; 
    value = i = HashFunction(item.name); 
while( !(ht[i].empty == -1) ) // 버켓이 비어있지 않다면
    { 
if(strcmp(item.name,ht[i].name)==0) 
        { 
            printf("삭제 데이터 : 위치 = %d, 이름 : %s, 전화번호 : %s\n",\
                                              i,ht[i].name,ht[i].phone); 
            memset(&ht[i].name,0,sizeof(ht[i].name)); 
            memset(&ht[i].phone,0,sizeof(ht[i].phone)); 
            ht[i].empty=0; // 삭제 표시,한번 사용된 버켓
return1; 
        } 

        i=(i+1) % TABLE_SIZE; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.

if(i==value) // 테이블 전체가 검사되었을 때
        { 
            printf("찾는 값이 테이블에 존재하지 않습니다.\n"); 
return -1; 
        } 
    } 

    printf("테이블이 비어있습니다..\n"); 
return -1; 

} 
int HashSearch(element item, element *ht) // 키 탐색
{ 
int i,value; 
    value = i = HashFunction(item.name); 
while( !(ht[i].empty == -1) ) // 버켓이 비어있지 않다면
    { 
if(strcmp(item.name,ht[i].name)==0) 
        { 
            printf("탐색 성공 : 위치 = %d, 이름 : %s, 전화번호 : %s\n",\
                                            i,ht[i].name,ht[i].phone); 
return1; 
        } 

        i=(i+1) % TABLE_SIZE; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.

if(i==value) // 테이블 전체가 검사되었을 때
        { 
            printf("찾는 값이 테이블에 존재하지 않습니다.\n"); 
return -1; 
        } 
    } 

    printf("찾는 값이 테이블에 존재하지 않습니다.\n"); 
return -1; 
} 

int main() 
{ 
    element temp; 
int input; 
int i; 

    InitTable(hash_table); 

while(1) 
    { 
        printf("1:입력\n2:삭제\n3:탐색\n4:종료\n"); 
        scanf("%d",&input); 
        fflush(stdin); 
        printf("이름 입력 : "); 
        gets(temp.name); 

switch(input) 
        { 
case1: 
                printf("전화번호 입력 : "); 
                gets(temp.phone); 
                HashAdd(temp,hash_table); 
break; 
case2: 
                HashDelete(temp,hash_table); 
break; 
case3: 
                HashSearch(temp,hash_table); 
break; 
default : 
return0; 
        } 

for(i=0;i<TABLE_SIZE;i++) 
            printf("hashtable[%d] :%s\n",i,hash_table[i].name); 
    } 

return0; 
}