본문 바로가기

C-Language/Hashtable

C Language Hashtable Implementation

C 언어를 이용한 Hashtable 구현


배열과 순차검색의 문제점

수만개의 데이터가 배열에 저장되어 있고 그 배열 안에서 특정 데이터를 검색해야 한다면 데이터가 배열의 끝부분에 가까이 위치해 있을수록 검색에 소요되는 시간이 길어진다. 배열은 원소를 참조할 때 색인번호(Index)를 사용하므로 0 부터 시작하여 배열의 끝까지 색인번호를 증가해가면서 쉽게 각 원소를 참조하고 비교할 수 있는 장점이 있다. 그러나 이와같은 순차검색은 배열의 원소 수가 많을 수록 많은 시간이 걸린다는 단점을 가진다.

만약에 배열에 저장된 특정 데이터의 위치(배열의 색인번호, Index)를 바로 알 수 있거나 계산해낼 수 있다면 검색시간을 획기적으로 줄일 수 있을 것이다. 


해시함수(Hash Function)

이와같은 검색시간 문제를 해결하기 위해 해시 테이블(Hashtable)이라는 데이터 구조를 이용할 수 있다. 해시테이블은 배열에 저장되는 데이터로부터 데이터가 저장될 색인번호를 결정하여 계산된 색인번호의 위치에 데이터를 저장하는 방식이다. 이 때 데이터를 이용하여 색인번호를 계산하는 알고리듬을 해시 알고리듬(Hash Algorithm)이라고 하고 해시 알고리듬을 수행하는 함수를 해시함수(Hash Function)라고 한다.


구조체 배열의 순차검색 예

#include <stdio.h>
#include <stdlib.h> // malloc(), free()
#include <string.h> // strcmp(), strcpy()

// 구조체 선언
struct User {
	int num;
	char name[16];
	char phone[16];
};

// 구조체 인스턴스 생성
struct User* createUser(int num, char* name, char* phone) {
	// 아래의 pUser 지역변수는 이 함수가 종료되면 해제되더라도 
	// malloc()을 이용하여 할당된 메모리는 명시적으로 free() 
	// 함수를 사용해야만 해제된다
	struct User* pUser = malloc(sizeof(struct User));
	pUser->num = num;
	strcpy(pUser->name, name);
	strcpy(pUser->phone, phone);
	return pUser;
}

// 구조체 배열 선언(전역변수, Global Variable)
struct User* users[20];

// 구조체 배열 안에서 이름으로 검색
struct User* findUser(char* name, int size) {
	for (int i = 0; i < size; i++) {
		if (strcmp(users[i]->name, name)==0) {
			printf("name:%s\n", users[i]->name);
			return users[i];
		}
	}
	printf("검색실패! \n");
	return NULL;
}

// 구조체 인스턴스 내용 출력
void printUser(struct User* user) {
	printf("번호:%d, 이름:%s, 전화:%s \n", 
		user->num, user->name, user->phone);
}

int main()
{
	printf("Hashtable 1, 구조체 배열및 검색 \n");

	//구조체 배열을 생성한다
	int i = 0;
	struct User* pu = createUser(10, "홍길동", "010-9786-1976");
	users[i++] = pu;
	users[i++] = createUser(11, "문재인", "010-9513-7891");
	users[i++] = createUser(12, "안철수", "010-2798-7895");
	users[i++] = createUser(13, "홍준표", "010-7852-9193");
	users[i++] = createUser(14, "유승민", "010-9761-9713");

	struct User* u = findUser("안철수", i);

	printUser(u);

	return 0;
}



위의 코드 중에서 struct 키워드를 사용하지 않으려면 구조체를 선언할 때 typedef 키워드를 사용하여 선언하면 된다

#include <stdio.h>
#include <stdlib.h> // malloc()
#include <string.h> // strcmp()

// 구조체 선언
typedef struct {
	int num;
	char name[16];
	char phone[16];
}User;

// 구조체 인스턴스 생성
User* createUser(int num, char* name, char* phone) {
	// 아래의 pUser 지역변수는 이 함수가 종료되면 해제되더라도 
	// malloc()을 이용하여 할당된 메모리는 명시적으로 free() 
	// 함수를 사용해야만 해제된다
	User* pUser = malloc(sizeof(User));
	pUser->num = num;
	strcpy(pUser->name, name);
	strcpy(pUser->phone, phone);
	return pUser;
}

// 구조체 배열 선언(전역변수, Global Variable)
User* users[20];

