[C언어]58일차 - 이중해싱

 

클러스터를 제대로 방지할 수 있는 방법은 탐사할 주소의 규칙성을 없애는 것뿐이다.

 

이중해싱

해시 함수에 키를 입력하여 얻어낸 주소에서 충돌이 일어나면 새로운 주소를 향해 이동해야 한다.

 

이때의 이동폭을 제2의 해시 함수로 계산한다.

 

즉, 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때, 또 다른 하나는 충돌이 일어날 때 탐사 이동폭을 얻기 위해 사용한다.

 

이렇게 하면 탐사 이동폭의 규칙성은 없애면서도 같은 키에 대해서는 항상 똑같은 결과를 얻을 수 있다.

 

 

 

키가 42인 데이터를 입력한다.

 

42 % 13은 3이므로 주소 3에 입력한다.

 

 

이어서 55를 입력한다. 55 % 13은 3이 지만 이미 42가 입력되어 있기 때문에 충돌이 발생한다.

 

그래서 Hash2 함수를 이용해서 이동폭을 얻어야 한다.

 

 

Hash2함수에 55를 매개변수로 넘기면 2를 반환한다. 55의 새 주소는 원래의 주소 3에 이동폭 2를 더한 5가된다.

 

 

이번에는 81을 입력. 81 % 13도 결과가 3이라 충돌이 일어난다.

 

제곱 탐사를 이용해서 81을 입력했을 때는 42에서 처음 충돌한 후 52에서 한 번 더 충돌한다.

 

반면 이중 해싱을 이용했을 때는 81이 42와 충돌한 후 곧장 자기 자리를 찾아갔다.

 

이처럼 이중 해싱은 2차 클러스터를 효과적으로 방지하여 해시 테이블의 성능 유지를 도와준다.

 

 

재해싱

 

지금까지 해시 테이블의 충돌 문제를 해결할 수 있는 알고리즘인 선형탐사, 제곱 탐사, 이중 해싱에 대해서 알아보았다. 

 

하지만 아무리 성능이 뛰어난 알고리즘이라고 해도 해시 테이블의 여유 공간이 모두 차버려서 발생하는 성능 저하는 막아낼 방법이 없다.

 

아래 그림과 같이 남은 공간이 거의 없는 해시 테이블에서는 연쇄 충돌이 자주 일어난다.

 

이때 재해싱은 이 문제를 해결할 수 있는 방법 중 하나이다.

 

재해싱은 해시 테이블의 크기를 늘리고 늘어난 해시 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱한다.

 

이렇게 하면 또 다시 여유 공간이 생긴다.