11. 해시

11-1 해시법

 

해시법 (hashing)

• 데이터를 저장할 위치 (인덱스)를 간단한 연산으로 구하는 것
• 해시값 (hash value) : 배열의 키 값(각 요소의 값)을 배열의 요소 개수로 나눈 나머지를 다시 정리한 값 > 데이터에 접근할 때 사용한다. 
• 해시 테이블 (hash tabe) : 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열 
• 해시 함수 (hash function) : 키 값을 가지고 해시 값을 만드는 과정 > 나머지를 구하는 연산 또는 나머지 연산을 다시 응용한 연산 
• 버킷 (bucket) : 해시 테이블의 각 요소 

 

* 해시와 해시 함수

•  충돌을 피하기 위해 해시 함수는 해시 테이블 크기 이하의 정수를 가능한 치우치지 않도록 (중복되지 않도록) 골게 분포되도록 만들어야 한다. 
• 해시 테이블 크기는 소수가 좋다고 알려져 있다. 이 밖에도 키 값이 정수가 아닌 경우 해시 값을 구하려면 다른 방법을 사용해야 한다. 
  ex) 실수 키 값에 대한 비트 연산 하는 방법, 문자열 키 값에 대한 각 문자 코드에 곱셈과 덧셈을 하는 방법 

 

충돌 (collision)

• 저장할 버킷이 중복되는 현상 (키값과 해시값의 대응 관계가 반드시 1:1 이라는 보장은 없다.)

충돌 대처 방법

1. 체인법 : 같은 해시 값을 갖는 요소를 연결 리스트로 관리한다. 
2. 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다. 

 

* 해시법을 사용하는 프로그램에서 다루는 데이터는 여러 데이터가 결합된 구조체인 경우가 많다. 

//회원 데이터 Member (헤더)
#ifndef ___Member
#define ___Member

//회원 데이터 
typedef struct {
   int no;         //번호
   char name[20];  //이름 
} Member;

#define MEMBER_NO 1   //번호를 나타내는 정수 값 
#define MEMBER_NAME 2 //이름을 나타내는 정수 값 

//회원 번호 비교 함수 
int MemberNoCmp(const Member *x, const Member *y);

//회원 이름 비교 함수 
int MemberNameCmp(const Member *x, const Member *y);

//회원 데이터 출력 (줄 바꿈 없음)
void PrintMember(const Member *x);

//회원 데이터 출력 (줄 바꿈 있음)
void PrintLnMember(const Member *x);

//회원 데이터를 읽어들임
//번호와 이름 가운데 하나 혹은 둘 모두를 대화형을 읽어 들이는 함수 
Member ScanMember(const char *message, int sw);
#endif

//회원 데이터 Member (소스)
#include <stdio.h>
#include <string.h>
#include "Member.h"

//회원 번호 비교 함수 
int MemberNoCmp(const Member *x, const Member *y) {
   return x->no < y->no ? -1 : x->no > y->no ? 1 : 0;
}

//회원 이름 비교 함수 
int MemberNameCmp(const Member *x, const Member *y) {
   return strcmp(x->name, y->name);
}

//회원 데이터 (번호와 이름) 출력 (줄 바꿈 없음)
void PrintMember(const Member *x) {
   printf("%d %s", x->no, x->name);
}

//회원 데이터 (번호와 이름) 출력 (줄 바꿈 있음)
void PrintLnMember(const Member *x) {
    printf("%d %s\n", x->no, x->name);
}

//회원 데이터 (번호와 이름)를 읽어 들임 
Member ScanMember(const char *message, int sw) {
   Member temp;
   printf("%s하는 데이터를 입력하시오 \n", message);
   if(sw & MEMBER_NO) { printf("번호 : "); scanf("%d", &temp.no); }
   if(sw & MEMBER_NAME) { printf("이름 : "); scanf("%s", &temp.name); }
   return temp;
}

 

1. 체인법 (chaining), 오픈 해시법 (open hashing)

