해시 #2

선형 탐색

• 슬롯이 넉넉하고 해시 함수가 정교해도 언제나 충돌 가능성은 있다.
• 선형 탐색법은 충돌이 발생할 경우 이 데이터를 버리지 않고 다른 버킷에 대신 집어 넣는 방법이다.
• 대체 버킷을 찾는 가장 간단한 방법은 바로 옆칸에 적어놓는 것이다.
• 주소록의 경우 ㄱ 칸이 모자라면 ㄴ 칸을 잠시 빌려쓰도록 하는 것이다.
  
• 입력된 데이터의 버킷 번호를 조사하여 데이터를 넣되 이 버킷이 비어있지 않다면 다음 버킷을 조사한다.
• 만약 다음 버킷이 비어있지 않다면 그 다음 빈 버킷을 계속해서 찾아 빈 버킷에 값을 써 넣는다.

내 생각
hashtable[bucket][0]에 값이 존재한다면 [bucket+i][0]에 대입하게 하면 되지 않을까?

void insertValue(int key)
{
	int bucket = Hash(key);

		while (hashtable[bucket][0] != 0)
		{
			bucket = bucket + 1;
		}
		hashtable[bucket][0] = key;

}
bool findValue(int key)
{
	int bucket = Hash(key);

	while (hashtable[bucket][0] != 0)
	{
		if (hashtable[bucket][0] == key)
			return true;

		bucket = bucket + 1;
	}
	return false;
}

맞다. 그런데 for문이 아니라 while문을 이용한다!

동적 슬롯

• 동적 슬롯은 슬롯의 개수를 가변적으로 관리하는 방법이다.
  최초 일정한 크기의 슬롯을 준비하되 만약 버킷이 가득할 정도로 데이터가 들어온다면 슬롯 크기를 실행중에 늘린다.
  

• 슬롯은 실행 중에 크기를 늘릴 수 있어야 하므로 동적 배열이나 연결 리스트를 사용해야 한다.

• 동적 배열을 사용한다면 해시테이블은 포인터 배열이 될 것이다.

• 연결 리스트를 사용한다면 각 버킷이 슬롯 연결 리스트의 진입점인 head를 저장해야 할 것이다.