완전 해싱(Perfect Hashing)이란?
완전 해싱은 임의의 n개 원소 집합을 그와 동일한 크기의 해시 테이블에 저장하고, 탐색(lookup) 연산을 상수 시간(O(1))에 수행할 수 있도록 보장하는 해싱 모델을 의미합니다. 이 기법은 프레드먼(Fredman), 코몰로시(Komlós), 세메레디(Szemerédi)가 1984년에 발명하고 체계적으로 논의했기 때문에, 세 사람의 이름을 딴 'FKS 해싱'이라는 별칭으로도 널리 알려져 있습니다.
일반적인 해싱에서는 서로 다른 키가 같은 슬롯에 매핑되는 충돌(collision)이 발생할 수 있지만, 완전 해싱은 키 집합이 고정되어 있다는 전제 아래 충돌 자체를 원천적으로 제거하는 것이 핵심 특징입니다.
정적 해싱(Static Hashing)이란?
정적 해싱은 해싱 문제의 또 다른 형태로, 사용자가 최종 확정된 사전(dictionary) 집합에 대해 탐색을 수행할 수 있게 해주는 방식입니다. 여기서 '사전'이란 저장 대상이 되는 데이터 집합을 뜻하며, 사전에 포함된 모든 객체는 이미 최종 결정되어 더 이상 변경되지 않는다는 것이 전제 조건입니다.
즉, 데이터의 삽입·삭제·갱신이 없고 조회만 반복적으로 일어나는 환경에서 정적 해싱은 빛을 발합니다.
응용 분야
정적 해싱은 데이터베이스와 그 객체, 참조 값이 항상 동일하게 유지되어야 한다는 요구 사항 때문에 적용 범위가 제한적입니다. 다만 데이터 변경이 매우 드문 데이터베이스라면, 아주 가끔 전체 데이터베이스를 재해싱(rehash)하는 비용만 감수하면 되므로 충분히 활용 가능합니다.
대표적인 활용 예시는 다음과 같습니다.
- 특정 언어의 단어 집합 및 단어 정의 목록
- 조직의 인사 정보처럼 거의 변하지 않는 중요 데이터 집합
- 컴파일러의 예약어(reserved keyword) 테이블
구현 방법
정적 환경에서는 총 p개의 항목(entry)으로 이루어진 집합이 미리 주어지며, 각 항목은 고유한 키를 가집니다. 프레드먼, 코몰로시, 세메레디는 이를 위해 2단계(two-level) 해싱 구조를 사용합니다.
- 1차 해시 테이블: 크기가 s = 2(p−1)인 버킷(bucket)들로 구성된 최상위 해시 테이블을 선택합니다.
- 버킷 분배: 최상위(top-level) 해시 함수를 이용해 p개의 항목을 q = 2(p−1)개의 버킷으로 분리합니다.
- 2차 테이블 할당: r개의 항목을 담고 있는 각 버킷에 대해, 슬롯 수가 r²인 2차(second-level) 테이블을 할당합니다.
- 해시 함수 선택: 각 버킷의 해시 함수는 범용 해시 함수군(universal hash function family)에서 무작위로 선택하며, 해당 버킷 내부에서 충돌이 없도록 보장될 때까지 새로운 함수를 계속 추출합니다. 선택된 해시 함수는 해시 테이블과 함께 저장하여 이후 탐색 시 재사용합니다.
- 최종 배치: 충돌 없는 해시가 확보되면, 해당 버킷의 r개 항목을 2차 테이블에 해싱하여 배치합니다.
이러한 구조 덕분에 어떤 키든 최대 두 번의 해시 계산만으로 목표 위치에 도달할 수 있으며, 전체 테이블의 공간 복잡도 역시 O(n) 수준으로 유지됩니다. 결과적으로 정적 완전 해싱은 최악의 경우에도 상수 시간 탐색을 보장하는 강력한 기법입니다.