해시법 (C)

해시법은 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법이다.

정렬된 배열에 새로운 값 추가

기본적으로 새로운 값을 배열 사이에 삽입하려면 O(n)의 시간이 든다. 해시법은 이를 보완한다.

해시법

해시법은 데이터를 저장할 위치를 간단한 연산으로 구하는 것이다. 게다가 추가, 삭제도 효율적으로 수행할 수 있다.
배치하고자 하는 배열의 길이가 13일 때, data들의 index는 data%13이 된다. 그럼 삽입 삭제가 용이하다.
이렇게 index를 계산하는 과정을 해시 함수(hash function)이라고 한다. 해시 테이블의 각 요소(인덱스들)를 버킷(bucket)이라고 한다.

충돌

나머지가 서로 같은 수들은 반드시 존재한다. 따라서 버킷이 중복될 수 밖에없는데 이를 충돌(collision)이라고 한다.
충돌에 대한 대처는 다음과 같다.
1. 체인법 : 같은 해시 값을 갖는 요소를 연결 리스트로 관리한다.
2. 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

체인법

체인법은 같은 해시 값을 갖는 데이터를 연결 리스트에 의해 사슬 모양으로 연결하는 방법이다. 따라서 배열(해시 테이블)의 각 버킷에 저장하는 값은 연결 리스트의 첫번째 노드에 대한 포인터이다.

체인법으로 구현한 노드의 구조체는 다음과 같다.

typedef struct __node {
	Member data;
    struct __node* next;
} Node;

typedef struct {
	int size;
    Node** table;
} Chainhash;

함수는 다음과 같다.

//해시 함수
static int hash(int key, int size) {
	return key % size;
}

//값을 설정
static void SetNode(Node* n, Member x, const Node* next) {
	n->data = x;
    n->next = next;
}
// * 함수간의 주고 받는 데이터의 크기에 제한이 있기때문에 원래는 포인터로 하는 것이 정석이다.

//초기화
int Initialize(ChainHash* h, int size) {
	int i;
    if((h->table = calloc(size, sizeof(Node *))) == NULL) { //영역 확보에 실패
    h->size = 0;
    return 0;
    }
    h->size = size;
    for(i=0; i<size; i++)
    	h->table[i] = NULL; //모든 버킷을 공백 상태로 만든다.
    return 1;
}

• 충돌을 없애기 위해 연결 리스트를 쓰는 것은 좋지만, 데이터를 많이 잡아먹는다. 따라서 애초에 충돌이 없도록 하는 것이 가장 베스트인데, 이는 해시 테이블 크기는 소수가 좋다.

키 값으로 검색하는 Search 함수
1. 해시 함수가 키 값을 해시 값으로 변환한다.
2. 해시 값을 인덱스로 하는 버킷을 선택한다.
3. 선택한 버킷의 연결 리스트를 순서대로 검색한다. 찾으면 검색 성공, 끝까지 스캔하며 찾지 못하면 검색 실패이다.
코드는 다음과 같다.

//Member->no 는 정수형 데이터 값이다.
Node* Search(const ChainHash* h, const Member* x) {
	int key = hash(x->no, h->size);
    Node* p = h->table[key];
    
    while(p != NULL) {
    	if(p->data.no == x->no)
        	return p;
        p = p->next;
    }
    return NULL;
}

추가 Add 함수
1. 해시 함수가 키 값을 해시 값으로 변환
2. 해시 값을 인덱스로 하는 버킷을 선택
3. 버킷에 저장된 포인터가 가리키는 연결 리스트를 순서대로 검색, 키 값과 같은 값을 찾으면 실패, 찾지못하면 리스트의 맨 앞 위치에 노드를 삽입.

//데이터 추가
int Add(ChainHash* h, const Member* x) {
	int key = hash(x->no, h->size);
    Node* p = h->table[key];
    Node* temp;
    while(p != NULL) {
    	if(p->data.no == x->no)
        	return 1;
        p = p->next;
    }
    if((temp = calloc(1, sizeof(Node))) == NULL)
    	return 2;
    SetNode(temp, x, h->table[key]);
    h->table[key] = temp;
    return 0;
}

삭제 Remove 함수
1. 해시값 변환
2. 버킷 선택
3. 선택한 버킷의 포인터가 가리키는 연결 리스트를 순서대로 검색, 키 값과 같은 값을 찾으면 그 노드를 리스트에서 삭제 못찾으면 실패.

