해슁에서의 충동해결(Collision Resolution)

이전글 - 해슁(Hashing) / 해쉬 알고리즘 / 해쉬 함수

충동 해결(Collision Resolution)에는 크게 두 가지 방법이 있다. 첫 번째는 체이닝(Chaining)으로 해쉬 테이블의 각 주소가 연결 리스트의 헤더 역활을 하고, 여기에 해당 주소로 들어오는 원소들이 연결 리스트(Linked List)로 매달린다. 두 번째는 개방 주소 방법인데, 체이닝처럼 추가 공간을 사용하지 않고 해쉬 테이블 안에서 충돌을 해결한다. 원래 들어갈 자리가 아니더라도 테이블의 다른 자리를 찾아 들어가게 된다.

① 체이닝(Chaining)

체이닝에서는 같은 주소로 해슁되는 원소를 모두 하나의 연결 리스트에 매달아 관리한다.

위 의 그림처럼 h(39) = h(13) = 0 인 경우 해쉬테이블의 0 인덱스는 39를 가리키고 39는 13을 가리킨다.

체이닝에서의 삽입은 효율성을 위해서 연결리스트의 맨 앞에 삽입을 한다. 맨 뒤에 삽입할 경우 삽입시마다 연결리스트를 따라 맨 끝으로 이동해야하므로 낭비가 된다.

탐색과 삭제 같은 경우는 그냥 연결리스트 방식과 동일하게 진행된다.

② 개방주소 방법(Open Addressing)

개방주소 방법은 체이닝과 같은 추가 공간을 허용하지 않고 주어진 해쉬 테이블 공간 내에서 해결한다. 먼저 해쉬 함수를 계산하여 계산된 주소를 차지하고 있는 다른 원소가 없으면 그 자리에 넣고, 이미 그 자리를 차지한 원소가 있으면 정해진 규칙에 따라 다음 자리를 찾게된다. 처음 계산한 해쉬 함수를 0번째 해쉬함수, 충돌이 일어나서 다음 주소를 계산하는 것을 1번째 해쉬함수 ... 이런식으로 표현한다.

다음 주소를 결정하는 방법이 다양한데 대표적인 3가지는 선형 조사(Linear Probing), 이차원 조사(Quadratic Probing), 더블 해슁(Double Hashing)이다.

선형 조사(Linear Probing)

선형 조사는 가장 간단한 충돌 해결 방법으로, 충돌이 일어난 바로 뒷자리를 보는 것이다. 이렇게 하면 i번째 해쉬 함수는 h(x)로 부터 i만큼 떨어진 자리가 된다. 테이블의 경계를 넘어갈 경우에는 맨 앞으로 돌아간다.

위 의 예제는 25, 13, 16, 15, 7, 28, 31, 20, 1, 38 이 입력된 경우이다. 7까지는 정상으로 배치가 되고 28부터 충돌이 발생하게 된다. h(28) = 2 인데 이미 2 인덱스에는 원소 15가 자리르 차지하고 있다. 그래서 그 다음 자리인 인덱스 3으로 이동하나 이미 원소 16이 자리하고있다. 한칸 더 이동하여 인덱스 4에 28이 저장되게 된다.

선형 조사의 경우 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다. 이런 형상을 1차 군집(Primary Clustering)이라 한다. 이렇게 되면 평균 검색 시간과 삽입 시간이 증가하게 된다.

이차원 조사(Quadratic Probing)

이차원 조사는  바로 뒷자리를 보는 선형 조사와 달리 보폭을 이차함수에 의해 넓혀가면서 본다. 예를 들면, i번째 해쉬 함수를 h(x)로 부터 i^2만큼 떨어진 자리로 삼을 수 있다. 즉, h(x), h(x)+1, h(x)+4, h(x)+9, h(x)+16.... 과 같이 볼 수 있다.

이렇게 하면 선형 조사에서처럼 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있다. 그러나 여러 개의 원소가 동일한 초기 해쉬 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없어 비효율적이 된다. 이런 현상을 2차 군집(Secondary Clustering)이라 한다.

위의 그림은 이차원 조사의 한 예이다.

더블 해슁(Double Hashing)

더블 해슁은 두 개의 함수를 사용한다. 더블 해슁에서 i번째 해쉬 함수는 다음과 같다.

여기서 h(x)와 f(x)는 서로 다른 해쉬 함수이다. 충돌이 생겨 다음에 볼 주소를 계산할 때 두 번째 해쉬 함수값 만큼씩 점프를 한다.

더블 해슁에서 조심할 점은 두 번째 해쉬 함수 값 f(x)가 해쉬 테이블 크기 m과 서로 소인 값이어야 한다는 것이다. 만일 f(x)와 m이 1보다 큰 최소공약수 d를 가지면 x의 자리를 찾기 위해 해쉬 테이블 전체 중 기껏해야 1/d 밖에 보지 못하게 된다.

두 개의 해쉬 함수를 정하는 데 있어서 권장하는 방법은 h(x) = x mod m 으로 잡고, m보다 조금 작은 소수 m' 에 대해 f(x) = 1 + (x mod m')으로 잡는 것이다.

개방주소 방법에서의 삽입의 슈도코드는 다음과 같다.

개방주소 방법은 테이블에 주어진 공간만 사용할 수 있으므로 적재율이 1을 넘을 수 없다. 적재율이 높아지면 효율이 급격히 떨어지므로 적당한 임계점을 설정한 후 그것을 넘으면 해쉬 테이블의 크기를 두배로 키우고 모든 원소를 다시 해슁하는 것이 일반적이다.

또 한가지 개방주소 방식에서 조심할 것은 원소를 삭제했을 경우이다.

위 예는 선형조사에서의 삭제로 (a)에서 1을 삭제하면 (b)에서 38을 삽입할때 1의 자리를 검사하여 없는 자리인 줄 알고 38을 1의 자리에 삽입할 수 있다. 이러면 삽입의 순서가 뒤틀리게 된다. 그리하여 삭제할 경우 그 자리에 DELETED 라는 상수값을 저장하여 삭제된 자리라는 것을 표시하여야 한다.