// 구조체 배열 안에서 이름으로 검색
User* findUser(char* name, int size) {
	for (int i = 0; i < size; i++) {
		if (strcmp(users[i]->name, name) == 0) {
			printf("name:%s\n", users[i]->name);
			return users[i];
		}
	}
	printf("검색실패! \n");
	return NULL;
}

// 구조체 인스턴스 내용 출력
void printUser(User* user) {
	printf("번호:%d, 이름:%s, 전화:%s \n",
		user->num, user->name, user->phone);
}

int main()
{
	printf("Hashtable 1, 구조체 배열및 검색 \n");

	//구조체 배열을 생성한다
	int i = 0;
	struct User* pu = createUser(10, "홍길동", "010-9786-1976");
	users[i++] = pu;
	users[i++] = createUser(11, "문재인", "010-9513-7891");
	users[i++] = createUser(12, "안철수", "010-2798-7895");
	users[i++] = createUser(13, "홍준표", "010-7852-9193");
	users[i++] = createUser(14, "유승민", "010-9761-9713");

	struct User* u = findUser("안철수", i);

	printUser(u);

	return 0;
}



이용자의 번호를 해싱하여 배열 인덱스를 구하고 해당 인덱스의 위치에 다른 데이터가 없다면 그 위치에 User 인스턴스의 주소를 저장한다

만약 해싱하여 구한 인덱스에 이미 다른 데이터가 저장되어 있는 경우에는 그 옆의 공간을 연쇄적으로 검사하여 빈 곳에 데이터를 저장한다

아래의 코드는 해시테이블에 아이템을 다수개 저장하고 저장된 모든 아이템의 리스트를 출력하는 예이다

문자열로 구성된 키를 해싱하는 예는 이곳을 클릭하여 참조하세요

#include <stdio.h>
#include <stdlib.h> // malloc()
#include <string.h> // strcmp()

#define SIZE 30 // 세미콜른 없음. 배열의 인덱스는 30을 넘지 않도록 한다

// 구조체 선언
typedef struct {
	int num;
	char name[16];
	char phone[16];
}User;

// 구조체 인스턴스 생성
User* createUser(int num, char* name, char* phone) {
	// 아래의 pUser 지역변수는 이 함수가 종료되면 해제되더라도 
	// malloc()을 이용하여 할당된 메모리는 명시적으로 free() 
	// 함수를 사용해야만 해제된다
	User* pUser = malloc(sizeof(User));
	pUser->num = num;
	strcpy(pUser->name, name);
	strcpy(pUser->phone, phone);
	return pUser;
}

int hashcode(int key) {
	return key % SIZE;
}

// 구조체 배열 선언(전역변수, Global Variable)
User* users[SIZE];

// 구조체 배열 안에서 이름으로 검색
struct User* findUser(char* name, int size) {
	for (int i = 0; i < size; i++) {
		if (strcmp(users[i]->name, name) == 0) {
			printf("name:%s\n", users[i]->name);
			return users[i];
		}
	}
	printf("검색실패! \n");
	return NULL;
}

// 구조체 인스턴스 내용 출력
void printUser(User* user) {
	printf("번호:%d, 이름:%s, 전화:%s \n",
		user->num, user->name, user->phone);
}

// Hashtable에 추가
void insert(User* u) {
	int key = u->num;
	int idx = 0;
	do {
		idx = hashcode(key);
		if (users[idx] == NULL) {
			users[idx] = u;
			break;
		}
		key++;
	} while (1);
}

void printUserList() {
	for (int i = 0; i < SIZE; i++) {
		User* u = users[i];
		if (u == NULL) continue;
		printf("%d. %d %s %s \n", i, u->num, u->name, u->phone);
	}
}

int main()
{
	printf("Hashtable 1, 구조체 배열및 검색 \n");

	//구조체를 생성하여 해시테이블에 저장한다
	User* pu = createUser(10, "홍길동", "010-9786-1976");

	insert(pu);
	insert( createUser(11, "문재인", "010-9513-7891") );
	insert( createUser(25, "안철수", "010-2798-7895") );
	insert( createUser(37, "홍준표", "010-7852-9193") );
	insert( createUser(44, "유승민", "010-9761-9713") );

	printUserList();

	printf("프로그램 종료...\n");
	return 0;
}



해시테이블에서 검색하는 예(위의 코드에 get() 함수 추가)

#include <stdio.h>
#include <stdlib.h> // malloc()
#include <string.h> // strcmp()

