해시

해시의 개념

• 해시는 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다.
• 해시는 검색방법이라기보다는 자료관리 기법이다.
• 쉬운 예로 실생활의 주소록을 생각하면 된다. 주소록은 가나다 순으로 페이지를 미리 분류하고 이름의 첫 글자를 기준으로 주소를 적는다.
• 주소록처럼 찾기 쉽게 인덱싱을 만들어놓은 형태를 해싱( (hasing)이라고 한다.
  

해싱의 기본 동작은 새 데이터가 새로 입력되면, 가장 먼저 어떤 버킷에 넣을 것인지 결정해야 하는데 이 연산을 하는 기능이 해시알고리즘이다.
특정 데이터를 검색시에도 해시알고리즘 기능을 사용하면 어떤 버킷에서 찾을 것인지 결정되기 때문에 빠르게 검색할 수 있다.

해시 테이블

• 자료가 저장되는 전체 저장소를 해시 테이블(Hash Table)이라고 한다.

• 해시 테이블은 여러 개의 버킷(Bucket)으로 나누어지는데, 주소록의 ㄱ,ㄴ,ㄷ,ㄹ과 같은 인덱스 페이지가 버킷이다.

• 버킷은 여러 개의 슬롯으로 구성되어 있는데, 슬롯은 버킷에 데이터가 저장되는 단위이다. 즉, 주소록에서 한 명의 주소를 적는 칸의 단위라고 보면 된다.

해시테이블의 형태 : 2차원 배열 (표)

해시 함수

• 해싱의 기초적인 연산은 자료가 새로 입력될 때 이 자료를 어떤 버킷에 넣을지 결정하는 것인데, 이를 해시 함수라고 한다.

• 해시 함수는 입력된 키 값으로 버킷의 번호를 찾아내는 함수이다.

• 주소록의 경우 이름의 첫 글자 자음으로 버킷 번호를 찾는다. (ex, 김 아무개는 ㄱ칸, 이 아무개는 ㅇ칸, 장 아무개는 ㅈ칸)

• 이러한 원리를 이용하여 해시 함수를 만들어보자.

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

#define BK 10
#define SL 1

void insertValue(int key);
bool findValue(int key);

int hashtable[BK][SL];

void main()
{
	int data = 0;
	memset(hashtable, 0 , sizeof(hashtable));

	printf("키를 5개 입력하세요.\n");

	for (int i = 0; i < 5; i++)
	{
		printf("%d번째 값을 입력하세요 : ", i + 1);
		scanf_s("%d", &data);

		insertValue(data);

	}
	
	printf("검색할 키를 입력하세요.\n");
	scanf_s("%d", &data);

	bool search = findValue(data);
	if (search)
	{
		printf("검색되었습니다.\n");
	}
	else
	{
		printf("안 검색되었습니다.\n");
	}
}

int Hash(int key)
{
	int rest = key % 10 ;
	return rest;
}

void insertValue(int key)
{
	int bucket = Hash(key);
	printf("bucket : %d\n", bucket);
	if (hashtable[bucket][0] == 0)
	{
		hashtable[bucket][0] = key;
		printf("hashtable : %d\n", hashtable[bucket][0]);
	}
}

bool findValue(int key)
{
	int bucket = Hash(key);
	if (hashtable[bucket][0] == key)
	{
		return true;
	}
	else
	{
		return false;
	}
}

• 해시함수 Hash는 키의 마지막 자리 수 하나만으로 해시값을 계산한다. % 연산자 사용
• InsertValue 함수는 hash 함수를 호출하여 해시값을 찾고 이 버킷이 비어있을 때 해시 테이블에 데이터를 추가한다. 이미 버킷이 점령되어있다면 값을 추가할 수 없다.
• FindValue 함수는 키가 해시 테이블에 있는지만 조사하여 값과 키값을 비교한 결과를 리턴한다.

해싱의 문제점

• 가장 큰 문제는 버킷끼리 충돌할 수 있다는 점이다.
• 새로 삽입하고자 하는 키의 버킷이 이미 점령되어 있다면 이 키는 해시 테이블에 추가할 수 없다.
  (ex. 38이 8번 버킷에 들어있다. 48이나 58이 입력되면 저장할 버킷이 없다.)
• 이러한 상황을 충돌이라고 한다. 이러한 충돌을 해결하는 것이 해싱의 관건이다.
• 해결 방법으로 다중 슬롯, 선형 탐색, 재해시 등의 방법들이 있다.

다중 슬롯

• 슬롯의 크기를 크게 잡기만 해도 충돌을 많이 완화시킬 수 있다.
• InsertValue 함수에서 슬롯 크기만큼 루프를 돌며 빈자리를 찾아 새로운 키를 삽입하도록 수정한다.

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

#define BK 10
#define SL 3

void insertValue(int key);
bool findValue(int key);

int hashtable[BK][SL];

void main()
{
	int data = 0;
	memset(hashtable, 0 , sizeof(hashtable));

	printf("키를 5개 입력하세요.\n");

	for (int i = 0; i < 5; i++)
	{
		printf("%d번째 값을 입력하세요 : ", i + 1);
		scanf_s("%d", &data);

		insertValue(data);

	} 

	printf("검색할 키를 입력하세요.\n");
	scanf_s("%d", &data);

	bool search = findValue(data);
	if (search)
	{
		printf("검색되었습니다.\n");
	}
	else
	{
		printf("안 검색되었습니다.\n");
	}
}

int Hash(int key)
{
	int rest = key % 10 ;
	return rest;
}

void insertValue(int key)
{
	int bucket = Hash(key);
	printf("bucket : %d\n", bucket);
	
	for (int i = 0; i < SL; i++)
	{
		if (hashtable[bucket][i] == 0)
		{
			hashtable[bucket][i] = key;
			printf("hashtable : %d\n", hashtable[bucket][0]);
			break;
		}
	}
}

bool findValue(int key)
{
	int bucket = Hash(key);
	for (int i = 0; i < SL; i++)
	{
		if (hashtable[bucket][i] == key)
		{
			return true;
		}
	}
	return false;
}
``