[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()라고 했을 때 서로 다른 문자열 s1s2에 대해서 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)

  • keyvalue로 된 쌍을 저장하는 자료구조이다.
  • 아래 사진처럼 Lisa Smith라는 key521-8976value를 저장할 수 있도록 설계된 자료구조입니다.
  • 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;
}


참고자료

[Docker] 도커(Docker) 이미지 이름과 태그 목록 가져오기

> 도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Docker- awk, tail 명령어## 도커(Docker...… Continue reading