Hash 구현

Hash를 구현해보았습니다.

 

Python에는 Dictionary라는 좋은 라이브러리가 있는데, Pro 시험을 위해서라면 직접 구현을 해봐야겠죠?

 

어려우니 주석을 잘 봐주시길 바랍니다.

 

#include <stdio.h>
#include <memory.h>

#define MAX_KEY 64
#define MAX_DATA 128
#define MAX_TABLE 4096

int strcmp(char* data1, const char* data2) {
	int index = 0;

	while (data1[index] != '\0') {
		if (data1[index] == data2[index]) {
			index++;
		}
		else {
			return 1;
		}
	}
	if (data2[index] != '\0') {
		return 1;
	}
	return 0;
}

void strcpy(char* data1, const char* data2) {
	int i = 0, j = 0;
	char* tempData = data1;

	while (data2[i] != '\0') {
		tempData[j++] = data2[i++];
	}
	tempData[j] = '\0';
}

typedef struct {
	char key[MAX_KEY + 1];
	char data[MAX_DATA + 1];
}Hash;

Hash tb[MAX_TABLE];

unsigned long hash(const char* str) { // key가 들어옵니다.
	unsigned long hash = 5381; // 이 수가 아마 소수일겁니다.
	int c;

	while (c = *str++) {
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

int find(const char* key, char* data) { // key랑 data가 들어옵니다.
	unsigned long h = hash(key); // key 값으로 hash function 돌리고
	int cnt = MAX_TABLE;

	while (tb[h].key[0] != 0 && cnt--) {
		if (strcmp(tb[h].key, key) == 0) { // key랑 같은 값이 있으면
			strcpy(data, tb[h].data); // data 변수에 return 값을 넣고
			return 1;
		}
		h = (h + 1) % MAX_TABLE; // 배열 한칸 전진
	}
	return 0; // 없으면 그냥 0을 뱉습니다.
}

int add(const char* key, char* data) { // key랑 data가 들어옵니다.
	unsigned long h = hash(key); // key 값을 넣어서 hash function을 구동합니다.

	while (tb[h].key[0] != 0) { // 이미 key 값이 그 자리를 차리하고 있으면 while 문을 실행합니다.
		if (strcmp(tb[h].key, key) == 0) { // 비교를 했는데 두 문자열이 같으면 0, 왜냐면 동일 key 값을 2개 가질 순 없습니다.
			return 0;
		}
		h = (h + 1) % MAX_TABLE; // 다음 배열로 넘어갑니다.
	}
	strcpy(tb[h].key, key); // key 값에는 key 값 넣고
	strcpy(tb[h].data, data); // data엔 data 넣고
	return 1;
}

int main(void) {
	int T, N, Q;

	scanf("%d", &T);

	for (int test_case = 1; test_case <= T; test_case++) {
		memset(tb, 0, sizeof(tb)); // tb 배열을 0으로 모두 초기화 (채우고자하는 메모리의 시작 포인터, 메모리에 채우고자하는 값, 채우고자 하는 바이트의 수)
		scanf("%d", &N);
		char k[MAX_KEY + 1];
		char d[MAX_DATA + 1];

		for (int i = 0; i < N; ++i) {
			scanf("%s %s", &k, &d);
			add(k, d); // Hash에 넣기 !
		}

		printf("#%d\n", test_case);

		scanf("%d", &Q);

		for (int i = 0; i < Q; ++i) {
			char k[MAX_KEY + 1];
			char d[MAX_DATA + 1];

			scanf("%s", &k);

			if (find(k, d)) { // 찾아봅시다. 없으면 0을 뱉네요
				printf("%s\n", d);
			}
			else {
				printf("not find\n");
			}
		}
	}
	return 0;
}