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