끄적끄적

해쉬 테이블

검색, 삽입, 삭제 모두가 다 O(1)인 엄청난 녀석이다.

삽입, 삭제가 O(1)이면 검색이라도 O(N)이 되어야 되는데 어떻게 모두가 다 O(1)일까?

검색이 O(1)이란 말은 인덱싱을 사용할 수 있다는 말이다.

가장 작은값 0부터 가장 큰 값 793까지의 배열을 만들고(총 794개) 값을 입력하면 1로 비어있으면 0으로 세팅한다.

이렇게 되면 입력할때 O(1)이 되고 검색할때도 인덱스를 사용할 수 있으니 O(1)이 된다. 이렇게 사용하지도 않은 메모리를 너무 많이 사용한다는 단점이 있다. 말그대로 무식 그자체다.

덜 무식하게

무식하게 모든 범위의 메모리를 잡아 두지말고 임의의 숫자에 메모리 인덱스를 매핑 시키면 좀 더 아름다워진다.

배열의 크기가 10이라고 가정하고 숫자에 메모리 인덱스를 매핑 시키는 방법은 간단하게 10으로 나눈후 나머지를 인덱스값으로 세팅하면 된다.

여기서 중요한 점은 중복이 발생한다는 점이다. 703이나 793이나 나머지는 3으로 똑같다. 이미 3번 인덱스에는 703이 들어가있는데 793의 값이 들어오면 덮어 쓸수도 없고 난감해진다. 중복을 제거해보자.(물론 불가능)

배열의 크기도 충분히 늘리고(2배) 나누는 값을 소수로 두면 중복을 최소화 할 수 있다. 하지만 중복을 막을 순 없다 중복이 하나라도 발생한다면 데이터의 신뢰성이 보장 될 수 없다. 어떻게 하면 좋을까?

중복 제거(불가능)

원칙은 나머지값의 인덱스에 값을 넣으면 되지만, 이미 그 인덱스에 값이 존재한다면(충돌) 가장 인접해 있는 빈 공간에 값을 넣으면 된다. 즉 색인을 1씩 증가 시키면서 빈 공간을 찾다가 비어 있으면 넣는다는 말이다. 물론 이때는 자신의 나머지 값을 인덱스로 같지 않는다.

일단 배열을 만들면 절대 사용하지 않을 값 INT_MIN으로 초기화 한 뒤 자신의 인덱스에 해당하는 배열에 값을 넣는다.

1. 793을 11인덱스에 넣는다

2. 724를 11인덱스에 넣으려고 한다. 하지만 793이 이미 있다

3. 인덱스를 1증가 시키면서 빈공간을 찾은뒤 가장 가까운 빈공간에 넣는다.(12 인덱스에 넣음)

4. 계속 반복

코드

#include <limits.h>

#define	BUCKET_SIZE (23)
int s_numbers[BUCKET_SIZE];

void init_hashtable(void)
{
	size_t i;

	for (i = 0; i < BUCKET_SIZE; i++)
	{
		s_numbers[i] = INT_MIN;
	}
}

int has_value(int value)
{
	int i;
	int start_index;

	start_index = value % BUCKET_SIZE;
	i = start_index;

	do
	{
		if (s_numbers[i] == value) {
			return true;
		}
		else if (s_numbers[i] == INT_MIN) {
			return false;
		}

		i = (i + 1) % BUCKET_SIZE;

	} while (i != start_index);

	return false;
}

int add(int value)
{
	int i;
	int start_index;

	start_index = value % BUCKET_SIZE;
	i = start_index;
	do
	{
		if (s_numbers[i] == value || s_numbers[i] == INT_MIN)
		{
			s_numbers[i] = value;
			return true;
		}
		i = (i + 1) % BUCKET_SIZE;
	} while (i != start_index);
	
	return false;
}

int main()
{
	init_hashtable();

	add(703);
	add(793);
	add(724);
	add(441);
	add(219);
	add(1);
	add(81);
	add(546);
	add(777);
	add(747);

	return 0;
}