09.해시

해시의 정의

• Hash는 데이터를 최대한 빠른 속도로 관리하도록 돕는 자료구조
• 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터 처리
• 데이터베이스 등에 활용

해시의 동작

• 특정한 값(Value)을 찾고자 할 때 그 값의 키(Key)로 접근 가능
• 해시 함수는 Modulo 등의 수학 연산으로 O(1)만에 값에 접근 가능

입력 값의 modulo 연산을 취한 값을 키로 설정할 때 분포

해시의 충돌

• 해시 함수를 거쳐 생성되는 키는 한정적이기에 키 중복 발생 가능
• 해시 테이블에서 키가 중복되는 경우를 충돌이 발생했다고 함

해싱

• 해싱 알고리즘은 나눗셈 법(Division Method)이 가장 많이 활용
• 입력 값을 테이블 크기로 나눈 나머지를 키로 이용

테이블 크기는 소수(Prime Number)로 설정하는 것이 효율적

충돌 처리법

1. 충돌을 발생시키는 항목을 해시테이블의 다른 위치에 저장
   --> 선형조사법, 이차조사법 등
2. 해시테이블의 하나의 버킷에 여러 개의 항목을 저장
   -->체이닝(Chaining) 등

선형 조사법

해당 키에 값이 있으면 다음 키로 넘어가서 확인 후 비어있을 때 삽입

선형 조사법의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.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++;
	}
}

// 특정 ID 값에 매칭되는 데이터를 해시 테이블에서 탐색
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 1;
		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 index = findEmpty(hashTable, student->id);
			add(hashTable, student, index);
		}
	}

	show(hashTable);
	destructor(hashTable);
	system("pause");
	return 0;
}

선형 조사법의 단점

선형 조사법은 충돌이 발생하기 시작하면 유사값을 가지는 데이터끼리 서로 밀집되는 집중 결합 문제가 존재함. 일반적으로 해시 테이블의 크기가 한정적이기 때문에 충돌을 최소화 해야 함

이차 조사법

• 선형 조사법을 약간 변형한 형태로 해당 키가 선점되었다면 '완전 제곱수'를 더해가는 방식

조사법의 테이블 크기 재설정

일반적으로 선형 조사법, 이차 조사법 등의 조사법에서 테이블이 가득 차게 되면 테이블의 크기를 확장하여 계속해서 해시 테이블을 유지 할 수 있도록 함

체이닝

• Chaining 기법은 연결 리스트를 활용해 특정한 키를 가지는 항목들을 연결해 저장
• 삽입과 삭제가 용이
• 테이블 크기 재설정 문제는 '동적 할당'을 통해 쉽게 해결

체이닝의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TABLE_SIZE 10007
#define INPUT_SIZE 5000

// 구조체 정의
typedef struct {
	int id;
	char name[20];
} Student;

// 버킷 정의
typedef struct {
	Student* data;
	struct Bucket* next;
} Bucket;

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

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

// 체이닝 데이터 탐색
int isExist(Bucket** hashTable, int id) {
	int i = id % TABLE_SIZE;
	if (hashTable[i] == NULL) return 0;
	else {
		Bucket* cur = hashTable[i];
		while (cur != NULL) {
			if (cur->data->id == id) return 1;
			cur = cur->next;
		}
	}
	return 0;
}

// 특정 키 인덱스에 데이터 삽입
void add(Bucket** hashTable, Student* input) {
	int i = input->id % TABLE_SIZE;
	if (hashTable[i] == NULL) {
		hashTable[i] = (Bucket*)malloc(sizeof(Bucket));
		hashTable[i]->data = input;
		hashTable[i]->next = NULL;
	}
	else {
		Bucket* cur = (Bucket*)malloc(sizeof(Bucket));
		cur->data = input;
		cur->next = hashTable[i];
		hashTable[i] = cur;
	}
}

// 해시 테이블에 존재하는 모든 데이터 출력
void show(Bucket** hashTable) {
	for (int i = 0;i < TABLE_SIZE;i++) {
		if (hashTable[i] != NULL) {
			Bucket* cur = hashTable[i];
			while (cur != NULL) {
				printf("키 : [%d] 이름 : [%s]\n", i, cur->data->name);
				cur = cur->next;
			}
		}
	}
}

// 체이닝 해시 테이블에 적용
int main(void) {
	Bucket** hashTable;
	hashTable = (Bucket**)malloc(sizeof(Bucket) * 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 (!isExist(hashTable, student->id)) { // 중복되는 ID는 존재하지 않도록
			add(hashTable, student);
		}
	}

	show(hashTable);
	destructor(hashTable);
	system("pause");
	return 0;
}

해시는 데이터 삽입과 삭제 시 O(1)의 시간복잡도를 가짐
데이터베이스 인덱싱 및 정보보안 모듈 등에서 다양하게 활용