데이터 구조에서의 이중 해싱(Double Hashing) 기법 완벽 정리

이 글에서는 개방 주소법(Open Addressing) 방식에서 충돌을 해결하는 대표적인 기법인 이중 해싱(Double Hashing)에 대해 자세히 살펴보겠습니다.

이중 해싱이란?

개방 주소법에서는 해시 테이블의 특정 슬롯이 이미 차 있을 경우, 다른 빈 슬롯을 찾아 데이터를 삽입해야 합니다. 이때 하나의 해시 함수만 사용하는 선형 탐사(Linear Probing)나 제곱 탐사(Quadratic Probing)와 달리, 이중 해싱은 두 개의 서로 다른 해시 함수를 조합하여 탐사 위치를 결정합니다.

먼저 일반적인 해시 함수 h′(x) : U → {0, 1, ..., m − 1}이 정의되어 있다고 가정합니다. 삽입하려는 위치가 이미 차 있으면, 두 번째 해시 함수를 활용해 새로운 탐사 간격(probe interval)을 계산하며 빈 공간을 찾습니다.

핵심 수식

이중 해싱은 아래와 같은 두 개의 보조 해시 함수로 구성됩니다.

h₁(x) = x mod m
h₂(x) = x mod m′

그리고 실제 탐사 순서를 결정하는 해시 함수는 다음과 같습니다.

h(x, i) = (h₁(x) + i · h₂(x)) mod m

여기서 i는 0, 1, ..., m − 1 범위의 값을 가지며, 빈 슬롯을 발견할 때까지 0부터 시작해 1씩 증가시킵니다. 특히 i = 0일 때는 h(x, i)가 기본 해시 함수 h′(x)와 동일해지므로, 첫 번째 시도는 항상 원래의 해시 위치에서 시작됩니다.

이중 해싱의 장점

• 클러스터링 감소: 선형 탐사에서 발생하는 1차 군집화(primary clustering) 문제를 크게 줄여줍니다.
• 균등한 분포: 키마다 서로 다른 탐사 간격을 사용하므로 충돌 시 위치가 고르게 분산됩니다.
• 성능 향상: 적절한 m과 m′ 값을 선택하면 평균 탐사 횟수를 최소화할 수 있습니다.

예시

크기가 20(m = 20)인 해시 테이블이 있다고 가정하고, 다음 요소들을 이중 해싱 방식으로 삽입해 보겠습니다.

삽입할 요소: {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

이 예제에서 사용되는 두 해시 함수는 다음과 같습니다.

h₁(x) = x mod 20
h₂(x) = x mod 13

각 키에 대해 h(x, i) = (h₁(x) + i · h₂(x)) mod 20을 계산한 결과는 아래 표와 같습니다.

위 과정을 거쳐 완성된 최종 해시 테이블은 다음과 같습니다.

마무리

이중 해싱은 두 개의 독립적인 해시 함수를 활용함으로써 충돌 발생 시에도 데이터가 테이블 전반에 고르게 분포되도록 만드는 강력한 기법입니다. 특히 테이블의 크기 m을 소수(prime number)로 선택하면 모든 슬롯을 빠짐없이 탐사할 수 있어 성능이 더욱 안정적입니다. 해시 테이블의 검색·삽입 성능을 극대화하고 싶다면 이중 해싱을 적극적으로 고려해 볼 만합니다.