해싱의 오버플로우 처리 방법

해싱의 오버플로우 처리 방법

해싱에서 오버플로우를 잘 처리하는 것은 매우 중요하다. 이러한 오버플로우의 처리 방법은 다음의 두 가지로 나눌 수 있다.

(1) 선형 조사법(linear probing) : 충돌이 일어나면 해시 테이블의 다른 위치를 찾아 항목을 저장한다.

(2) 체이닝(chaining) : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다.

• 선형 조사법
  

선형 조사법(linear probing) 은 해싱 함수로 구한 버켓에 빈 슬롯이 없으면 그 다음 버켓에서 빈 슬롯이 있는지를 찾는 방법이다. 이때 비어 있는 공간을 찾는 것을 조사(probing) 이라고 하는데, 여러 가지의 조사 방법이 가능하다.

만약 ht[k] 에서 충돌이 방생했다고 하자. 선형 조사법은 먼저 ht[k+1] 이 비어 있는지를 살핀다. 비어있지 않다면 다음 위치인 ht[k+2] 를 살펴보는데, 이런 식으로 비어있는 공간이 나올 때까지 계속하는 조사 방법이다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 간다. 처음 충돌이 났던 곳으로 다시 돌아오면 테이블이 가득 찬 것이 된다. 따라서 조사되는 위치는 다음과 같은 순서이다.

h(k), h(k) + 1, h(k) + 2, h(k) + 3, ... mod M

버켓 조사는 원형으로 회전하는데, 한번 충돌이 발생한 위치에서 항목들이 집중되는 현상이 나타난다. 이것을 군집화(clustering) 현상이라고 한다.