[알고리즘] 해싱(Hashing) - 2

해싱(Hashing) - 2

충돌을 해결하는 기법중에 2번째인 open addressing에 대해 알아보자

해시 테이블 슬롯에 키는 하나씩만 저장한다.

이때 충돌이 일어나면 그 슬롯이아니라 다른 슬롯에 저장해야한다는것을 뜻한다.

open addressing은 여러가지 종류가 있는데,

1) Linear Probing

2) Quardratic Probing

3) Double Hashing

위의 3 종류가 대표적이다.

먼저 Linear Probing에 대해서 알아보도록 하자

(a)에서는 순서대로 인덱스에 들어가며 충돌이 일어나지 않는다.

(b) 에서는 B5가 들어가야하는데 이미 A5가 들어가 있으므로 충돌이 일어나게 된다.

여기서 open addressing의 Linear Probing을 수행하는데, 

해싱을 했을 때 이미 다른키에 의해서 해당 인덱스가 차있다면,

Linear 하게 인덱스를 탐색해서 다음 빈 인덱스에 해당 키를 채워넣는 방법이다.

즉, h(k), h(k+1), h(k+2)순으로 탐색하며 빈 인덱스를 찾아 키를 채워넣는다.

테이블의 끝에 들어가면 다시 처음으로 Circulate  하게 돌아오게 된다.

따라서, A5가 5번 인덱스를 차지하고 있으므로 B5는 6번 인덱스에 들어가게 된다.

만약 search를 한다면, 해당 인덱스로 접근을 한 뒤 

빈 슬롯이 나올때까지 다음 슬롯으로 연속해서 search를 진행하게된다.

이런 부분이 chaining과 비슷한 부분이라고 할 수 있다.

Linear Probing의 단점은 클러스터링이다.

테이블의 키 들이 연속으로 뭉쳐 있는 것을 클러스터링이 심하다 라고 하는데 

긴 클러스터가 생기면 새로운 키가 삽입될때 해싱의 결과가 클러스터 끝으로 해싱될 확률이 점점 높아진다.

이런식으로 클러스터링이 발생하게된다면

눈이 커지는것과 비슷하게 클러스터가 점점 커지고, 검색 시간이 길어지게 된다.

그래서 Linear Probing의 단점을 보완하기 위한 것중 하나가 Quardratic probing이다.

Quardratic probing은 probing 의 순서를 조금 변경한것으로 충돌 발생 시다음과 같은 수식으로 해싱을 시도한다.

 h(k), h(k)+1, h(k)+2^2, h(k)+3^2

이것은 Quardratic probing의 한가지 방법이며 항상 위와 같은 식으로 동작하지는 않는다.

이 방법도 Circular하게 돌아가게 된다.

클러스터링이 심해지는 것은 피할수 있지만 다른 단점도 존재한다.

다른 방법으로 Double Hashing이 있는데, 처음부터 해시 함수 2개를 만들게된다.

h(k,i) = (h_1(k) + i*h_2(k)) mod m

이 후에 위와 같은 식으로 키를 저장하게 되는데 기본적인 개념은 Quardratic probing 와 비슷하게

클러스터링을 줄이려고 띄엄띄엄 저장하는 것이다.

Open addressing의 경우 단순히 값을 삭제할 경우 오류가 발생한다.

가령 A2,B2,C2가 순서대로 동일한 해시함수를 가져서 linear probing으로 충돌을 해결한다.

B2를 삭제한 후 C2를 검색한다고 했을때 중간의 B2가 삭제 됐으므로 C2까지 도달하지 못한다.

따라서  B2를 삭제하고 C2를 삭제된 B2의 자리에 놓아야한다.

좀더 자세하게 말하면 어떤 값을 삭제하면 다음 키 들을 한자리씩 옮겨야한다는것이다. 

아니면, 클러스터의 마지막 값을 삭제된 값의 자리에 옮기는것도 방법이 될 수 있다.