TWpower Reading time ~1 minute

MailReminder 프로젝트 개발기


목차


회고

  • 리눅스 기본 crontab을 이용해서 특정 시간에 원하는 코드가 실행되도록 만들었으며 그 코드가 실행되면 내 구글계정을 이용해 원하는 메일에 메일을 보내도록 해놓았다.


목표

  • 저번에는 도장에 가는 일정만 추가했는데 이번에는 사내 근골격 센터를 예약하는 작업을 추가해보려 한다.
  • 매주 있는게 아니기 때문에 필요할 때 알림기능을 on/off를 하고 싶다.
  • 도장 알림 같은 경우에는 매달 특정한 시간에 알림이 오도록하고 근골격 센터 예약은 알림을 등록하고 1달 후에 알림이 오게 하고 싶다.(결국, 이 부분을 crontab을 이용했기 때문에 하지 못했다…)


환경 및 구조

on/off의 기능

  • on/off의 기능은 shell script를 실행해서 crontab의 내용을 수정하도록 하려고 한다.
  • jupyter notebook을 통해서 원격으로 접속해서 쉘을 실행할 수 있기 때문에 쉘 스크립트의 실행을 통해 on/off 기능을 구현하려 한다.
  • 간단하게 보면 파일이 on_smc_physiotherapy.sh라는 파일이 있고 이걸 실행하면 crontab의 내용을 변경하는 방식이라 볼 수 있다.


방법 설명

  • crontab에 근골격 센터의 일정 알림을 추가하는 방법은 아래와 같다.
  • 시작할 때 PATH를 프로젝트 폴더로 잡아주고 일정이 이미 추가되어있는 smc_on_in_text 파일의 내용을 crontab에 입력으로 넣어주었다.

on_smc_physiotherapy.sh

#/bin/bash

cd /home/twpower/MailReminder
crontab smc_on_in_text

smc_on_in_text

...
# 환경 변수들 목록 쫘르륵
...

0 10 17 * * python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt
50 10 * * 3 python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt


코드 구현

  • 메일을 보내는 reminder.py는 저번과 같다.
  • off_smc_physiotherapy.sh, on_smc_physiotherapy.sh, smc_off_in_text, smc_on_in_text이 추가되었다.


메인 구현 부분

off_smc_physiotherapy.sh

#/bin/bash

cd /home/twpower/MailReminder
crontab smc_off_in_text

on_smc_physiotherapy.sh

#/bin/bash

cd /home/twpower/MailReminder
crontab smc_on_in_text

smc_off_in_text

...
# 환경 변수들 목록 쫘르륵
...

0 10 17 * * python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt

smc_on_in_text

...
# 환경 변수들 목록 쫘르륵
...

0 10 17 * * python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt
50 10 * * 3 python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt


반성

  • 결국 생각해보니 crontab은 일정 주기로 반복하는 작업을 도와주는 기능이어서 내가 등록하고 나서 1달 후 특정 요일에 알람이 오도록 하는건 힘든 일이었다… 나중에 프레임워크를 쓰거나 다른 라이브러리를 알아보는 방향으로 가야할거 같다.
  • 그래서 결국 매달 수요일에 하는거로 일단 구현을 하였다.


다음 목표

  • 일단, 메일은 잘 오는걸 확인했는데 2가지 문제가 있었다..
  • 첫째, 메일이 너무 많이 와서 알림 메일이 와도 메일 알림을 닫아버리면(안드로이드의 경우) 알림이 왔는지 알 수가 없다. 결국, 애초에 의도한 기능을 제대로 하지 못한다는것!
  • 둘째, on/off하기가 너무 불편하다. UI가 있으면 좋겠다.
  • 첫째와 둘째를 모두 구현하기란 쉽지 않기 때문에… crontab과 별개로 특정 시점부터 얼마가 지난후에 알림이 올 수 있도록 하는 부분을 찾아봐서 추가해야겠다.


