해시 hash

1. 해시는 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조다

2. 해시를 사용하려면 메모리 공간이 많이 소모되지만, 매우 빠른 속도로 데이터를 처리할 수 있다

 

특정한 값을 찾고자 할 때는 그 값의 키로 접근할 수 있다. 일반적으로 해시 함수는 module 연산 등의 수학적 연산으로 이뤄져 있어 찾고자 하는 값에 O(1)만에 값에 접근할 수 있다. 그러나 수학적 연산으로 나온 결과값이 키가 되는데 아무대로 중복이 발생할 수 있다. 이때 해시에서 충돌이 발생했다고 표현한다

 

해싱 알고리즘은 나눗셈 법이 가장 많이 활용된다. 입력 값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식으로, 테이블의 크기는 소수로 설정하는데 충돌 발생을 줄일 수 있기 때문이다. 충돌을 피하는 것은 불가능한데, 충돌을 처리하는 방법은 다음과 같이 두 가지 유형으로 분류할 수 있다

 

1) 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장하는 선형 조사법, 이차 조사법

2) 해시 테이블의 하나의 버킷에 여러 개의 항목을 저장하는 체이닝 기법

 

1. 선형 조사법

- 충돌이 발생했을 때, 바로 다음 위치를 탐색한다

	#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;
	}

view raw hashtable_line_transect.c hosted with ❤ by GitHub