해싱 오버플로우 해결법; 개방주소법과 재해싱, 체이닝

해싱이란 ?

 

키값으로 직접 배열에 접근하는 것이 아니라, 키값을 해시 함수에 넣어서 나온 해시값을 가지고 해시테이블에 접근하여 원소를 탐색, 삽입, 제거하는 기법

 

 

 

예를 들어 array, binary, bubble, file, digit, direct, zero, bucket을 저장하려고 할 때, 첫 번째 글자를 키값으로 사용하여 a는 0, b는 1, c는 2와 같은 해시값을 할당한다. 해시값은 해시 테이블의 인덱스, 버킷 번호에 해당하기 때문에 각각의 값을 순서대로 삽입하면 해시 테이블은 다음의 그림과 같이 구성된다.

 

'bucket'은 주어진 슬롯이 다 찼기 때문에 해시 테이블에 삽입할  수 없고, 이와 같은 현상을 오버플로우라고 한다.

 

 

이러한 오버플로우를 해결하는 방법에는 크게 1. 개방주소법 , 2. 체이닝 두 가지가 존재한다.

 

 

 

▷ 개방주소법(open addressing)

: 현재 사용되고 있지 않은 공간을 찾아 저장하는 방법. 빈 공간을 효율적으로 찾는 것이 중요하다. 충돌이 일어났을 때 대처하는 방법에 따라 선형 조사법, 이차 조사법, 이중 해싱법, 뻐꾸기 해싱 등이 존재한다.

 

 

 

1. 선형 조사법(linear probing)

 

해시테이블을 ht, 해시값을 k라고 할 때 충돌이 ht[k]에서 발생했다면 비어있는 공간이 나올 때까지 ht[k]+1, ht[k]+2... 를 조사한다. 테이블의 마지막에 도달하게 되면 테이블의 처음부터 다시 비어있는 공간을 찾고, 만약 조사를 시작했던 위치로 다시 돌아오게 되면 테이블이 가득 찬 것이다.

 

선형 조사법은 군집화(clustering) 문제가 발생할 수 있다는 단점이 있다. 군집화란, 한 번 충돌이 시작되면 그 위치 근처에 항목들이 집중되는 현상이다. 군집화 문제가 발생하면 빈 공간을 탐색하는 시간이 오래 걸린다.

 

 

조사 위치 : (h(k) + i) mod M, i = 0,1,2.... 

 

 

 

만약 h(k) = k mod 7인 경우에 8, 1, 9, 6, 13의 원소를 순서대로 저장하려고 할 때는 해시 테이블이 다음과 같이 변화할 것이다. 

 

 

1단계 : h(8) = 8 mod 7 = 1 이므로 버킷 1에 8을 저장

2단계 : h(1) = 1 mod 7 = 1 이므로 충돌. h(1)+1, 즉 1+1 이므로 버킷 2에 1을 저장

3단계 : h(9) = 9 mod 7 = 2 이므로 충돌. h(9)+1, 버킷 3에 9를 저장

4단계 : h(6) = 6 mod 7 = 6 이므로 버킷 6에 6을 저장

5단계 : h(13) = 13 mod 7 = 6 이므로 충돌. h(13)+1, 6이 테이블의 마지막으므로 테이블의 처음인 버킷 0에 13 저장

 

 

버킷 6부터 버킷 3까지 클러스터링이 발생한 것을 확인할 수 있다.

 

만약 해시테이블이 이와 같은 상황에서 만약 20을 저장하려고 한다면,

h(20) = 20 mod 7 = 6 이므로 충돌. h(20)+1, h(20)+2, h(20)+3, h(20)+4 모두 충돌 발생하여 h(20)+5, 버킷 4에 20을 저장하게 될 것이다.

 

클러스터링이 발생하면 이와 같이 빈 공간을 탐색하는데 시간이 많이 소요되기 때문에, 군집화를 완화할 수 있는 방법이 필요하다.

 

 

 

 

2. 이차 조사법(quadratic probing)

 

선형조사법과 유사하지만, 조사할 다음 위치를 구하는 식에 약간 변형을 주어 군집화를 완화시킨 방법이다. 

 

조사 위치 : (h(k) + i²) mod M, i = 0,1,2.... 

 

동일한 위치로 맵핑되는 탐색 키들이 빈 버킷을 조사하는 순서가 동일하기 때문에(h(k)가 1인 탐색 키는 모두 1, 2, 5, 10 의 순서로 빈 버킷을 조사) 2차 클러스터링 문제가 있지만 1차 집중과 비교하면 훨씬 심각도가 덜하다.

 

 

 

3. 이중 해싱법(double hashing)

 

충돌 발생시 원 해시함수 h(k)와 다른 별개의 해시함수 h'(k)를 추가로 사용하는 방법. 예를 들어 h(k) = k mod M이라면, h'(k) = C - (k mod C) 라는 별개의 식을 만드는 것으로, 집중 현상이 거의 발생하지 않는다.

 

 

