#자료구조와 함께 배우는 알고리즘 입문 C언어 - 13

11장 해시

 

11-1 해시법

데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행하는 방법

 

충돌 : 저장할 버킷이 중복되는 현상

충돌에 대한 대처

1. 체인법 : 같은 해시값을 갖는 요소를 연결 리스트로 관리

2. 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복

 

키 값과 데이터

// 회원데이터 구조체 정의(헤더)
#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

번호의 대소관계를 판단하는 MemberNoCmp 함수

int MemberNoCmp(const Member* x, const Member* y)
{
	return x->no < y->no ? -1 : x->no > y->no ? 1 : 0;
}

이름의 대소관계를 판단하는 MemberNameCmp 함수

int MemberNameCmp(const Member* x, const Member* y)
{
	return strcmp(x->name, y->name);
}

번호와 이름을 출력하는 PrintMember / PrintLnMember 함수

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);
}

번호와 이름 가운데 하나 혹은 둘 모두를 대화형으로 읽어 들이는 ScanMember 함수

Member ScanMember(const char* message, int sw)
{
	Member tmp;
	printf("%s하는 데이터를 입력하세요. \n", message);
	if (sw & MEMBER_NO)
	{
		printf("번호 : ");
		scanf("%d", &tmp.no);
	}
	if (sw & MEMBER_NAME)
	{
		printf("이름 : ");
		scanf("%d", &tmp.name);
	}

	return tmp;
}

 

체인법

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

typedef struct __node {
	Member data;
	struct __node* next;
} 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

해시 값을 구하는 hash 함수

static int hash(int key, int size)
{
	return key % size;
}

노드에 값을 설정하는 SetNode 함수

static void SetNode(Node* n, const Member* x, const Node* next)
{
	n->data = *x;
	n->next = (Node*)next;
}

해시 테이블을 초기화하는 Initialize 함수

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 함수

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 함수

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

요소를 삭제하는 Remove 함수

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];
		printf("%02d ", 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;
}

 

오픈 주소법

// 오픈 주소법으로 구현한 해시(헤더)
#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 Memeber* x);

int Remove(ClosedHash* h, const Memeber* x);

void Dump(const ClosedHash* h);

void Clear(ClosedHash* h);

void Terminate(ClosedHash* h);
#endif

해시 값을 구하는 hash 함수

static int hash(int key, int size)
{
	return key % size;
}

재해시 함수 reshah

static int rehash(int key, int size)
{
	return (key + 1) % size;
}

노드의 각 멤버에 값을 설정하는 SetBucket 함수

static void SetBucket(Bucket* n, const Member* x, Status stat)
{
	n->data = *x;
	n->stat = stat;
}

해시 테이블을 초기화하는 Initialize 함수

int Initialize(ClosedHash* h, int size)
{
	int i;
	if ((h->table = (Bucket*)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;
}

검색 Search 함수

Bucket* Search(const ClosedHash* h, const Member* x)
{
	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;
}

데이터 추가하는 Add 함수

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 == Dleted)
		{
			SetBucket(p, x, Occupied);
			return 0;
		}
		key = rehash(key, h->size);
		p = &h->table[key];
	}
	return 0;
}

데이터를 삭제하는 Remove 함수

int Remove(ClosedHash* h, const Member* x)
{
	Bucket* p = Search(h, x);
	if (p == NULL)
	{
		return 1;
	}
	p->stat = Deleted;
	return 0;
}

해시 테이블의 내용을 출력하는 Dump 함수

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;
		}
	}
}

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

void Clear(ClosedHash* h)
{
	int i;
	for (i = 0; i < h->size; i++)
	{
		h->table[i].stat = Empty;
	}
}

해시 테이블을 종료하는 Terminate 함수

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