#define SIZE 30 // 세미콜른 없음. 배열의 인덱스는 30을 넘지 않도록 한다

// 구조체 선언
typedef struct {
	int num;
	char name[16];
	char phone[16];
}User;

// 구조체 인스턴스 생성
User* createUser(int num, char* name, char* phone) {
	// 아래의 pUser 지역변수는 이 함수가 종료되면 해제되더라도 
	// malloc()을 이용하여 할당된 메모리는 명시적으로 free() 
	// 함수를 사용해야만 해제된다
	User* pUser = malloc(sizeof(User));
	pUser->num = num;
	strcpy(pUser->name, name);
	strcpy(pUser->phone, phone);
	return pUser;
}

int hashcode(int key) {
	return key % SIZE;
}

// 구조체 배열 선언(전역변수, Global Variable)
User* users[SIZE];

// 구조체 배열 안에서 이름으로 순차검색
User* findUser(char* name, int size) {
	for (int i = 0; i < size; i++) {
		if (strcmp(users[i]->name, name) == 0) {
			printf("name:%s\n", users[i]->name);
			return users[i];
		}
	}
	printf("검색실패! \n");
	return NULL;
}

// 해시테이블 검색(찾으면 해당 값을 리턴하고 아니면 NULL을 리턴)
User* get(int num) {
	int key = num;
	do {
		//번호를 해싱하여 배열 인덱스를 구하고 배열의 원소를 추출한다
		int idx = hashcode(key);
		User* u = users[idx];
		//해당 인덱스 위치에 저장된 값이 NULL이면 NULL을 리턴한다
		if (u == NULL) return NULL;
		else {// 해당 인덱스에 저장된 num이 파라미터로 전달된 num과 동일하면 검색완료
			if (u->num == num) return u;
		}
		//해당 인덱스 위치에 다른 값이 있을 경우에는 그 다음 인덱스로 이동하여 검색
		key++;
	} while (1);
}

// 구조체 인스턴스 내용 출력
void printUser(User* user) {
	printf("번호:%d, 이름:%s, 전화:%s \n",
		user->num, user->name, user->phone);
}

// Hashtable에 추가
void insert(User* u) {
	int key = u->num;
	int idx = 0;
	do {
		idx = hashcode(key);
		if (users[idx] == NULL) {
			users[idx] = u;
			break;
		}
		key++;
	} while (1);
}

void printUserList() {
	for (int i = 0; i < SIZE; i++) {
		User* u = users[i];
		if (u == NULL) continue;
		printf("%d. %d %s %s \n", i, u->num, u->name, u->phone);
	}
}

int main()
{
	printf("Hashtable 1, 구조체 배열및 검색 \n");

	//구조체를 생성하여 해시테이블에 저장한다
	User* pu = createUser(10, "홍길동", "010-9786-1976");

	insert(pu);
	insert( createUser(11, "문재인", "010-9513-7891") );
	insert( createUser(25, "안철수", "010-2798-7895") );
	insert( createUser(37, "홍준표", "010-7852-9193") );
	insert( createUser(44, "유승민", "010-9761-9713") );

	printUserList();

	//검색 테스트
	User* res = get(55);
	if (res == NULL) printf("검색결과가 없음\n");
	else printf("%d, %s, %s \n", res->num, res->name, res->phone);

	printf("프로그램 종료...\n");
	return 0;
}



해시테이블 삭제 기능 구현의 예(위의 코드에 delete() 함수 추가)

#include <stdio.h>
#include <stdlib.h> // malloc()
#include <string.h> // strcmp()

#define SIZE 30 // 세미콜른 없음. 배열의 인덱스는 30을 넘지 않도록 한다

// 구조체 선언
typedef struct {
	int num;
	char name[16];
	char phone[16];
}User;

// 구조체 인스턴스 생성
User* createUser(int num, char* name, char* phone) {
	// 아래의 pUser 지역변수는 이 함수가 종료되면 해제되더라도 
	// malloc()을 이용하여 할당된 메모리는 명시적으로 free() 
	// 함수를 사용해야만 해제된다
	User* pUser = malloc(sizeof(User));
	pUser->num = num;
	strcpy(pUser->name, name);
	strcpy(pUser->phone, phone);
	return pUser;
}

int hashcode(int key) {
	return key % SIZE;
}

// 구조체 배열 선언(전역변수, Global Variable)
User* users[SIZE];

