#5. 해시

해시

 

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

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

3.빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용된다.

 

해시함수는?

 

어떠한 데이터를 암호화시키기에 용이하다.

예를들어,  해시함수를 n mod 5 라하자.

n mod 5는  n을 넣었을때, 5로 나눈 나머지값인데

입력데이터가 

23	오리
16	피자
14	김치
2	나물

이라 한다면  key가

key	값
3	오리
1	피자
4	김치
2	나물

이런식으로 작성된다.

 

특징

 

특정한 값을 찾고자 할 때는 그 값의 키(Key)로 접근할 수 있다.

일반적인 해시함수는 모듈로 연산등 수학적 연산으로 이루어져 있으며, O(1)만에 값에 접근가능하다.

 

또한, 위 데이터에서 만약, 21 -> 콜라  라는 데이터가 추가된다면,

16이라는 피자와 Key 값이 중복 될 수있다.

이렇게 해시 테이블에서 Key가 중복되는 경우 충돌이 발생했다 표현한다.

 

 

알고리즘

 

해싱 알고리즘은 나눗셈 법이 가장많이 활용된다.

입력값을 테이블의 크기로 나눈 나머지를Key로 활용하는 방식이다.

테이블의 크기는 소수로 설정하는것이 효율성이 좋다.(충돌이 적게 일어나게끔)

 

하지만, 아무리 잘 만들었다 하더라도, 해시함수는 충돌이 발생할 수 밖에 없다.

 

충돌처리방법은?

 

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

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

 

 

 

선형 조사법

1	오리
3	김치
13	홍어
23	삼치
33	갈치

위 데이터를 해시함수:(n mod 10)이라 가정했을때,

 

오리와 김치는 겹치지않지만,

 

김치,홍어,삼치,갈치는 모두 충돌이 발생한다.

이를 해결하기위해, 만약 3을 넣은 공간 밑에 자리에 비어있다면, 그 비어있는 곳으로 그다음 데이터인 홍어를 넣어준다.

이를 반복한다.

1	오리
3	김치
4	홍어
5	삼치
6	갈치

 

선형조사법 코드예시

 

 

#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++;  
		//만약 들어갈 값이 차있다면, 1씩 더해서 그다음 공간에 넣는다.
	}
}

//특정한 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 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;  //랜덤한 숫자를100만으로 나눈 나머지를 id로설정
		sprintf(student->name, "사람%d", student->id); 
		if (search(hashTable, student->id) == -1) { //중복되는 ID는 존재하지않도록 함.
			int index = findEmpty(hashTable, student->id);
			add(hashTable, student, index);
		}
	}

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

 

 

결과값:

키: [1] 이름: [사람10008]
키: [8] 이름: [사람8]
키: [10] 이름: [사람20024]
키: [11] 이름: [사람30032]
키: [13] 이름: [사람20027]
키: [14] 이름: [사람10021]
키: [16] 이름: [사람30037]
키: [17] 이름: [사람30038]
키: [20] 이름: [사람30041]
키: [21] 이름: [사람21]
키: [23] 이름: [사람20037]
키: [26] 이름: [사람26]
키: [27] 이름: [사람30048]
키: [28] 이름: [사람28]
키: [30] 이름: [사람30049]
키: [33] 이름: [사람10040]
키: [34] 이름: [사람10041]
키: [39] 이름: [사람39]
키: [40] 이름: [사람40]
키: [41] 이름: [사람20055]
키: [42] 이름: [사람30062]
키: [45] 이름: [사람30066]
키: [47] 이름: [사람20061]
키: [50] 이름: [사람10057]
키: [51] 이름: [사람20065]
키: [53] 이름: [사람53]
키: [58] 이름: [사람20070]
키: [59] 이름: [사람20073]
키: [60] 이름: [사람10067]
키: [64] 이름: [사람20078]
키: [66] 이름: [사람65]
키: [68] 이름: [사람10075]
키: [69] 이름: [사람20083]
키: [70] 이름: [사람20084]
키: [71] 이름: [사람71]
키: [72] 이름: [사람30093]
키: [74] 이름: [사람10080]
키: [75] 이름: [사람30096]
키: [76] 이름: [사람10083]
키: [83] 이름: [사람30104]
키: [85] 이름: [사람30106]
키: [88] 이름: [사람30109]
키: [93] 이름: [사람30114]
키: [96] 이름: [사람10102]
키: [98] 이름: [사람30119]
키: [99] 이름: [사람10106]
키: [101] 이름: [사람101]
키: [105] 이름: [사람10112]
키: [108] 이름: [사람20122]
키: [109] 이름: [사람20123]
키: [110] 이름: [사람20124]
키: [114] 이름: [사람30134]
키: [118] 이름: [사람20130]
키: [120] 이름: [사람119]
키: [122] 이름: [사람20135]
키: [123] 이름: [사람10130]
키: [124] 이름: [사람30145]