• 같은 해시 값을 갖는 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법 
• 배열의 각 버킷(해시 테이블)에 저장하는 값은 그 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째 노드(node)에 대한 포인터이다. 
• 같은 해시 값을 갖는 데이터는 연결 리스트로 연결하여 저장하고, 데이터가 없는 버킷 값은 널 (NULL) 포인터 값을 저장한다. 

//체인법으로 구현한 해시(헤더)
#ifndef ___ChainHash
#define ___ChainHash
#include "Member.h"

//버킷용 구조체 
typedef struct __node {
   Member data;         //버킷에 담을 Member형 데이터 
   struct __node *next; //다음 노드에 대한 포인터. 다음 노드가 없으면 NULL이 된다. 
} Node;

//해시 테이블을 관리하기 위한 구조체 
typedef struct {
   int size;     //해시 테이블 크기 (배열 요소 개수)
   Node **table; //해시 테이블의 첫번째 요소에 대한 포인터
} ChainHash;

//해시 테이블 초기화 
int Initialize(ChainHash *h, int size);

//검색
Node *Search(const ChainHash *h, const Member *x);

//데이터 추가 
int Add(ChainHash *h, const Member *x);

//데이터 삭제 
int Remove(ChainHash *h, const Member *x);

//해시 테이블 덤프 
void Dump(const ChainHash *h);

//모든 데이터 삭제 
void Clear(ChainHash *h);

//해시 테이블 종료 
void Terminate(ChainHash *h);
#endif

/* 체인법으로 구현한 해시(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "ChainHash.h"

/*--- 해시 함수(key의 해시 값을 반환) ---*/
//실인수 key로 받은 회원 번호 값을 해시 테이블의 크기 size로 나눈 나머지 반환
static int hash(int key, int size) { 
	return key % size;
}

//(버킷의 노드에 값)노드의 각 멤버에 값을 설정
//두번째 인수가 가리키는 데이터를 data에 저장
//세번째 인수로 전달받은 다음 노드에 대한 포인터를 next에 저장 
static void SetNode(Node *n, const Member *x, const Node *next) {
	n->data = *x;				/* 데이터 */
	n->next = next;				/* 다음 노드에 대한 포인터 */
}

//해시 테이블 초기화 > 공백인 해시 테이블로 만들기 
//요소 자료형이 Node형이고 요소 개수가 size인 배열을 생성하고
//매개변수 size로 받은 값을 멤버 size에 복사한다. 
//모든 요소에 공백 포인터 NULL을 대입했기 때문에 모든 버킷이 공백 상태가 된다. 
int Initialize(ChainHash *h, int size) {
	int i;
	
    //기억 영역 확보 실패 > NULL 대입하고 멤버 size에 0 대입한다. (데이터가 잘못 추가되는 것 방지)
	if ((h->table = calloc(size, sizeof(Node *))) == NULL) {
		h->size = 0;  
		return 0;
	}

	h->size = size;  //해시 테이블 크기 
	for (i = 0; i < size; i++)	/* 모든 버킷을 공백(NULL) 상태로 만듭니다. */
		h->table[i] = NULL;
	
	return 1;
}

/*--- 검색 ---*/
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; /* 검색 실패 */
}

/*--- 데이터 추가 ---*/
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; /* 추가 성공 */
}

/*--- 데이터 삭제 ---*/
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;							/* 삭제 실패(존재하지 않음) */
}

/*--- 해시 테이블 덤프 ---*/
//해시 테이블의 모든 요소에 대해 다음에 오는 노드를 끌어당기면서 
//각 노드의 키 값과 데이터를 출력하는 작업을 반복한다.
void Dump(const ChainHash *h) {
	int i;
	for (i = 0; i < h->size; i++) {
		Node *p = h->table[i];
		printf("%02d ", i);
		
		while (p != NULL) { //같은 해시 값을 갖는 데이터는 화살표로 연결한다. 
			printf("→ %d :(%s) ", p->data.no, p->data.name);
			p = p->next;
		}
		putchar('\n');
	}
}