참고자료

TWpower Reading time ~1 minute

cat 명령어를 통해서 여러 줄을 입력하는 방법을 알아보자

환경 및 선수조건

  • Linux
  • Bash shell(/bin/bash)


cat 명령어

  • cat: 파일들을 인자로 받아서 해당 파일들을 연결해 표준출력으로 출력합니다.
  • 간단히 말해 들어오는 파일명들의 파일 내용을 쉘 화면에 출력해주는 명령어입니다.


예시 및 사용법

  • 사용법: cat [OPTION]... [FILE]...
  • 옵션들은 아래 참고자료에 있는 링크에 가시면 볼 수 있습니다.

$ echo "Test Document" >> test.txt
$ cat test.txt # cat 명령어의 기본 사용법
Test Document


cat을 이용해 여러 줄 입력하기

  • cat 다음에 <<를 쓰고 원하는 표시자를 씁니다. 아래의 경우에는 EOF를 사용하였는데 다른 단어를 사용해도 됩니다. 단, 처음에 사용한 단어가 끝에도 같아야 합니다. 여기에 EOF를 사용했기 때문에 마지막에 입력을 끝내려면 똑같이 EOF를 입력하면됩니다.
  • 이러한 부분을 Here-Document라고 하는데 자세한 내용은 http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_07_04에 나와있습니다.

$ cat << EOF
> This
> is
> multiline test
> EOF
This
is
multiline test
$


cat을 이용해 여러 줄을 파일로 생성하기

  • Here-Document와 Redirection의 응용입니다.
  • stdin을 cat 명령어로 받고 Redirection를 통해서 파일에 stdout의 내용을 출력합니다. 어려우면 그냥 아래처럼 사용하셔도 무방합니다!!
  • 개행문자를 포함해서 파일에 쓰고 싶을 때 아래처럼 사용합니다.
  • Redirection에 관해서는 Redirect와 Pipe의 차이를 참고하세요.

$ # 아래와 같습니다
$ cat << EOF > test.txt
> This
> is
> multiline file write
> EOF
$ cat test.txt
This
is
multiline file write
$



$ # 아래와 같습니다
$ cat > test_another.txt << EOF
> Another
> multiline text to file test
> EOF
$ cat test_another.txt
Another
multiline text to file test
$


참고자료

TWpower Reading time ~1 minute

MailReminder 프로젝트 개발기


목차


개발 시작 이유

  • MailReminder라는 이름부터 즉흥적으로 지었는데… 일을 시작하고 살다보니까 도장비 입금이나 병원 신청같은 부분을 매달 알려줬으면 좋겠는데 단순한 일이라서 캘린더에는 추가하기 싫고 메일로 알림을 받으면 좋을거 같아서 개발을 시작하게 되었다.


목표

  • 최종적으로는 어떤 모습이 될지는 모르겠으나… 내가 원하는 날짜에 알림을 신청하면 메일로 알려주는 서비스를 나를 위해 만들고 싶다.
  • 추후 모습이 바뀔수도 있고 현재 내 요구사항은 등록한 사항을 원하는 날짜에 알려주자!
  • 스스로 애자일과 린 소프트웨어 개발론을 통해 개발할 예정! 물론, 나중에 개발 방법이 어떻게 바뀔지는 모르겠지만.. 우선 만들고 싶은 한 가지의 목표를 정하고 구현하고 불편한거 개선해서 추가하고 하는 방식으로 가보자


환경 및 구조

방법 설명

  • 메일을 보내주는 부분은 python을 이용해서 작성한다.
  • 리눅스에 있는 crontab을 이용해서 원하는 날짜에 메일을 보내도록 한다.
  • 메일을 보내주는 부분은 직접 smtp 서버를 만들고 도메인에 붙일수도 있지만… 빠른 개발을 위해서 우선 Google에 계정을 만들고 해당 계정으로 메일을 보내도록 했다.(최소한으로 필요한 부분을 제외하고 다른 부분들은 다 쓸 수 있는걸 가져다가 쓰자!)
  • 잘 보내졌는지 확인하기 위해 로그를 남겼습니다.(stdout으로 나오게 하고 파일로 redirection함)


