나눗셈 해싱이란?
이 글에서는 나눗셈을 활용한 해싱(division hashing) 기법에 대해 자세히 살펴보겠습니다. 이 방법에서는 다음과 같은 해시 함수를 사용합니다.
ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚
즉, 입력값 x를 해시 테이블의 크기 m으로 나눈 나머지를 해시값으로 사용하는 방식입니다.
해시 테이블의 구조
이 해시 함수를 사용하려면 배열 A[0, …, m-1]을 유지 관리해야 합니다. 여기서 배열의 각 요소는 연결 리스트(linked list)의 머리(head) 노드를 가리키는 포인터 역할을 합니다. 배열 요소 A[i]가 가리키는 연결 리스트 Li에는 h(x) = i를 만족하는 모든 원소 x가 저장됩니다. 이처럼 연결 리스트를 활용해 충돌되는 원소들을 관리하는 기법을 체이닝(chaining)을 이용한 해싱이라고 부릅니다.
삽입, 검색, 삭제 연산의 시간 복잡도
삽입 연산은 매우 빠릅니다. 인덱스 i = h(x)를 계산한 뒤, 리스트 Li에 원소 x를 추가(append 또는 prepend)하면 되므로 O(1) 시간이 걸립니다.
반면 검색 및 삭제 연산은 그렇게 간단하지 않습니다. 먼저 인덱스 i = h(x)를 계산한 후, 원하는 값을 찾거나 리스트가 끝날 때까지 리스트 Li를 처음부터 순회(traverse)해야 합니다. 따라서 이 연산은 해당 리스트 Li의 크기에 비례하는 시간이 소요됩니다.
만약 집합 S가 0, m, 2m, 3m, …, nm 형태의 원소들로만 구성된다면, 모든 원소가 L0에 몰리게 되어 검색과 삭제에 선형 시간(linear time)이 걸리는 최악의 상황이 발생합니다.
균등 분포와 적재율
다행히 이런 극단적인 상황은 실제로 매우 드물게 발생합니다. 예를 들어, 집합 S가 전체 집합(universal set) U에 균등하고 독립적으로 분포되어 있고, U의 크기 u가 m의 배수라면 각 리스트 Li의 기대 크기는 n/m에 불과합니다. 이 경우 검색과 삭제 연산은 O(1 + α) 시간 안에 수행됩니다. 여기서 α는 적재율(load factor)로, 저장된 원소 수 n을 테이블 크기 m으로 나눈 값(n/m)을 의미합니다.
최적의 m 값 선택 방법
앞서 언급한 최악의 시나리오를 피하려면 테이블 크기 m을 현명하게 선택해야 합니다. 일반적으로 다음 두 가지 원칙을 따르는 것이 좋습니다.
- m을 2의 거듭제곱으로 설정하는 것은 피한다 — 이 경우 키의 하위 비트만 해시값에 영향을 주어 특정 패턴의 키가 한쪽 버킷에 몰릴 수 있습니다.
- 2의 거듭제곱에 너무 가깝지 않은 소수(prime number)를 m으로 선택한다 — 소수를 사용하면 키 값이 고르게 분산되어 충돌 가능성을 줄일 수 있습니다.
이러한 원칙을 지키면 나눗셈 해싱이 평균적으로 O(1)에 가까운 성능을 발휘하도록 보장할 수 있습니다.