.... 이하 생략

 

 

선형 조사법의 단점

 

1.선형 조사법은 충돌이 발생하기 시작하면, 비슷한 값을 가지는 데이터끼리 모이는, 집중결합 문제가  존재한다.

->해시테이블의 크기가 엄청 크다면(메모리소모량증가) 충돌이 적게 발생하므로, 빠르게 데이터에 접근할 수 있다.

-->하지만, 보통은 해시테이블의 크기가 한정적이므로 충돌이 최대한 적게 발생하도록해야한다.

 

이를 보안하기 위해선?

이차 조사법

 

키값을 완전제곱수로 더해 나가는 방식이다.

 

만약, 키값이 5인데 차있을 경우  6에다 넣고, 또 키값이 5가 들어온다면, 선형조사법처럼 7이아니라,  2의제곱인 4칸 뒤인 9에 넣는다.

 

-->데이터가 뭉쳐있는 현상을 방지한다.

 

체이닝

 

연결리스트를 활용해 특정한 키를 가지는 항목들을 연결해 저장한다.

연결리스트를 사용하니-> 삽입,삭제가 간편하다.

테이블크기 문제 또한,  동적할당을 통해 쉽게 해결가능하다.

->동적 할당을 위한 추가적인 메모리 공간이 소모된다는 단점이 있다. (연결리스트의 구조적 단점)

체이닝 기법은, 키값 충돌이 발생하면,  그냥 그 키값에 전부 데이터를 넣는다.

 

 

체이닝 코드예시

 

#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;  
	//해당테이블이 NULL -> 존재하지않는다 -> 0반환
	else {
		Bucket* cur = hashTable[i];
		while (cur != NULL) {
			if (cur->data->id == id) return 1; 
			//해당키에 해당하는 연결리스트를 하나하나확인하면서 존재하면 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() % 100000;
		sprintf(student->name, "사람%d", student->id);
		if (!isExist(hashTable, student->id)) {
			add(hashTable, student);
		}
	}

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

결과값

 

키: [1] 이름: [사람10008]
키: [8] 이름: [사람8]
키: [10] 이름: [사람20024]
키: [11] 이름: [사람30032]
키: [13] 이름: [사람20027]
키: [14] 이름: [사람10021]
키: [16] 이름: [사람30037]
키: [17] 이름: [사람30038]
키: [20] 이름: [사람30041]
키: [21] 이름: [사람21]
키: [23] 이름: [사람20037]
키: [26] 이름: [사람26]
키: [26] 이름: [사람20040]
키: [27] 이름: [사람30048]
키: [28] 이름: [사람30049]
키: [28] 이름: [사람10035]
키: [28] 이름: [사람28]
키: [29] 이름: [사람10036]
키: [33] 이름: [사람10040]
키: [34] 이름: [사람10041]
키: [39] 이름: [사람39]
키: [39] 이름: [사람20053]
키: [40] 이름: [사람40]
키: [41] 이름: [사람30062]
키: [41] 이름: [사람10048]
키: [41] 이름: [사람20055]
키: [41] 이름: [사람41]
키: [42] 이름: [사람42]
키: [45] 이름: [사람30066]
키: [47] 이름: [사람20061]

 

위를 보면, 동일한 키값데이터가 존재하는걸 확인 할 수있다.

 

 

 

해시는 이론적으로 데이터삽입과 삭제에 있어서O(1)의 시간복잡도를 가진다.

데이터베이스 인덱싱 및 정보보안관련 모듈에서 많이 사용된다.