이차 조사법, 이중 해싱법, 체이닝

• 이차 조사법

이차 조사법(quadratic probing) 은 선형 조사법과 유사하지만 충돌 방생 시 다음에 조사 할 위치를 다음 식에 의하여 결정한다.

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

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

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

여기서 주의할 것은 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 한다는 점이다. 이 방법은 선형 조사법에서의 문제점인 군집화 현상을 크게 완화시킬 수 있다. 이 방법도 2차 집중 문제를 일으킬 수 있지만 1차 집중처럼 심각한 것은 아니다. 2차 집중의 이유는 동일한 위치로 사상되는 여러 탐색키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문이다. 이것은 이중 해싱법 으로 해결할 수 있다. 이차 조사법은 다음에 조사할 위치를 계산하는 부분만 다음과 같이 변경시키면 된다.

inc++;

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

• 이중 해싱법

이중 해싱법(double hashing) 또는 재해싱(rehashing) 은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. 이 방법은 항목들을 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적인 방법이라 할 수 있다.

선형 조사법과 이차 조사법은 충돌이 발생했을 경우에 해시 함수값에 어떤 값을 더해서 다음 위치를 얻는다. 선형 조사법에서는 더해지는 값이 1이고 이차 조사법에서는 이 된다. 따라서 해시 함수값이 같으면 차후에 조사되는 위치도 같게 된다. 예를 들어, 크기가 10인 해시 테이블에서 제산 함수를 해싱 함수로 사용한다고 할 때, 15와 25는 이차 조사법에서 5, 6, 9, 14, ... 와 같은 조사 순서를 생성한다.

이중 해싱법에서는 탐색키를 참조하여 더해지는 값이 결정된다. 따라서 해시 함수값이 같더라도 탐색키가 다르면 서로 다른 조사 순서를 갖는다. 따라서 이중 해싱법은 이차집중을 피할 수 있다.

두 번째 해시 함수는 조사 간격을 결정하게 된다. 일반적인 형태는 다음과 같다.

step = C - (k mod C) = 1 + k mod C

이런 형태의 함수는 [1...C] 사이의 값을 생성한다.

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

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

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

• 체이닝

체이닝은 하나의 버켓에 여러 개의 레코드를 저장할 수 있도록 하는 방법이다. 버켓은 여러 가지 방법으로 구현될 수 있겠지만 저장할 항목의 수를 예측할 수 없으므로 연결 리스트로 구현하는 것이 적절할 것이다. 이와 같은 오버플로우 해결 방법을 체이닝(chaining) 이라고 한다.