[Algorithm] C/C++에서 해시 테이블(Hash Table) 구현하기
업데이트(2019.02.04): 중복 및 map 관련 검증 에러 수정
업데이트(2019.01.19): 코드 수정 및 검증 코드 추가
C++에서 해시 테이블(Hash Table)을 구현해보자
환경
- C++
- 연결 리스트와 해시 함수에 대한 이해(제일 하단 참고자료 참고)
해시 함수(Hash Function)
해시 함수(Hash Function)란?
Hash Function: 해시 함수는 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이 때 함수를 구현하는 방법에 따라서 해당 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다.(H(s1) = H(s2))- 아래 사진의 경우에는 좌측에 파란 색들이
key이며 각key값들이 해시 함수의 결과를 오른쪽 우측에 숫자로 바뀌었음을 보여준다. 나중에 해시 테이블에서는 이key을 해시한 결과를 배열의 인덱스로 사용한다. - 해시 함수를
H()라고 했을 때H(Jonh Smith) = 02
해시 충돌(Hash Collision)
- 서로 다른 문자열을 해시한 결과가 동일한 경우
- 해시 함수를
H()라고 했을 때 서로 다른 문자열s1과s2에 대해서H(s1) = H(s2)인 경우 - 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면
Chaining혹은Open Addressing을 통해서 해결해야한다.
예시
- 아래는 아주 간단한 해시 함수의 예제로 문자열을 받아서 정수로 반환한다.
- 검색해보면 다양한 구현법이 존재하며 Shift연산과 소수를 이용해서 하면 더 해시 충돌을 막을 수 있다고 한다.(나중에 증명 같은건 찾아봐야지…)
int hash(const char * str) {
int hash = 401;
int c;
while (*str != '\0') {
hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
str++;
}
return hash % MAX_TABLE;
}
해시 테이블(Hash Table)
key와value로 된 쌍을 저장하는 자료구조이다.- 아래 사진처럼
Lisa Smith라는key로521-8976의value를 저장할 수 있도록 설계된 자료구조입니다. - C++에서는 map 그리고 python에서는 dictionary를 통해서 보다 쉽게 이용할 수 있습니다.(여기서는 한번 구현해 보는것에 의의!)
- 성능이 좋을 때는
O(c)에 접근을 할 수 있기 때문에 공간을 소비해서 접근속도를 늘리고 싶을 때 이용한다. 물론,O(c)도 해시 테이블의 용량이 엄청 크고 해시 함수도 충돌이 일어나지 않는다는 가정이 있을 때 가능하다. - 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면
Chaining혹은Open Addressing을 통해서 해결해야한다.
구현
- 여기서는 충돌일 있을때
Chaining을 이용했으며Singly Linked List(단순 연결 리스트)를 이용해서 작성하였다.
공통
key에 따른 데이터들은Chaining을 이용했기 때문레List로 해시테이블을 구현- 데이터를 저장하는
Node선언 #define에 나와있는 값을 조절해서 테이블의 크기나 해시 테이블에 집어넣을 데이터의 수를 조절할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_TABLE 5 // 테이블 크기
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // 해시테이블에 넣을 데이터의 수
#define DELETE_COUNT 6 // 삭제할 데이터의 수
#define FIND_COUNT 8 // 찾을 데이터의 수
struct Node {
char key[MAX_KEY];
int value;
Node * next;
};
Node * tb[MAX_TABLE]; // 해시 테이블(해당 인덱스에 리스트로 작성)
char keys[MAX_DATA][MAX_KEY]; // 문자열 key들
int values[MAX_DATA]; // key에 대응하는 값들
초기화 함수
- 랜덤 함수를 이용해서
key-value쌍들을 생성합니다.
void init() {
// 해시테이블 초기화
for (int i = 0; i < MAX_TABLE; ++i) {
Node * cur = tb[i];
Node * tmp;
while (cur != NULL) {
tmp = cur;
cur = cur->next;
free(tmp);
}
tb[i] = NULL;
}
// 랜덤함수를 위한 srand와 seed
srand(time(NULL));
// key에 대응하는 값들 초기화
for (int i = 0; i < MAX_DATA; ++i) {
values[i] = rand() % 100 + 1;
}
// 문자열 key들 초기화
for (int i = 0; i < MAX_DATA; ++i) {
for (int j = 0; j < MAX_KEY - 1; ++j) {
keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
}
keys[i][MAX_KEY - 1] = '\0';
}
}
문자열 함수
- 복사와 비교 함수 직접 작성(따로 사용해도 무방!)
void my_str_cpy(char * dest, const char * src) {
while (*src != '\0') {
*dest = *src;
dest++; src++;
}
*dest = '\0';
}
int my_str_cmp(const char * str1, const char * str2) {
while (*str1 != '\0' && (*str1 == *str2)) {
str1++;
str2++;
}
return *str1 - *str2;
}
해시 함수
- 위에 소개했던 내용과 동일하게 Shift연산과 소수를 이용함
- 해시 테이블의 인덱스로 활용하기 때문에 반드시
MAX_TABLE의 나머지를 반환해야함
int hash(const char * str) {
int hash = 401;
int c;
while (*str != '\0') {
hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
str++;
}
return hash % MAX_TABLE;
}
추가
- 일반적인 추가와 같으며 중복된 key가 있을 경우에는 값을 바꿉니다.
void add(const char * key, int value) {
Node * new_node = (Node *)malloc(sizeof(Node));
my_str_cpy(new_node->key, key);
new_node->value = value;
new_node->next = NULL;
int index = hash(key);
if (tb[index] == NULL) {
tb[index] = new_node;
}
else {
Node * cur = tb[index];
while (cur != NULL) {
// key가 중복이면 값을 바꾸기
if (my_str_cmp(cur->key, key) == 0) {
cur->value = value;
return;
}
cur = cur->next;
}
// 중복이 아니면 앞에다가 추가
new_node->next = tb[index];
tb[index] = new_node;
}
}
값 찾기
- 리스트를 이용하면 어렵지 않게 찾을 수 있습니다. 쭉 리스트를 따라가면서 순회하고 값을 찾으면 됩니다.
- 값이 있으면
val에 저장하고true를 반환하고 아니면false를 반홥합니다.
bool find(const char * key, int * val) {
int index = hash(key);
Node * cur = tb[index];
// 하나하나 찾아가면서 확인
while (cur != NULL) {
if (my_str_cmp(cur->key, key) == 0) {
*val = cur->value;
return true;
}
cur = cur->next;
}
return false;
}
삭제
- 삭제도 리스트를 이용하면 쉽게 할 수 있으며 첫번째 삭제만 주의해주면 됩니다.
bool destroy(const char * key) {
int index = hash(key);
// 처음이 비어있는지 확인
if (tb[index] == NULL) {
return false;
}
// 첫번째
if (my_str_cmp(tb[index]->key, key) == 0) {
Node * first = tb[index];
tb[index] = tb[index]->next;
free(first);
return true;
}
// 나머지의 경우
else {
Node * cur = tb[index]->next;
Node * prev = tb[index];
while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return false;
prev->next = cur->next;
free(cur);
return true;
}
}
출력
- 테이블의 배열을 모두 돌고 각각의 원소를 순회하면서
key-value쌍을 출렵합니다.
void print_hash() {
for (int i = 0; i < MAX_TABLE; ++i) {
if (tb[i] != NULL) {
printf("index: %d\n", i);
Node * cur = tb[i];
while (cur != NULL) {
printf("{ %s, %d }, ", cur->key, cur->value);
cur = cur->next;
}
printf("\n");
}
}
}
메인
- 추가, 삭제 그리고 찾는 과정을 코드로 작성하여 테스트 하였습니다.
int main() {
char tmp_key[MAX_KEY];
init();
// Add
printf("Add to hash table\n");
for (int i = 0; i < MAX_DATA; ++i) {
add(keys[i], values[i]);
}
print_hash();
printf("\n");
// Delete
printf("Deleted keys: ");
for (int i = 0; i < DELETE_COUNT; ++i) {
my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
printf("%s ", tmp_key);
destroy(tmp_key);
}
printf("\n");
print_hash();
printf("\n");
// Find
int val;
printf("Found: ");
for (int i = 0; i < FIND_COUNT; ++i) {
my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
if (find(tmp_key, &val)) {
printf("{ %s, %d } ", tmp_key, val);
}
}
printf("\n");
return 0;
}
코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_TABLE 5 // 테이블 크기
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // 해시테이블에 넣을 데이터의 수
#define DELETE_COUNT 6 // 삭제할 데이터의 수
#define FIND_COUNT 8 // 찾을 데이터의 수
struct Node {
char key[MAX_KEY];
int value;
Node * next;
};
Node * tb[MAX_TABLE]; // 해시 테이블(해당 인덱스에 리스트로 작성)
char keys[MAX_DATA][MAX_KEY]; // 문자열 key들
int values[MAX_DATA]; // key에 대응하는 값들
void init() {
// 해시테이블 초기화
for (int i = 0; i < MAX_TABLE; ++i) {
Node * cur = tb[i];
Node * tmp;
while (cur != NULL) {
tmp = cur;
cur = cur->next;
free(tmp);
}
tb[i] = NULL;
}
// 랜덤함수를 위한 srand와 seed
srand(time(NULL));
// key에 대응하는 값들 초기화
for (int i = 0; i < MAX_DATA; ++i) {
values[i] = rand() % 100 + 1;
}
// 문자열 key들 초기화
for (int i = 0; i < MAX_DATA; ++i) {
for (int j = 0; j < MAX_KEY - 1; ++j) {
keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
}
keys[i][MAX_KEY - 1] = '\0';
}
}
void my_str_cpy(char * dest, const char * src) {
while (*src != '\0') {
*dest = *src;
dest++; src++;
}
*dest = '\0';
}
int my_str_cmp(const char * str1, const char * str2) {
while (*str1 != '\0' && (*str1 == *str2)) {
str1++;
str2++;
}
return *str1 - *str2;
}
int hash(const char * str) {
int hash = 401;
int c;
while (*str != '\0') {
hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
str++;
}
return hash % MAX_TABLE;
}
void add(const char * key, int value) {
Node * new_node = (Node *)malloc(sizeof(Node));
my_str_cpy(new_node->key, key);
new_node->value = value;
new_node->next = NULL;
int index = hash(key);
if (tb[index] == NULL) {
tb[index] = new_node;
}
else {
Node * cur = tb[index];
while (cur != NULL) {
// key가 중복이면 값을 바꾸기
if (my_str_cmp(cur->key, key) == 0) {
cur->value = value;
return;
}
cur = cur->next;
}
// 중복이 아니면 앞에다가 추가
new_node->next = tb[index];
tb[index] = new_node;
}
}
bool find(const char * key, int * val) {
int index = hash(key);
Node * cur = tb[index];
// 하나하나 찾아가면서 확인
while (cur != NULL) {
if (my_str_cmp(cur->key, key) == 0) {
*val = cur->value;
return true;
}
cur = cur->next;
}
return false;
}
bool destroy(const char * key) {
int index = hash(key);
// 처음이 비어있는지 확인
if (tb[index] == NULL) {
return false;
}
// 첫번째
if (my_str_cmp(tb[index]->key, key) == 0) {
Node * first = tb[index];
tb[index] = tb[index]->next;
free(first);
return true;
}
// 나머지의 경우
else {
Node * cur = tb[index]->next;
Node * prev = tb[index];
while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return false;
prev->next = cur->next;
free(cur);
return true;
}
}
void print_hash() {
for (int i = 0; i < MAX_TABLE; ++i) {
if (tb[i] != NULL) {
printf("index: %d\n", i);
Node * cur = tb[i];
while (cur != NULL) {
printf("{ %s, %d }, ", cur->key, cur->value);
cur = cur->next;
}
printf("\n");
}
}
}
int main() {
char tmp_key[MAX_KEY];
init();
// Add
printf("Add to hash table\n");
for (int i = 0; i < MAX_DATA; ++i) {
add(keys[i], values[i]);
}
print_hash();
printf("\n");
// Delete
printf("Deleted keys: ");
for (int i = 0; i < DELETE_COUNT; ++i) {
my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
printf("%s ", tmp_key);
destroy(tmp_key);
}
printf("\n");
print_hash();
printf("\n");
// Find
int val;
printf("Found: ");
for (int i = 0; i < FIND_COUNT; ++i) {
my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
if (find(tmp_key, &val)) {
printf("{ %s, %d } ", tmp_key, val);
}
}
printf("\n");
return 0;
}
검증
- hash 함수명이 충돌나서 변경(hash->my_hash)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <map>
#include <string>
#define TOTAL_TEST_CASE 100
#define MAX_TABLE 300 // 테이블 크기
#define MAX_KEY 8 // include null
#define MAX_DATA 2000 // 해시테이블에 넣을 데이터의 수
#define DELETE_COUNT 1000 // 삭제할 데이터의 수
using namespace std;
struct Node {
char key[MAX_KEY];
int value;
Node * next;
};
Node * tb[MAX_TABLE]; // 해시 테이블(해당 인덱스에 리스트로 작성)
char keys[MAX_DATA][MAX_KEY]; // 문자열 key들
int values[MAX_DATA]; // key에 대응하는 값들
void init() {
// 해시테이블 초기화
for (int i = 0; i < MAX_TABLE; ++i) {
Node * cur = tb[i];
Node * tmp;
while (cur != NULL) {
tmp = cur;
cur = cur->next;
free(tmp);
}
tb[i] = NULL;
}
// 랜덤함수를 위한 srand와 seed
srand(time(NULL));
// key에 대응하는 값들 초기화
for (int i = 0; i < MAX_DATA; ++i) {
values[i] = rand() % 100 + 1;
}
// 문자열 key들 초기화
for (int i = 0; i < MAX_DATA; ++i) {
for (int j = 0; j < MAX_KEY - 1; ++j) {
keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
}
keys[i][MAX_KEY - 1] = '\0';
}
}
void my_str_cpy(char * dest, const char * src) {
while (*src != '\0') {
*dest = *src;
dest++; src++;
}
*dest = '\0';
}
int my_str_cmp(const char * str1, const char * str2) {
while (*str1 != '\0' && (*str1 == *str2)) {
str1++;
str2++;
}
return *str1 - *str2;
}
int my_hash(const char * str) {
int hash = 401;
while (*str != '\0') {
hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
str++;
}
return hash % MAX_TABLE;
}
void add(const char * key, int value) {
Node * new_node = (Node *)malloc(sizeof(Node));
my_str_cpy(new_node->key, key);
new_node->value = value;
new_node->next = NULL;
int index = my_hash(key);
// 처음이 비어있으면 할당
if (tb[index] == NULL) {
tb[index] = new_node;
}
// 아니면 하나하나 찾아서 중복이면 치환 아니면 제일 뒤에 추가
else {
Node * cur = tb[index];
while (cur != NULL) {
// key가 중복이면 값을 바꾸기
if (my_str_cmp(cur->key, key) == 0) {
cur->value = value;
return;
}
cur = cur->next;
}
// 중복이 아니면 앞에다가 추가
new_node->next = tb[index];
tb[index] = new_node;
}
}
bool find(const char * key, int * val) {
int index = my_hash(key);
Node * cur = tb[index];
// 하나하나 찾아가면서 확인
while (cur != NULL) {
if (my_str_cmp(cur->key, key) == 0) {
*val = cur->value;
return true;
}
cur = cur->next;
}
return false;
}
bool destroy(const char * key) {
int index = my_hash(key);
// 처음이 비어있는지 확인
if (tb[index] == NULL) {
return false;
}
// 첫번째
if (my_str_cmp(tb[index]->key, key) == 0) {
Node * first = tb[index];
tb[index] = tb[index]->next;
free(first);
return true;
}
// 나머지의 경우
else {
Node * cur = tb[index]->next;
Node * prev = tb[index];
while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return false;
prev->next = cur->next;
free(cur);
return true;
}
}
void print_hash() {
for (int i = 0; i < MAX_TABLE; ++i) {
if (tb[i] != NULL) {
printf("index: %d\n", i);
Node * cur = tb[i];
while (cur != NULL) {
printf("{ %s, %d }, ", cur->key, cur->value);
cur = cur->next;
}
printf("\n");
}
}
}
int main() {
int test_case = 1;
int correct = 0;
for (test_case = 1; test_case <= TOTAL_TEST_CASE; ++test_case) {
init();
bool is_equal = true;
map<string, int> m;
map<string, int>::iterator it;
for (int i = 0; i < MAX_DATA; ++i) {
add(keys[i], values[i]);
}
for (int i = 0; i < MAX_DATA; ++i) {
if (m.count(keys[i]) == 0) {
m.insert(make_pair(keys[i], values[i]));
}
else {
m[keys[i]] = values[i];
}
}
for (int i = 0; i < MAX_DATA; ++i) {
int tmp;
find(keys[i], &tmp);
if (m[keys[i]] != tmp) {
is_equal = false;
}
}
char tmp_key[MAX_KEY];
for (int i = 0; i < DELETE_COUNT; ++i) {
my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
destroy(tmp_key);
m.erase(tmp_key);
}
for (int i = 0; i < MAX_DATA; ++i) {
int tmp = -1;
if (find(keys[i], &tmp) == false && m.count(keys[i]) == 0) {
continue;
}
if (find(keys[i], &tmp) == true && m.count(keys[i]) == 1 && m[keys[i]] == tmp) {
continue;
}
else {
is_equal = false;
}
}
if (is_equal) correct++;
}
printf("Total: %d / %d\n", correct, TOTAL_TEST_CASE);
return 0;
}