조사 위치 : (h(k) + i * h'(k)) mod M, i = 0,1,2.... 

 

 

만약 앞선 예시에서 h'(k) = 5 - (k mod 5)를 이차 해시함수로 사용하여 8, 1, 9, 6, 13의 원소를 순서대로 저장한다면 해시테이블은 다음과 같이 변화할 것이다.

 

 

1단계 : h(8) = 8 mod 7 = 1 이므로 버킷 1에 8을 저장

2단계 : h(1) = 1 mod 7 = 1 이므로 충돌. h'(1) = 5 - (1 mod 5) = 5 - 1 = 4이므로  h(1)+1*h'(1), 즉 1+4 이므로 버킷 5에 1을 저장

3단계 : h(9) = 9 mod 7 = 2 이므로 버킷 2에 9를 저장

4단계 : h(6) = 6 mod 7 = 6 이므로 버킷 6에 6을 저장

5단계 : h(13) = 13 mod 7 = 6 이므로 충돌. h'(13) = 5 - (13 mod 5) = 5 - 3 = 2이므로 h(13)+1*h'(13), 즉 8이어서 8 mod 7 = 1이므로 충돌. h(13)+2*h'(13) = 6+4 = 10이고 10 mod 7 = 3이므로 버킷 3에 13을 저장.

 

 

 

 

 

4. 뻐꾸기 해싱(Cuckoo hashing)

 

뻐꾸기가 다른 새의 둥지에 알을 낳고, 기존의 알을 둥지에서 밀어내는 습성을 모방한 해싱 방법. 2개의 해시 함수와 2개의 해시 테이블을 가지고, 한 쪽에서 충돌이 발생하면 기존 원소를 다른 쪽으로 이동시킨 후 충돌이 발생했던 자리에 새로운 원소를 삽입한다.

 

예를 들어 해시 테이블 a,b와 해시 함수 a(x), b(x)가 있다고 해보자. k를 삽입하려고 할 때, a(x)를 사용하여 구한 해시값 a(k)가 해시 테이블 a에서 기존에 저장되어있던 원소 p와 충돌이 발생하였다면, b(x)를 사용해 해시값 b(p)를 구한 후 기존의 원소 p를 b 테이블로 이동시키고, a(k)의 자리를 k가 차지하는 것이다. 반대로 b 테이블에서 충돌이 발생한 경우도 마찬가지로, 기존 원소를 a 테이블로 옮긴 후에 새로운 원소가 그 자리에 들어간다.

 

 

만약 뻐꾸기 해싱을 사용하여 10, 32, 45, 61을 삽입한다고 해보자.

 

각 원소들의 해시값

 

각 원소들의 해시값은 위의 그림과 같다. 

 

1단계 : 10을 h 테이블 버킷 6에 저장

2단계 : 32를 h 테이블 버킷 1에 저장

3단계 : 45가 h 테이블의 해시값 6에서 충돌. -> 10을 d 테이블 버킷 3으로 이동 -> 45를 저장

4단계 : 61이 h 테이블 해시값 1에서 충돌 -> 32가 d 테이블 해시값 3에서 충돌 -> 10이 h 테이블 해시값 6에서 충돌 -> 45를 d 테이블 버킷 9에 이동 -> 10을 h 테이블 버킷 6으로 이동 -> 32를 d 테이블 버킷 3으로 이동 -> 61을 저장

 

 

만약 위와 같이 이동을 통해 삽입 연산을 시행하다가, 사이클이 발생한다면 어떻게 해야 할까? 새로운 해시 함수와 새로운 해시 테이블을 만들어야 할 것이다. 이런 경우뿐만 아니라, 해시 테이블에 담긴 정보가 많아져 어쩔 수 없이 집중현상이 발생하고 연산 시간이 증가한 경우에도 새로운 해시 함수와 새로운 해시 테이블이 필요하다.

 

이러한 연산을 재해싱이라고 한다.

 

 

 

 

 

▷ 재해싱 (rehashing)

 

해시 테이블의 적재 비율(load factor)이 일정 수준 이상으로 커지면 새로운 해시 함수와 새로운 해시 테이블을 생성하고 원래 해시 테이블의 모든 탐색 키들을 새로운 해시 테이블로 다시 해싱하는 것을 재해싱이라고 한다.

 

이때 새로운 해시 테이블의  크기는, 기존 해시 테이블 크기의 2배 이상 큰 소수로 선택한다. 예를 들어 기존 테이블의 크기가 7이었다면, 2배인 14 이상의 소수인 17을 새로운 해시 테이블의 크기로 선택한다.

 

적재 비율은 삽입된 원소 개수를 전체 해시 테이블 크기로 나눈 값이고, 적재 비율의 임계값은 0.5 혹은 0.7로 설정하면 된다. 재해싱은 오버플로우 해결에도 사용될 수 있다.

 

 

 

 

▷ 체이닝(chaining)

: 오버플로우 문제를 연결 리스트로 해결하는 방법이다. 각 슬롯에 다음 슬롯의 주소를 함께 저장하여 삽입과 삭제가 용이하도록 구현한다. 버킷 내에 중복 키가 있는지 확인하며 없다면 리스트 맨 앞이나 맨 뒤에 새로운 노드를 삽입한다.

 

 

 

만약 크기가 7인 해시 테이블에 h(k) = k mod 7인 해시 함수를 이용해 8, 1, 9, 6, 13의 원소를 삽입한다면, 해시 테이블은 다음과 같은 모양이 될 것이다.

 

체이닝은 적재 밀도가 증가하더라도 성능이 급격하게 떨어지지는 않으나 효율성을 위해 적재 밀도를 일정 수준 미만으로 유지시켜주는 것이 좋다.

 

 

 

이진 탐색 트리와 비교하였을 때, 키 값들의 순서 관계가 중요하지 않다면 해싱을 사용하는 것이 유리하고, 키 값의 크기 순으로 운행해야 한다면 이진 탐색 트리가 유리하다.