자료구조 :: 해싱(3) 충돌 해결책 - 이차조사법, 이중해싱법

# 이차조사법(quadratic probing)

이차조사법은 선형조사법과 유사하지만, 다음 조사할 위치를 다음 식에 의하여 결정한다.

(h(k) + i*i) mod M　　for 0,1,...,M-1

따라서 조사되는 위치는 다음과 같이 된다.

h(k), h(k)+1, h(k)+4, h(k)+9....

여기서 주의할 것은 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 한다는 점이다.
이 방법은 선형조사법에서 문제점인 집중 결합을 크게 완화시킬 수 있지만 이 방법도 2차 집중문제를 일으킨다.
2차 집중의 이유는 동일한 위치로 사상되는 여러 탐색 키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문이다.

선형조사법 소스 중에 데이터가 추가되는 부분에 아래 코드만 추가하면 된다.

i=(i+inc+1) % TABLE_SIZE; // (h(k) + i*i) mod M for 0,1,...,M-1
inc = inc+2;

또는

inc = inc + 1
i = (i+inc*inc) % TABLE_SIZE

위 두 코드는 같지만 1번 코드는 곱셈 연산이 없기때문에 조금 더 빠르게 수행된다고 할 수 있다.


# 이중해싱법(double hashing)

이중해싱법 또는 재해싱은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와
다른 별개의 해시 함수를 이용하는 방법이다.이 방법은 항목들을 해시 테이블에 보다 균일하게 분포시킬 수 있으
므로 효과적인 방법이라 할 수 있다.
이중 해싱법에서는 탐색키를 참조하여 더해지는 값이 결정된다. 따라서 해시함수 값이 같더라도 탐색키가 다르면
서로 다른 조사 순서를 갖는다. 따라서 이중해싱법은 이차 집중을 피할 수 있다.
두번째 해시 함수는 조사 간격을 결정하게 된다. 일반적인 형태는 다음과 같다.

step = C - (k mod C)// 이런 형태의 함수는 [1...C]사이의 값을 생성한다.

충돌이 발생했을 경우, 조사되는 위치는 다음과 같다.

h(k), h(k) + step, h(k)+2*step, h(k)+3*step ....

C는 보통 테이블의 크기인 M보다 약간 작은 소수이다. 이중 해싱에서는 보통 집중 현상이 매우 드물다.
이유는 같은 해시 함수값과 같은 탐색 순서를 가지는 요소들이 거의 없기 때문이다.

예를 들어 테이블 크기가 7(M)이고 C가 5, 문자열을 숫자로 변환한 탐색키값이 13일 때, 

h(13) = 13 mod 7 = 6
h`(13) = 5 - (h(13) mod 5 ) = 2

첫번째 조사의 위치 : h(13) = 6
충돌시 조사의 위치 : (h(13)+h`(13)) mod 7 = (6+2) mod 7 = 1
두번째 충돌시 조사의 위치 : (h(13) + 2 * h`(13)) mod 7 = (6+2*2) mod 7 = 3

따라서 조사는 인덱스 6에서 시작하여 2씩 증가하게 된다. 조사가 되는 인덱스를 나열해보면 6,1,3,5,0,2,4..가 되어
테이블의 모든 위치를 조사하게 된다. 이런 결과는 물론 테이블의 크기가 소수일 경우만 적용된다.
만약 테이블의 크기를 6으로 바꾼다면 조사 위치는 1,3,5,1,3,5..가 되어서 같은 위치만 되풀이 된다.

선형조사법의 문제점은 한번도 사용되지 않은 위치가 있어야만 탐색이 빨리 끝나게 된다는 것이다. 만약 거의모든
위치가 사용되고 있거나 사용된 적이 있는 위치라면 실패하는 탐색인 경우, 테이블의 거의 모든 위치를 조사하게
된다.