[Algorithms] Hash

 

[Algorithms] Hash

해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다.
즉 해쉬 알고리즘은 해쉬를 하는 방법에 대해 절차적으로 명세한다.

이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.
기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비해, 
해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.


1. Direct Addressing Table

 

 

 

 

Direct Addressing Table은 key-value쌍의 데이터를 배열에 저장할 , key값을 직접적으로 배열의 인덱스로 사용하는 방법이다.
예를 들면 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.
똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는, 각 키마다 자신의 공간이 존재하므로 그 위치에다 저장을 하면 되고, 
삭제 시에는 해당 키의 위치에 NULL값을 넣어주면 된다.탐 색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.
찾고자 하는 데이터의 key만 알고있으면 즉시 위치를  찾는 것이 가능하므로 탐색,저장,삭제,갱신은 모두 선형시간인 O(1)로 매우 빠른 속도로 처리가 가능하다.
다만 key값의 최대 크기만큼 배열이 할당 되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.




2. Hash Table

Hash Table은 key-value 쌍에서 key값을 테이블에 저장할 때, Direct Addressing Table 달리 key값을 함수를 이용해 계산을 수행 한 후,
그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key값을 계산 하는 함수는 해쉬 함수(Hash Function)이라고 부르며,
해쉬 함수는 입력으로 key를 받아, 0부터 배열의크기-1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로 변환 시킨 것이다.
이 경우 k값이 h(k)로 해쉬되었다고 하며, h(k)는 k의 해쉬값이라고 한다.

 

 

2.1 충돌(Collusion)

하지만 해쉬 테이블은 '충돌'이 일어 날 수 있다는 큰 문제점이 있다. 충돌이란, 다른 k값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 경우를 말한다.
예를 들자면 k1과 k12을 해쉬하였더니 h(k1) = h(k12)인 경우를 들 수 있다. Direct Addressing Table에서는 이를 방지 하기 위해 모든 key값이 다르다고 전제하였지만
해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.
하지만 해쉬 함수를 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기는 힘드므로, 충돌을 방지하기 위한 방법으로
충돌을 어느정도 허용하되 이를 최소화 하는 방법도 사용하기도 한다..


2.1.1 Chaining 방법 - 충돌을 허용하되 최소화 하는 방법

충돌을 허용하지만 이를 최소화 하기 위한 방법중 하나인 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해쉬 테이블에선 동일한 해쉬값이 출력되 충돌이 일어나면, 그 위치에 있던 데이터에 key값을 포인터로 뒤이어 연결한다.
따라서 최초로 h(k)위치에 저장된 데이터를 시작으로 그 이후의 h(k)값이 출력되는 데이터는 모두 연결 리스트의 형태를 취한다.
그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다. 
Chaing 방법에서의 수행시간은 삽입 시에는 해쉬값을 이용해 바로 slot에 저장하면 되므로 상수시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색 시에는 연결리스트를 따라 가기 때문에 리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 저장됬을 경우엔 연결리스트의 탐색 시간과 동일한 선형시간을 가지게 된다.

 

예제

아래 예제는 해시 함수를 활용한 코드이며 Shift 연산과 소수 값(5381)을 활용 한 예제 코드이다.

최대 HASH Table 보다 작은 값의 Index를 반환 해야 하므로 % MAX_TABLE 값으로 나누어 준다.

 

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

#define MAX_KEY 64   // Key의 String 길이 최대 64
#define MAX_DATA 128 // Data의 String 길이 최대 128
#define MAX_TABLE 4096  // Hash Table의 최대 크기

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

 

Hash Code 출처 : ggodong.tistory.com/89