단일 해시 함수의 한계
해시 테이블에서 하나의 고정된 해시 함수를 사용할 때 근본적인 문제가 발생합니다. 테이블 크기 m이 전체 키 공간(universe)의 크기 u보다 훨씬 작다면(|U| ≫ m), 어떤 해시 함수 h를 선택하더라도 반드시 같은 해시 값으로 매핑되는 U의 거대한 부분집합이 존재하게 됩니다.
즉, 입력 데이터가 어떤 특정 함수에 취약한 형태로 분포해 있다면 충돌(collision)이 집중적으로 발생하여 해시 테이블의 성능이 급격히 저하될 수 있습니다.
해결 방법: 해시 함수 집합의 도입
이 문제를 해결하기 위해서는 여러 개의 해시 함수로 이루어진 집합 ℌ을 준비하고, 그중에서 실제 저장할 키 집합 S에 잘 맞는 함수를 선택하는 전략이 필요합니다.
만약 ℌ에 속한 대부분의 해시 함수가 S에 대해 좋은 성능을 보인다면, 굳이 S를 분석하지 않고도 ℌ에서 무작위(random)로 함수를 하나 골라 사용하는 것만으로도 높은 확률로 좋은 성능을 기대할 수 있습니다. 이것이 범용 해싱의 핵심 아이디어입니다.
범용 해싱(Universal Hashing)의 정의
해시 함수들의 집합 ℌ가 다음 조건을 만족하면 범용(universal)이라고 합니다.
전체 키 공간 U에 속한 서로 다른 임의의 두 키 x, y ∈ U에 대하여, h(x) = h(y)를 만족하는 함수 h ∈ ℌ의 개수는 최대 |ℌ|/m개입니다.
이를 직관적으로 표현하면 다음과 같습니다.
- ℌ에서 무작위로 해시 함수 h를 선택했을 때,
- 서로 다른 두 키 x와 y가 충돌할 확률은 최대 1/m입니다.
이는 마치 x와 y를 집합 {0, 1, ..., m − 1}에서 독립적으로 무작위 추출한 것과 동일한 충돌 확률을 보장한다는 의미입니다. 즉, 어떤 악의적인 입력 패턴이 주어지더라도 무작위성 덕분에 충돌이 예상 수준(1/m)을 넘지 않습니다.
기대 성능 분석
범용 해시 함수 h를 사용하여 키 집합 S를 해시 테이블에 저장하고 체이닝(chaining)으로 충돌을 처리할 경우, 탐색(search)과 삭제(delete) 연산의 기대 시간 복잡도는 다음과 같습니다.
O(1 + α)
여기서 α = n/m은 적재율(load factor)로, 저장된 요소 수 n을 테이블 크기 m으로 나눈 값입니다. α를 적절히 유지하면 평균적으로 상수 시간에 연산을 수행할 수 있습니다.
정리
범용 해싱은 단일 해시 함수가 가진 최악의 경우(worst-case) 취약점을 무작위화(randomization)로 극복하는 기법입니다. 해시 함수를 실행 시점에 무작위로 선택함으로써, 어떤 입력에 대해서도 충돌 확률이 1/m 이하로 제한되며, 결과적으로 탐색·삽입·삭제가 기대적으로 O(1 + α) 시간에 동작함을 보장합니다.