정수 키를 위한 해시 테이블의 기본 구조
해시 테이블(hash table)은 키(key)를 기반으로 데이터를 빠르게 저장하고 검색할 수 있는 대표적인 데이터 구조입니다. 이 글에서는 정수 키를 다루는 해시 테이블의 동작 원리와 완전 해시 함수(perfect hash function)의 개념을 살펴봅니다.
키 값 𝑥는 전체 집합(universe) 𝑈 = {0, 1, …, 𝑢 – 2, 𝑢 – 1}에서 추출됩니다. 해시 함수 ℎ는 이 집합 𝑈를 정의역(domain)으로 가지며, 결과 값은 {0, 1, …, 𝑚 – 1} 범위 안에 속합니다. 이때 테이블 크기 𝑚은 항상 전체 집합의 크기 𝑢보다 작거나 같습니다(𝑚 ≤ 𝑢).
완전 해시 함수(Perfect Hash Function)란?
집합 𝑆 ⊆ 𝑈에 속한 모든 원소 𝑥에 대해 해시 값 ℎ(𝑥)가 서로 겹치지 않고 유일하다면, 이 해시 함수 ℎ를 완전 해시 함수라고 부릅니다. 즉, 충돌(collision)이 전혀 발생하지 않는 이상적인 해시 함수를 의미합니다.
완전 해시 함수 ℎ가 최소(minimal)라는 것은 테이블 크기가 저장할 원소의 개수와 정확히 일치하는 경우, 즉 𝑚 = |𝑆|일 때를 말합니다. 이 조건이 성립하면 ℎ는 집합 𝑆와 {0, 1, …, 𝑚 – 1} 사이의 전단사(bijection, 일대일 대응)가 됩니다.
최소 완전 해시 함수가 특히 바람직한 이유는 분명합니다. 길이가 𝑛인 단일 배열 하나만으로 𝑆의 모든 원소를 낭비 없이 저장할 수 있기 때문입니다. 메모리 활용 측면에서 가장 효율적인 형태라 할 수 있습니다.
완전 해시 함수는 왜 찾기 어려운가?
안타깝게도 완전 해시 함수는 매우 드물게 존재합니다. 테이블 크기 𝑚이 원소 개수 𝑛보다 훨씬 큰 경우에도 예외는 아닙니다.
그 이유는 생일 역설(birthday paradox)에서 찾을 수 있습니다. 만약 𝑆의 각 원소가 {0, 1, …, 𝑚 – 1} 범위 내의 임의의 값에 균등하고 독립적으로 대응된다면, 𝑚이 𝑛²보다 훨씬 작아지는 순간 두 원소가 동일한 해시 값을 갖는 충돌이 발생할 확률이 거의 확실해집니다.
이는 실제 생일 문제와 같은 원리입니다. 365개의 날짜 중 단 23명만 모여도 두 사람의 생일이 같을 확률이 절반을 넘습니다. 마찬가지로 해시 테이블에서도 키의 개수가 테이블 크기의 제곱근 수준만 되어도 충돌이 필연적으로 발생합니다.
따라서 실무에서는 완전 해시 함수를 기대하기보다 체이닝(chaining)이나 개방 주소법(open addressing)과 같은 충돌 해결 기법을 함께 활용하는 것이 일반적입니다. 다만 키 집합이 고정된 특수한 상황(예: 컴파일러의 예약어 처리)에서는 최소 완전 해시 함수를 미리 계산해 사용함으로써 O(1) 조회 성능과 무충돌을 동시에 달성할 수 있습니다.