int Remove(ChainHash* h, const Member* x) {
	int key = hash(x->no, h->size);
    Node* p = h->table[key];
    Node** pp = &h->table[key];
    while(p != NULL) {
    	if(p->data.no == x->no) {
        	*pp = p->next;
            free(p);
            return 0;
        }
        pp = &p->next;
        p = p->next;
    }
    return 1;
}

해시 테이블 내용 출력 Dump 함수
해시 테이블의 내용을 통째로 출력한다.

void Dump(const ChainHash* h) {
	int i;
    for(i=0; i < h->size; i++) {
    	Node* p = h->table[i];
        while(p != NULL) {
        	printf("%d %s", p->data.no, p->data.name);
            p = p->next;
        }
        putchar('\n');
    }
}

모든 데이터를 삭제하는 Clear 함수

void Clear(ChainHash* h) {
	int i;
    for(i=0; i < h->size; i++) {
    	Node* p = h->table[i];
        while(p != NULL) {
        	Node* next = p->next;
            free(p);
            p = next;
        }
        h->table[i] = NULL;
    }
}

종료하는 Terminate 함수

void Terminate(ChainHash* h) {
	Clear(h);
    free(h->table);
    h->size = 0;
}

오픈 주소법

오픈 주소법(opening addressing)은 충돌이 발생했을 때, 재해시를 수행하여 비어있는 버킷을 찾아내는 방법이다.
닫힌 해시법(closed hashing)이라고도 한다. 빈 버킷을 만날 때까지 재해시를 여러 번 반복하므로 연결 탐사법(linear probing)이라고도 한다.

요소 삭제
요소를 삭제하기 위핸 검색부터 해야한다.

우선 각 버킷에 대해 3가지 속성을 부여한다.
1. 데이터 저장 속성값
2. 비어 있음 속성값
3. 삭제 마침 속성값

만약 해시값에 맞는 버킷을 탐색하는데 2. 비어있음이면 검색 실패이다. 3. 삭제 마침이면 같은 해시 값의 데이터가 다른 버킷에 저장되어 있다는 것이므로 다음 인덱스를 탐색한다.

구조체와 함수는 다음과 같다.

//요소의 상태
typedef enum {
	Occupied, Empty, Deleted
} Status;

//요소
typedef struct {
	Member data;
    Status stat;
}

//해시 테이블
typedef struct {
	int size;
    Bucket* table;
} ClosedHash;

선언은 생략한다.

//해시 함수
static int hash(int key, int size) {
	return key % size;
}
//재해시 함수
static int rehash(int key, int size) {
	return (key + 1) % size;
}

//노드의 각 멤버에 값을 설정
static void SetBucket(Bucket* n, const Member* x, Status stat) {
	n->data = *x;
    n->stat = stat;
}

//해시 테이블 초기화
int Initialize(ClosedHash* h, int size) {
	int i;
    if((h->table = calloc(size, sizeof(Bucket))) == NULL) {
    	h->size = 0;
        return 0;
    }
    h->size = size;
    for(i = 0; i < size; i++) {
    	h->table[i].stat = Empty;
    return 1;
    }
}

//검색
Bucket* Search(const ClosedHash* h, cosnt Member* x) {
	int i;
    int key = hash(x->no, h->size);
    Bucket* p = &h->table[key];
    for(i = 0; p->stat != Empty && i < h->size; i++) {
    	if(p->stat == Occupied && p->data.no == x->no)
        	return p;
        key = rehash(key, h->size);
        p = &h->table[key];
    }
    return NULL;
}

//데이터 추가
int Add(CloseHash* h, cosnt Member* x) {
	int i;
    int key = hash(x->no, h->size);
    Bucket* p = &h->table[key];
    if(Search(h, x))
    	return 1;
    for(i = 0; i < h->size; i++) {
    	if(p->stat == Empty || p->stat == Deleted) {
        	SetBucket(p, x, Occupied);
            return 0;
        }
        key = rehash(key, h->size);
        p = &h->table[key];
    }
    return 2;
}

//데이터 삭제
int Remove(ClosedHash* h, const Member* x) {
	Bucket* p = Search(h, x);
    if(p == NULL)
    	return 1; // 이값은 존재하지 않음.
    p->stat = Deleted;
    return 0;
}

//모든 데이터 삭제
void Clear(ClosedHash* h) {
	int i;
    for(i = 0; i < h->size; i++)
    	h->table[i].stat = Empty;
}

//종료
void Terminate(ClosedHash* h) {
	Clear(h);
    free(h->table);
    h->size = 0;
}