코드 구현

공통

  • 계정 정보를 저장하는 account.json의 경우에는 개인 정보이니 .gitignore에 추가했다.


메인 구현 부분

reminder.py

import smtplib
from email.mime.text import MIMEText
import json
import datetime

def sendMail(sender_email, receiver_email, app_password ,msg):
    smtp = smtplib.SMTP_SSL('smtp.gmail.com', 465)
    print(str(datetime.datetime.now()) + ": " + "Access Success")
    smtp.login(sender_email, app_password)
    print(str(datetime.datetime.now()) + ": " + "Login Success")
    msg = MIMEText(msg)
    msg['Subject'] = '리마인더'
    smtp.sendmail(sender_email, receiver_email, msg.as_string())
    print(str(datetime.datetime.now()) + ": " + "Sending Success")
    smtp.quit()

email=""
app_password=""
with open('/home/twpower/MailReminder/account.json') as account_json_file:
    account = json.load(account_json_file)
    email = account['email']
    app_password = account['app_password']
    print(str(datetime.datetime.now()) + ": " + "Parsing Success")

# 나한테 보내는 메일 정보는 없음... 개인정보라서
sendMail(email, '', app_password, "입금 or 예약")

crontab

# 쉘은 bash를 사용했고 환경 변수들을 다 가져왔습니다.(PATH를 포함!)
# 환경 변수를 가져와야 일반적인 쉘과 환경이 같아지며 python 경우에는 사용하는 인터프리터 path 정보가 거기에 담겨 있기 때문에 가져오는게 좋습니다.(처음에 안해줘서 자꾸 오류떴던...)
...
* 10 17 * * python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt
...


다음 목표

  • 우선 사용이 잘 되면 api를 통해서 on/off를 할 수 있는 기능을 만들어보고 싶다. 필요없을 때 서버에 들어가서 끄기는 귀찮으니…


참고자료

TWpower Reading time ~1 minute

Python에서 JSON 파일을 읽어서 파싱해보자


환경 및 선수조건

  • Python(3.X)


with문과 json 모듈을 이용해서 파싱

  • with문과 json모듈을 이용하면 dictionary로 쉽게 사용이 가능하다.
import json # import json module

# with statement
with open('json file path or name') as json_file:
    json_data = json.load(json_file)

    ...


예제

example.json

{
    "json_string": "string_example",
    "json_number": 100,
    "json_array": [1, 2, 3, 4, 5],
    "json_object": { "name":"John", "age":30},
    "json_bool": true
}


example.py

import json

# with를 이용해 파일을 연다.
# json 파일은 같은 폴더에 있다고 가정!

with open('example.json') as json_file:
    json_data = json.load(json_file)

    # 문자열
    # key가 json_string인 문자열 가져오기
    json_string = json_data["json_string"]
    print(json_string)

    # 숫자
    # key가 json_number인 숫자 가져오기
    json_number = json_data["json_number"]
    print(str(json_number)) # 숫자이기 때문에 str()함수를 이용

    # 배열
    # key가 json_array인 배열 가져오기
    json_array = json_data["json_array"]
    print(json_array)

    # 객체
    # key가 json_object인 객체 가져와서 만들기
    # json object의 경우에 python ojbect로 바꿀때는 따로 처리를 해줘야합니다.
    # 기본형은 dictionary입니다.
    json_object = json_data["json_object"]
    print(json_object)

    # bool형
    # key가 json_bool인 bool형 자료 가져오기
    json_bool = json_data["json_bool"]
    print(json_bool)


참고자료

TWpower Reading time ~12 minutes

업데이트(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;
}


참고자료