/*--- 모든 데이터 삭제 ---*/
void Clear(ChainHash *h) {
	int i; 
    //배열 표의 모든 요소를 순서대로 검사한다. 

	for (i = 0; i < h->size; i++) {
		Node *p = h->table[i];			/* 현재 선택한 노드 */
        //요소가 NULL이 아니면 그 해시값을 갖는 데이터가 연결 리스트에 존재하므로 
        //연결 리스트를 맨 앞부터 순서대로 검사하면서 리스트의 모든 노드에 대한 메모리를 해제한다.
		while (p != NULL) {
			Node *next = p->next;
			free(p);					/* 현재 선택한 노드의 메모리 해제 */
			p = next;					/* 다음 노드 선택 */
		}
        //마지막으로 검사중인 배열 요소에 NULL을 대입한다. > 모든 버킷 공백 상태로 만들기 
		h->table[i] = NULL;
	}
}

/*--- 해시 테이블 종료 ---*/
void Terminate(ChainHash *h) {
	Clear(h);						/* 모든 데이터 삭제 */
	free(h->table);					/* 해시 테이블 배열의 메모리 해제 */
	h->size = 0;					/* 해시 테이블 크기를 0으로 초기화(clear) */
}

 

* 매개변수 포인터/값

• SetNode 함수의 두번째 매개변수는 포인터가 아니라 값으로 주고받아도 가능하다. 
• 하지만 구조체에서 매개변수를 주고받을 때는 값이 아니라 포인터로 하는 것이 정석이다. 
  > 함수 사이에 주고받는 데이터의 크기(바이트 수)에 제한이 있기 때문이다. 

 

* Search 함수 검색 과정 

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

 

* Add 함수 요소 추가 과정 

1. 해시 함수가 키 값을 해시 값으로 변환한다. 
2. 해시 값을 인덱스로 하는 버킷을 선택한다. 
3. 버킷에 저장된 포인터가 가리키는 연결 리스트를 처음부터 순서대로 검색한다. 
   키 값과 같은 값을 찾으면 키 값이 이미 등록된 상태이므로 추가에 실패한다. 
   끝까지 스캔하여 찾지 못하면 리스트의 맨 앞 위치에 노드를 삽입한다. 

 

* Remove 함수 요소 삭제 과정 

1. 해시 함수가 키 값을 해시 값으로 변환한다. 
2. 해시 값을 인덱스로 하는 버킷을 선택한다. 
3. 선택한 버킷의 포인터가 가리키는 연결 리스트를 처음부터 순서대로 검색한다. 
   키 값과 같은 값을 찾으면 그 노드를 리스트에서 삭제한다.
   그렇지 않으면 삭제에 실패한 것.

 

* Terminate 함수 과정 

1. Clear 함수로 해시에 등록한 모든 데이터를 삭제한다. 
2. Initialize 함수로 메모리에 확보한 해시 테이블 해제 
3. 해시 테이블의 크기를 저장하는 멤버 size를 0으로 초기화한다. 

 

/* 체인 해시(ChainHash)의 사용 */
#include <stdio.h>
#include "Member.h"
#include "ChainHash.h"

/*--- 메뉴 ---*/
typedef enum {
	TERMINATE, ADD, DELETE, SEARCH, CLEAR, DUMP
} Menu;

/*--- 메뉴 선택 ---*/
Menu SelectMenu(void) {
	int ch;
	do {
		printf("(1) 추가 (2) 삭제 (3) 검색 (4) 모두 삭제 (5) 덤프 (0) 종료 : ");
		scanf("%d", &ch);
	} while (ch < TERMINATE || ch > DUMP);

	return(Menu)ch;
}

