[C언어] 해쉬(hash) 이해하기

#define BK 10
#define SL 1
int hashtable[BK][SL];

int hash(int key)
{
	return key % 10;
}
 
void AddKey(int key)
{
	int bucket;

	bucket = hash(key);
	if(hashtable[bucket][0] == 0)hashtable[bucket][0] = key;
}
 
int FindKey(int key)
{
	int bucket;

	bucket = hash(key);
	return (hashtable[bucket][0] == key);
}
 
void main()
{
	int i, key;
 
	memset(hashtable, 0, sizeof(hashtable));
	for (i = 0; i < 5; i++)
	{
		printf("%d번째 값을 입력하세요 : ", i + 1);
		scanf("%d", &key);
		AddKey(key);
	}
	printf("검색할 키를 입력하세요 : ");
	scanf("%d", &key);
	if (FindKey(key))
	{
		puts("검색되었습니다.");
	}
	else
	{
		puts("입력하신 값은 없습니다..");
	}
}

프로그램 실행화면

해쉬는 처음 저장할 때부터 검색하기 좋게 저장한다. 그래서 검색 알고리즘이라기 보다는 저장 알고리즘에 더 가깝다고 볼 수 있다.

방법은 복잡해 보이지만 이해하면 엄청 쉽다. 위에 있는 프로그램으로 설명을 하자면 입력받은 값을 저장하기 위한 2차원 배열을 선언한다.

이 배열은 구조체가 될수도 있고 여러 타입으로 선언이 가능하다. 프로그램 실행화면에서 8일 제일 먼저 입력 받았다.

hash() 함수에서 하는 일은 이 입력 받은 값을 10으로 나눈 나머지를 구하는 것이다. 어떤 수이든 1의 자리가 남게 된다. 그러면 모든 수는 0~9의 숫자가 생기게 된다.

그럼 이 수를 이용해 hashtable[0~9][n]에 넣어주는 것이다. 여기서 n은 이미 저장된 갯수를 말한다. 만약 이 n때문에 범위를 초과하면 어떻게 될까?

해쉬(hash)의 가장 큰 단점이 이것이다. 값은 key값을 가지는 입력이 여러 번 들어오게 되면 금방 범위를 초과해 버린다.

그래도 엄청 빠르게 검색할 수 있다는 장점 때문에 자주 사용하고 또 이 해쉬를 지원해 주는 함수도 많다.