// 구조체 배열 안에서 이름으로 순차검색
User* findUser(char* name, int size) {
	printf("\n 이름(%s)으로 검색결과 =========================== \n", name);
	for (int i = 0; i < size; i++) {
		if (strcmp(users[i]->name, name) == 0) {
			printf("name:%s\n", users[i]->name);
			return users[i];
		}
	}
	printf("검색실패! \n");
	return NULL;
}

// 해시테이블 검색(찾으면 해당 값을 리턴하고 아니면 NULL을 리턴)
User* get(int num) {
	int key = num;
	do {
		//번호를 해싱하여 배열 인덱스를 구하고 배열의 원소를 추출한다
		int idx = hashcode(key);
		User* u = users[idx];
		//해당 인덱스 위치에 저장된 값이 NULL이면 NULL을 리턴한다
		if (u == NULL) return NULL;
		else {// 해당 인덱스에 저장된 num이 파라미터로 전달된 num과 동일하면 검색완료
			if (u->num == num) return u;
		}
		//해당 인덱스 위치에 다른 값이 있을 경우에는 그 다음 인덱스로 이동하여 검색
		key++;
	} while (1);
}

// 구조체 인스턴스 내용 출력
void printUser(User* user) {
	printf("\n 사용자(%s) 정보 =========================== \n", user->name);
	printf("번호:%d \t 이름:%s \t 전화:%s \n",
		user->num, user->name, user->phone);
}

// Hashtable에 추가
void insert(User* u) {
	int key = u->num;
	int idx = 0;
	do {
		idx = hashcode(key);
		if (users[idx] == NULL) {
			users[idx] = u;
			break;
		}
		key++;
	} while (1);
}

// 해시테이블에서 삭제(get()함수에서 일부만 변경하여 작성함)
unsigned char delete(int num) {
	int key = num;
	do {
		//번호를 해싱하여 배열 인덱스를 구하고 배열의 원소를 추출한다
		int idx = hashcode(key);
		User* u = users[idx];
		//해당 인덱스 위치에 저장된 값이 NULL이면 0을 리턴한다
		if (u == NULL) return 0;
		else {// 해당 인덱스에 저장된 num이 파라미터로 전달된 num과 동일하면 삭제하고 1 리턴
			if (u->num == num) {
				free((void*)u);
				users[idx] = NULL;
				return 1;
			}
		}
		//해당 인덱스 위치에 다른 값이 있을 경우에는 그 다음 인덱스로 이동하여 검색
		key++;
	} while (1);
}

void printUserList() {
	printf("\n 전체 사용자 리스트 =========================== \n");
	for (int i = 0; i < SIZE; i++) {
		User* u = users[i];
		if (u == NULL) continue;
		printf("%d \t %d \t %s \t %s \n", i, u->num, u->name, u->phone);
	}
}

int main()
{
	printf("Hashtable 1, 구조체 배열및 검색 \n");

	//구조체를 생성하여 해시테이블에 저장한다
	User* pu = createUser(10, "홍길동", "010-9786-1976");

	insert(pu);
	insert( createUser(11, "문재인", "010-9513-7891") );
	insert( createUser(25, "안철수", "010-2798-7895") );
	insert( createUser(37, "홍준표", "010-7852-9193") );
	insert( createUser(44, "유승민", "010-9761-9713") );

	printUserList();

	//검색 테스트
	User* res = get(44);
	printf("\n 해시테이블 검색결과 ========================== \n");
	if (res == NULL) printf("검색결과가 없음\n");
	else printf("%d \t %s \t %s \n", res->num, res->name, res->phone);

	//삭제 테스트
	unsigned char removed = delete(37);
	printf("\n 삭제결과:%s \n", removed ? "성공" : "실패");

	printUserList();

	printf("\n 프로그램 종료...\n");
	return 0;
}



동일한 번호를 사용하는 아이템을 중복 저장하는 경우에는 기존 아이템은 삭제되고 나중에 추가된 아이템이 저장된다

위의 코드에서 insert() 함수를 약간 변경

#include <stdio.h>
#include <stdlib.h> // malloc()
#include <string.h> // strcmp()

#define SIZE 30 // 세미콜른 없음. 배열의 인덱스는 30을 넘지 않도록 한다

// 구조체 선언
typedef struct {
	int num;
	char name[16];
	char phone[16];
}User;

// 구조체 인스턴스 생성
User* createUser(int num, char* name, char* phone) {
	// 아래의 pUser 지역변수는 이 함수가 종료되면 해제되더라도 
	// malloc()을 이용하여 할당된 메모리는 명시적으로 free() 
	// 함수를 사용해야만 해제된다
	User* pUser = malloc(sizeof(User));
	pUser->num = num;
	strcpy(pUser->name, name);
	strcpy(pUser->phone, phone);
	return pUser;
}