/*--- 메인 ---*/
int main(void) {
	Menu menu;					/* 메뉴 */
	ChainHash hash;				/* 해시 테이블 */
	Initialize(&hash, 13);		/* 해시 테이블 초기화 */
	
	do {
		int result;
		Member x;
		Node *temp;
		switch (menu = SelectMenu()) {
		case ADD: /*--- 데이터 추가 ---*/
			x = ScanMember("추가", MEMBER_NO | MEMBER_NAME);
			result = Add(&hash, &x);
			if (result)
				printf("\a오류 : 추가에 실패했습니다(%s).\n",
				(result == 1) ? "이미 등록됨" : "메모리 부족");
			break;
		
		case DELETE: /*--- 데이터 삭제 ---*/
			x = ScanMember("삭제", MEMBER_NO);
			result = Remove(&hash, &x);
			if (result == 1)
				printf("\a오류 : 이 번호의 데이터가 존재하지 않습니다.\n");
			break;
		
		case SEARCH: /*--- 데이터 검색 ---*/
			x = ScanMember("검색", MEMBER_NO);
			temp = Search(&hash, &x);
			if (temp == NULL)
				printf("\a검색에 실패했습니다.\n");
			else {
				printf("검색에 성공했습니다. : ");
				PrintLnMember(&temp->data);
			}
			break;
		
		case CLEAR: /*--- 모든 데이터 삭제 ---*/
			Clear(&hash);
			break;
		
		case DUMP: /*--- 해시 테이블 덤프 ---*/
			Dump(&hash);
			break;
		}
	} while (menu != TERMINATE);
	
	Terminate(&hash); /* 해시 테이블 종료 */
	
	return 0;
}

 

* 분할 컴파일과 결합 

1. 각 소스 파일은 개별적으로 컴파일되어 각각의 객체 파일이 만들어진다. 
2. 객체 파일과 라이브러리 파일에서 뽑아낸 printf 등의 함수를 연결하면 최종 실행 프로그램이 완성된다. 

분할 컴파일 순서

1) 외부 결합 (external linkage)

• 키워드 static을 붙이지 않고 정의하는 함수와 파일 유효 범위를 갖는 변수에 주어지는 특징 
• 외부 결합으로 주어진 식별자는 소스 파일 외부에 공개된다. 
• 같은 식별자가 존재하는 경우 충돌하여 '중복 정의' 오류가 발생한다. (링크 단계에서 발생)

2) 내부 결합 (internal linkage)

• 키워드 static을 붙여 정의하는 함수와 파일 유효 범위를 갖는 변수에 주어지는 특징 
• 내부 결합으로 주어진 식별자는 소스 파일의 내부에서만 통용된다. 
• 내부 결합을 갖는 식별자는 같은 이름의 식별자가 여러 소스 파일에 존재해도 '중복 정의' 오류가 발생하지 않는다. 
• 각 소스파일의 변수는 다른 소스 파일에서 사용하거나 호출할 수 없다. 

3) 무결합 (no linkage)

• 함수 안에서 정의한 것은 그 함수 안에서만 유효하며 같은 소스 파일 안에서 작성되었다고 해도 함수 외부에서는 접근할 수 없다. 
• 소스 프로그램 안에서만 사용하고 다른 소스에 존재를 알릴 필요가 없는 함수나 변수는 외부 결합 하면 안 된다. 

* 키워드 extern : 다른 소스 파일에서 정의한 변수를 사용할 때 사용 

 

오픈 주소법 (open addressing), 닫힌 해시법 (closed hashing), 연결 탐사법 (linear probing)

• 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아낼 때까지 재해시를 여러 번 반복하는 것 
• 재해시할 때 해시 함수는 자유롭게 결정해도 된다. 

/* 오픈 주소법으로 구현한 해시(헤더) */
#ifndef ___ClosedHash
#define ___ClosedHash

#include "Member.h"

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

/*--- 요소 ---*/
typedef struct {
	Member data;		/* 데이터 */
	Status stat;		/* 요소의 상태 */
} Bucket;

