데이터 구조의 비대칭 해싱(Asymmetric Hashing): 개념부터 성능 분석까지

비대칭 해싱(Asymmetric Hashing)이란?

비대칭 해싱은 다중 선택 해싱(multiple choice hashing)을 발전시킨 기법으로, 해시 테이블을 여러 개의 블록으로 나누고 각 블록 안에서 후보 위치를 선택함으로써 충돌을 효과적으로 줄이는 방식입니다. 이 글에서는 비대칭 해싱의 동작 원리와 대표적인 성능 분석 결과를 살펴보겠습니다.

기본 개념

비대칭 해싱에서는 해시 테이블을 d개의 블록으로 분할하며, 각 블록의 길이는 n/d입니다. 블록 i에 해당하는 탐색 값(probe value) x_i(0 ≤ i ≤ d−1)은 다음 구간에서 균등하게(uniformly) 추출됩니다.

[i·n/d , (i+1)·n/d − 1]

즉, 각 후보 위치가 서로 다른 블록에 속하도록 제한하는 것이 일반적인 다중 선택 해싱과의 핵심적인 차이점입니다.

삽입 과정

다중 선택 해싱과 마찬가지로, 원소 x를 삽입할 때 알고리즘은 리스트 A[x₀], A[x₁], …, A[x_d−1]의 길이를 먼저 확인합니다. 그다음 x를 이들 중 가장 짧은 리스트에 추가합니다. 만약 길이가 같은 리스트가 여러 개 있어 동률(tie)이 발생하면, 인덱스가 가장 작은 리스트에 삽입하는 것으로 규칙을 단순하게 유지합니다.

최장 리스트 길이의 기댓값

Vöcking(Vocking)의 연구에 따르면, 비대칭 해싱에서 가장 긴 리스트 길이의 기댓값은 다음과 같은 상한을 가집니다.

E[W] ≤ (ln ln n) / (d · ln φ_d) + O(1)

여기서 함수 φ_d는 황금비(golden ratio)의 일반화된 형태입니다. d = 2인 경우에는 고전적인 황금비가 사용됩니다.

φ₂ = (1 + √5) / 2

즉, 두 개의 후보 위치를 사용하는 경우 황금비가 성능 분석의 핵심 상수 역할을 하며, 선택지의 수 d가 늘어날수록 최대 부하가 더욱 빠르게 감소합니다.

왜 중요한가?

참고로 단일 선택 해싱에서는 최대 체인 길이가 대략 ln n / ln ln n 수준으로 증가하는 반면, 비대칭 해싱을 포함한 다중 선택 계열 기법은 ln ln n 수준으로 크게 줄어듭니다. 로그가 두 번 적용된 이 doubly logarithmic 증가 형태는 해시 테이블 전체의 균형을 획기적으로 개선한다는 의미이며, 이것이 비대칭 해싱이 실무적으로 주목받는 이유입니다.