hashtable_line_transect.c

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE	10007
#define INPUT_SIZE	5000

typedef struct {
	int id;
	char name[20];
} Student;

// 해쉬테이블 초기화
void init(Student** hashTable) {
	for (int i = 0; i < TABLE_SIZE; i++) {
		hashTable[i] = NULL;
	}
}

// 해쉬테이블 메모리 해제
void destructor(Student** hashTable) {
	for (int i = 0; i < TABLE_SIZE; i++) {
		if (hashTable[i] != NULL) {
			free(hashTable[i]);
		}
	}
}

// 선형 조사법으로 빈 공간 탐색
int findEmpty(Student** hashTable, int id) {
	int i = id % TABLE_SIZE;
	while (1) {
		if (hashTable[i % TABLE_SIZE] == NULL) {
			return i % TABLE_SIZE;
		}
		i++;
	}
}

// 해당 아이디가 존재하는지 
int search(Student** hashTable, int id) {
	int i = id % TABLE_SIZE;
	while (1) {
		if (hashTable[i % TABLE_SIZE] == NULL) return -1;
		else if (hashTable[i % TABLE_SIZE]->id == id) return i;
		i++;
 	}
}

// 해쉬테이블에 추가
void add(Student** hashTable, Student* input, int key) {
	hashTable[key] = input;
}

// 해쉬테이블 키에 대한 값
Student* getValue(Student** hashTable, int key) {
	return hashTable[key];
}

// 테이블 출력
void show(Student** hashTable) {
	for (int i = 0; i < TABLE_SIZE; i++) {
		if (hashTable[i] != NULL) {
			printf("키: [%d] 이름: [%s]\n", i, hashTable[i]->name);
		}
	}
}

int main(void) {
	Student** hashTable;
	hashTable = (Student **)malloc(sizeof(Student *) * TABLE_SIZE);
	init(hashTable);

	for (int i = 0; i < INPUT_SIZE; i++) {
		Student* student = (Student*)malloc(sizeof(Student));
		student->id = rand() % 1000000;
		sprintf(student->name, "사람%d", student->id);
		if (search(hashTable, student->id) == -1) {
			int idx = findEmpty(hashTable, student->id);
			add(hashTable, student, idx);
		}
	}

	show(hashTable);
	destructor(hashTable);
	return 0;
}