11. 해시테이블의 충돌 해결

해시테이블에서 두 개 이상의 원소들이 동일한 셀로 매핑되는 것을 충돌collision이라 한다.
즉, $k_1 \neq k_2$에 대해 $h(k_1) = h(k_2)$이면 충돌이 일어났다고 한다.

분리연쇄법^{separate chaining}

분리연쇄법 또는 연쇄법에서 각 버켓 $A[i]$는 리스트 $L_i$에 대한 참조를 저장한다. 여기서 $L_i$은, 해시함수가 버켓 $A[i]$로 매핑한 모든 항목들을 저장하는, 무순리스트 또는 기록파일 방식으로 구현된 미니 사전이라 볼 수 있다.

즉, 같은 키값으로 매핑된 원소들을 미니 사전 $L$에 넣어두고, 해당 사전안에서 재귀적으로 탐색하여 원소를 찾는다.

이 방법은 단순하고 빠르다는 장점이 있으나, 테이블 외부에 추가적인 저장공간을 요구한다.

개방주소법^{open addressing}

개방주소법에서는 충돌 항목을 테이블의 다른 셀에 저장한다. 분리연쇄법에 비해 공간이 절약되지만, 삭제가 어렵고 사전 항목들이 연이어 군집화된다.

선형조사법^{Linear Probing}

충돌 항목을 바로 다음의 빈 테이블 셀에 저장함으로써 충돌을 처리한다.
예를들어, 셀 $A[h(k)]$에서 충돌이 발생할 경우, 데이터는 $A[(h(k)+1)\%M]$셀에 저장된다. 이때, 셀을 검사하는 것을 조사^probe라 한다.

충돌 항목들은 군집화하며, 이후의 충돌에 대해 더욱 긴 조사열로 군집된다. (1차 군집화)

2차 조사법^{Quadratic Probing}

2차 조사법은 다음 식의 순서로 버켓을 조사한다.

$$ A[(h(k)+f(i)) \% M], f(i) = i^2 $$

1차 군집화는 피하지만, 이 또한 나름의 군집을 형성하는 2차 군집화가 발생한다. 또한, M이 소수가 아니거나, 버켓 배열이 반 이상 차면, 비어 있는 버켓이 있더라도 찾지 못할 수도 있다.

이중해싱

 이중 해싱은 두번째의 해시함수 $h'$를 사용하여 다음과 같이 버켓을 조사한다.

$$ A[h(k) + f(i)) \%M], f(i) = i\cdot h'(k)$$

동일한 해시값을 갖는 키들도 상이한 조사를 수반할 수 있기 때문에 군집화가 최소화된다. 단, $h'$의 계산 결과가 0이 되면 안된다.

최선의 결과를 위해, $h'(k)$와 $M$은 서로소여야 한다.

개방주소법에서의 갱신

개방주소법에서는 기존의 empty와 active 외에 inactive 상태를 만든다. 이 상태의 셀은 삭제된 셀을 의미한다.

적재율

해시테이블의 적재율 $\alpha = n/M$이다. 즉, 좋은 해시함수를 이용할 경우 각 버켓의 기대 크기이다.

적재율은 가능하면 낮게 유지되어야 한다. (가능하면 1 아래)

좋은 해시함수가 주어졌다면, 탐색, 삽입, 삭제 작업의 기대실행시간은 $O(\alpha)$이다.

분리연쇄법에서, $\alpha > 1$이면 작동은 하지만 비효율적이고, $\alpha \leq 1$이면 $O(1)$의 기대실행시간을 달성할 수 있다.

개방주소법은 항상 $\alpha \leq 1$인데, 이때 $\alpha > 0.5$면 군집화의 가능성이 높고 그 이하이면 $O(1)$ 기대실행시간을 갖는다.

재해싱

해시테이블의 적재율을 최적(보통 0.75)으로 유지하기 위해, 주기적으로 재해싱을 해주는 것이 좋다.

• 적재율이 최적치를 초과했을 때
• 삽입이 실패했을 때
• 너무 많은 비활성 셀이 존재하여 성능이 저하될 때

위 경우에 재해싱을 수행하는데, 그 과정은 아래와 같다.

1. 버켓 배열의 크기를 증가시킨다. (원래 배열의 대략 두 배 크기로 하되, 크기를 소수로 설정해야 한다.)
2. 새 크기에 대응하도록 압축맵을 수정한다.
3. 새 압축맵을 적용하여, 기존 해시테이블의 모든 원소들을 새 테이블에 삽입한다.