int hashcode(int key) {
	return key % SIZE;
}

// 구조체 배열 선언(전역변수, Global Variable)
User* users[SIZE];

// 구조체 배열 안에서 이름으로 순차검색
User* findUser(char* name, int size) {
	printf("\n 이름(%s)으로 검색결과 =========================== \n", name);
	for (int i = 0; i < size; i++) {
		if (strcmp(users[i]->name, name) == 0) {
			printf("name:%s\n", users[i]->name);
			return users[i];
		}
	}
	printf("검색실패! \n");
	return NULL;
}

// 해시테이블 검색(찾으면 해당 값을 리턴하고 아니면 NULL을 리턴)
User* get(int num) {
	int key = num;
	do {
		//번호를 해싱하여 배열 인덱스를 구하고 배열의 원소를 추출한다
		int idx = hashcode(key);
		User* u = users[idx];
		//해당 인덱스 위치에 저장된 값이 NULL이면 NULL을 리턴한다
		if (u == NULL) return NULL;
		else {// 해당 인덱스에 저장된 num이 파라미터로 전달된 num과 동일하면 검색완료
			if (u->num == num) return u;
		}
		//해당 인덱스 위치에 다른 값이 있을 경우에는 그 다음 인덱스로 이동하여 검색
		key++;
	} while (1);
}

// 구조체 인스턴스 내용 출력
void printUser(User* user) {
	printf("\n 사용자(%s) 정보 =========================== \n", user->name);
	printf("번호:%d \t 이름:%s \t 전화:%s \n",
		user->num, user->name, user->phone);
}

// Hashtable에 추가
void insert(User* u) {
	int key = u->num;
	int idx = 0;
	do {
		idx = hashcode(key);
		if (users[idx] == NULL) {
			users[idx] = u;
			break;
		}
		// 이미 저장된 아이템이라면 기존 아이템을 삭제하고 새로 저장한다
		else if (users[idx]->num == u->num) {
			free(users[idx]);
			users[idx] = u;
			break;
		}
		key++;
	} while (1);
}

// 해시테이블에서 삭제(get()함수에서 일부만 변경하여 작성함)
unsigned char delete(int num) {
	int key = num;
	do {
		//번호를 해싱하여 배열 인덱스를 구하고 배열의 원소를 추출한다
		int idx = hashcode(key);
		User* u = users[idx];
		//해당 인덱스 위치에 저장된 값이 NULL이면 0을 리턴한다
		if (u == NULL) return 0;
		else {// 해당 인덱스에 저장된 num이 파라미터로 전달된 num과 동일하면 삭제하고 1 리턴
			if (u->num == num) {
				free((void*)u);
				users[idx] = NULL;
				return 1;
			}
		}
		//해당 인덱스 위치에 다른 값이 있을 경우에는 그 다음 인덱스로 이동하여 검색
		key++;
	} while (1);
}

void printUserList() {
	printf("\n 전체 사용자 리스트 =========================== \n");
	for (int i = 0; i < SIZE; i++) {
		User* u = users[i];
		if (u == NULL) continue;
		printf("%d \t %d \t %s \t %s \n", i, u->num, u->name, u->phone);
	}
}

int main()
{
	printf("Hashtable 1, 구조체 배열및 검색 \n");

	//구조체를 생성하여 해시테이블에 저장한다
	User* pu = createUser(10, "홍길동", "010-9786-1976");

	insert(pu);
	insert( createUser(11, "문재인", "010-9513-7891") );
	insert( createUser(25, "안철수", "010-2798-7895") );
	insert( createUser(37, "홍준표", "010-7852-9193") );
	insert( createUser(44, "유승민", "010-9761-9713") );
	insert( createUser(56, "조원진", "010-1234-5678"));
	insert( createUser(56, "조원진", "010-4568-2975"));

	printUserList();

	//검색 테스트
	User* res = get(44);
	printf("\n 해시테이블 검색결과 ========================== \n");
	if (res == NULL) printf("검색결과가 없음\n");
	else printf("%d \t %s \t %s \n", res->num, res->name, res->phone);

	//삭제 테스트
	unsigned char removed = delete(37);
	printf("\n 삭제결과:%s \n", removed ? "성공" : "실패");

	printUserList();

	printf("\n 프로그램 종료...\n");
	return 0;
}