[C++/자료구조] 이차조사법과 이중해쉬 (Quadratic Probing, Double Hash)

선형조사법의 한계

closed hashing 인 선형조사법의 한계는 데이터 클러스터 현상입니다.

단순하게 말하면, 데이터가 한 곳에 몰려서 군집을 이룬다는 것이죠.

 

선형 조사법은 충돌 발생시 선형으로 빈공간을 탐색하기 때문에, 충돌이 발생한 지역 위주로 데이터가 몰릴 가능성이 높습니다.

 

이차조사법 및 이중해쉬는 closed hasing, open addressing 해쉬임과 동시에, 선형조사법의 클러스터 현상을

보완하는 해쉬 구조입니다.

 

이차조사법

1) 개요

이차조사법이 상당히 간단합니다.

그냥 선형조사법에 양념만 쳐주면 되죠.

 

이것이 선형조사법의 삽입 코드입니다.

충돌시 hashAddr +1, hashAddr +2, HashAddr +3... 이런 식으로 +1 씩 더해간다는 것을 알 수 있습니다.

 

이제 이차조사법의 코드를 보여드리겠습니다.

 

차이점을 아시겠나요?

offset 이라는 변수를 추가해줘서

충돌이 발생할수록 추가되는 값이 +1 이 아니라, 2의 제곱으로 처리했다는 것에 있습니다.

 

이것말고는 선형조사법과 차이가 없습니다.

 

이차조사법이 선형조사법에 비해서 데이터를 골고루 퍼뜨려준다는 것은 수학적으로 증명이 가능하나, 그리 효과적이지는 않습니다.

 

 

이중해쉬

1) 개요

이차조사법이 선형조사법보다는 낫지만, 그래도 데이터를 몰리게하는 이유는 무엇일까요?

바로 충돌했을 때 항상 동일한 곳으로 점프하기 때문입니다.

 

 

이런 식으로 같은 해쉬 주소에 대해서 충돌이 연속해서 발생하는 것이 문제점이죠.

이를 해결하기 위한 방법이 해쉬함수를 2번 사용하는 이중 해쉬입니다.

 

이중 해쉬는 해쉬함수를 2개 준비합니다.

1차 해쉬: 키를 이용해서 해쉬주소를 만들어내는 함수

2차 해쉬: offset 주소를 만들어내는 함수

 

선형조사법에서는 충돌시

해쉬주소 + i

 

이차조사법에서는 충돌시

해쉬주소 + 2^i 

로 충돌을 해결했다면

 

이중해쉬에서는 충돌시

해쉬주소 + 2차해쉬값 * i

을 통해 충돌을 해결합니다.

 

2) 이차 해쉬의 규칙, 범용적인 이차해쉬

(1) 어떤 경우에도 이차 해쉬의 값이 0이 나오면 안된다.

-> 이차 해쉬의 값이 0이면, 충돌을 해결할 수 없으니 어떻게보면 당연한 조건이죠?

 

(2) 이차 해쉬의 값을 통해 충분히 요소를 넓게 퍼뜨릴 수 있어야 한다.

 

그래서 범용적으로 많이 사용되는 간단한 이차해쉬는 다음과 같습니다.

 

바로 해쉬테이블의 버켓 수보다 작은 prime number로 모듈러 연산을 하는 것인데요.

소수의 모듈러 연산을 통해 충분히 요소를 넓게 퍼뜨릴 수 있으며,

 

임의의 소수 p에 대해서

mod p 의 결과는 0 ~ p-1 이기 때문에

항상 리턴 값으로 0이 발생하지 않습니다.

 

위 이차해쉬를 사용하면 같은 해쉬 주소라 할지라도 다른 offset을 리턴하여, 충돌의 횟수 및 데이터 밀집현상을 막을 수 있습니다.

 

2) 구현

어려운 것은 없으므로 삽입 코드만 간단히 소개하겠습니다.

 

 

 

이차조사법, 이중해쉬의 한계점은 이러한 해쉬구조 또한 데이터의 삭제는 다루기 까다롭다는 것입니다.

 

마치며

해쉬는 O(1)의 시간복잡도를 제공하는 매우 강력한 자료구조이지만, 해쉬의 근본적인 구조 때문에 충돌을 막을 수 없고, 충돌을 최대한 피하는 방향으로 설계한다고 해도 그로 인한 성능 저하는 막을 수 없습니다.

 

충돌을 피하는 방법중 하나는 그냥 load factor 를 낮추는 방법인데요, 

차라리 해쉬 테이블의 버켓 수를 늘려서 충돌 가능성을 낮추는 것입니다.

물론 메모리를 많이 사용해야하는 단점도 존재하죠.

 

자 그럼 이때까지 다룬 자료구조

레드-블랙 트리, 체이닝 해쉬, 오픈어드레싱 해쉬

 

3개의 효율적인 자료구조가 있다고 했을 때, 어떤 자료구조를 고르는게 좋을까요?

 

개인적인 생각으로는

 

메모리를 절약하고, 정렬된 요소를 저장하고 싶다면 레드-블랙 트리

메모리를 많이 사용하고, 일정하게 좋은 성능을 얻고 싶고, 삽입/삭제가 빈번하게 발생하면 체이닝 해쉬

메모리를 매우 많이 사용하고, 매우 좋은 성능을 얻고 싶고, 삽입/삭제가 드물게 발생하면 오픈 어드레싱 해쉬가

좋다고 생각합니다.

 

참고로 여러 언어에서 해쉬 테이블 자료구조를 기본으로 제공하는데요.

C++, 자바의 경우 체이닝 해쉬

루비, 파이썬의 경우 오픈 어드레싱을 사용합니다.

 

다음 포스팅으로는 '자료구조에서의 좋은 해쉬 함수'에 대해서 알아보겠습니다.