곱셈법 해싱이란?
곱셈법(multiplication method)은 키 값을 해시 테이블의 인덱스로 변환하는 대표적인 해싱 기법 중 하나입니다. 이 방법은 다음과 같은 해시 함수를 사용합니다.
h(x) = ⌊m·x·A⌋ mod m
여기서 A는 실수형 상수이며, m은 해시 테이블의 크기를 의미합니다. 키 x에 상수 A를 곱한 뒤 소수점 아래를 버리고, 테이블 크기 m으로 나머지 연산을 하여 해시 값을 얻는 방식입니다.
곱셈법의 장점
곱셈법의 가장 큰 장점은 m(테이블 크기)의 값이 크게 중요하지 않다는 점입니다. 나눗셈법에서는 충돌을 줄이기 위해 소수를 선택해야 하는 제약이 있는 반면, 곱셈법에서는 m을 2의 거듭제곱 형태로 자유롭게 선택할 수 있습니다. 덕분에 비트 연산만으로 모듈로 계산을 빠르게 처리할 수 있어 구현 측면에서도 유리합니다.
물론 어떤 값의 A를 선택하더라도 유효한 해시 함수가 되지만, A 값에 따라 키가 해시 슬롯에 분포되는 균등성이 달라지므로 일부 값은 다른 값보다 더 좋은 성능을 보입니다.
최적의 A 값: 황금비
도널드 커누스(Donald Knuth)의 권고에 따르면, A 값으로 황금비(golden ratio)를 사용하는 것이 가장 좋습니다.
A = (√5 − 1) / 2 ≈ 0.61803398
황금비를 상수로 사용하면 연속적인 키 값들이 해시 테이블 전체에 비교적 고르게 흩어지므로, 충돌 가능성을 효과적으로 낮출 수 있다고 알려져 있습니다.
비둘기집 원리와 최악의 경우 성능
그러나 A 값을 어떻게 신중하게 선택하더라도 근본적인 한계는 존재합니다. 비둘기집 원리(pigeonhole principle)에 의해, 전체 키 공간의 크기를 u라고 할 때 u ≥ nm 조건이 성립하면 크기가 n인 부분집합 S ⊆ U와 특정 해시 값 i가 반드시 존재하여, S에 속한 모든 x에 대해 h(x) = i가 됩니다.
즉, n개의 서로 다른 키가 모두 동일한 해시 값으로 몰리는 상황이 이론상 피할 수 없습니다. 따라서 곱셈법 해싱의 최악의 경우(worst case) 성능은 나눗셈법 해싱만큼 나쁠 수 있다고 결론지을 수 있습니다.