/*--- 해시 테이블 ---*/
typedef struct {
	int size;			/* 해시 테이블의 크기 */
	Bucket *table;		/* 해시 테이블의 첫 번째 요소에 대한 포인터 */
} ClosedHash;

/*--- 해시 테이블 초기화 ---*/
int Initialize(ClosedHash *h, int size);

/*--- 검색 ---*/
Bucket *Search(const ClosedHash *h, const Member *x);

/*--- 데이터 추가 ---*/
int Add(ClosedHash *h, const Member *x);

/*--- 데이터 삭제 ---*/
int Remove(ClosedHash *h, const Member *x);

/*--- 해시 테이블 덤프 ---*/
void Dump(const ClosedHash *h);

/*--- 모든 데이터 삭제 ---*/
void Clear(ClosedHash *h);

/*--- 해시 테이블 종료 ---*/
void Terminate(ClosedHash *h);
#endif

/* 오픈 주소법으로 구현한 해시(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "ClosedHash.h"

/*--- 해시 함수(key의 해시 값을 반환) ---*/
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, const 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(ClosedHash *h, const 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 Dump(const ClosedHash *h) {
	int i;
	for (i = 0; i < h->size; i++) {
		printf("%02d : ", i);
		
		switch (h->table[i].stat) {
		case Occupied: printf("%d(%s)\n",
			h->table[i].data.no, h->table[i].data.name);	break;
		case Empty: printf("-- 미등록 --\n");				break;
		case Deleted: printf("-- 삭제 마침 --\n");			break;
		}
	}
}

/*--- 모든 데이터 삭제 ---*/
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;		/* 해시 테이블 크기를 클리어 */
}

/* 오픈 주소법으로 구현한 해시 사용 */
#include <stdio.h>
#include "Member.h"
#include "ClosedHash.h"

/*--- 메뉴 ---*/
typedef enum {
	TERMINATE, ADD, DELETE, SEARCH, CLEAR, DUMP
} Menu;

/*--- 메뉴 선택 ---*/
Menu SelectMenu(void) {
	int ch;
	do {
		printf("(1)추가 (2)삭제 (3)검색 (4)모두 삭제 (5)덤프 (0)종료 : ");
		scanf("%d", &ch);
	} while (ch < TERMINATE || ch > DUMP);

	return(Menu)ch;
}

/*--- 메인 ---*/
int main(void) {
	Menu menu;				/* 메뉴 */
	ClosedHash hash;		/* 해시 테이블 */
	Initialize(&hash, 13);	/* 해시 테이블 초기화 */
	
	do {
		int result;
		Member x;
		Bucket *temp;
		
		switch (menu = SelectMenu()) {
		case ADD: /*--- 데이터 추가 ---*/
			x = ScanMember("추가", MEMBER_NO | MEMBER_NAME);
			result = Add(&hash, &x);
			if (result)
				printf("\a오류 : 추가에 실패했습니다(%s).\n",
				(result == 1) ? "등록 마침" : "메모리 부족");
			break;
		
		case DELETE: /*--- 데이터 삭제 ---*/
			x = ScanMember("삭제", MEMBER_NO);
			result = Remove(&hash, &x);
			if (result == 1)
				printf("\a오류 : 이 번호의 데이터는 존재하지 않습니다.\n");
			break;
		
		case SEARCH: /*--- 데이터 검색 ---*/
			x = ScanMember("검색", MEMBER_NO);
			temp = Search(&hash, &x);
			if (temp == NULL)
				printf("\a검색에 실패했습니다.\n");
			else {
				printf("검색에 성공했습니다. : ");
				PrintLnMember(&temp->data);
			}
			break;
		
		case CLEAR: /*--- 모든 데이터 삭제 ---*/
			Clear(&hash);
			break;
		
		case DUMP: /*--- 해시 테이블 덤프 ---*/
			Dump(&hash);
			break;
		}
	} while (menu != TERMINATE);
	
	Terminate(&hash); /* 해시 테이블 종료 */
	
	return 0;
}