FKS 해싱 편집하기

FKS 해싱(FKS Hashing)은 정적인 키 집합에 대해 O(1) 시간의 탐색을 보장하는 두 단계 해싱(two-level hashing) 기법이다. 이 방법은 Fredman, Komlós, Szemerédi 세 명의 연구자가 제안하였으며, 완전 해싱(perfect hashing)의 대표적 구현으로 널리 알려져 있다.

* 최적 정적 해싱(Optimal Static Hashing)이라고도 불린다.

==개요==
FKS 해싱은 다음과 같은 조건에서 동작하도록 설계된다:
*키 집합이 고정(static)되어 있으며, 삽입/삭제는 없다고 가정
*각 검색 연산이 '''최악의 경우에도''' O(1) 시간에 완료됨
*기대 공간 복잡도는 O(n)이며, 간단한 무작위 해시 함수(universal hashing)를 사용
전체 구조는 다음과 같이 구성된다.
==알고리즘 구조==
===1단계 해싱===
*해시 함수 h: U → {0, 1, ..., m−1} 를 사용하여 키 집합 S의 각 키를 m개의 버킷(bucket)으로 분할함
*보통 m = n (키 개수)로 설정하여 각 슬롯에 평균적으로 1개의 키가 들어가도록 함
===2단계 해싱===
*각 슬롯 i에 대해서 별도의 해시 테이블 T<sub>i</sub>를 구성
*T<sub>i</sub>의 크기는 해당 슬롯의 키 개수 k<sub>i</sub>의 제곱, 즉 k<sub>i</sub>²
*무작위 해시 함수 h<sub>i</sub>를 이용해 T<sub>i</sub> 내에서 '''충돌 없이''' 키를 배치 (완전 해싱)
==동작 예시==
고정된 키 집합이 다음과 같다고 가정하자:

S = {3, 8, 11, 14, 18, 19, 21, 24, 27, 30}  → n = 10, 따라서 m = 10 (1단계 테이블 크기)
===1단계: h(x) = x mod 10===
각 키를 아래와 같이 슬롯에 배치:
{| class="wikitable"
!슬롯 번호 (i)!!키 목록
|-
|0||30
|-
|1||11, 21
|-
|2||2 (없음)
|-
|3||3
|-
|4||14, 24
|-
|5||5 (없음)
|-
|6||6 (없음)
|-
|7||27
|-
|8||8, 18
|-
|9||19
|}이제 각 슬롯에 대해 2차 해시 테이블 구성
===2단계 예시: 슬롯 1 (키: 11, 21)===
*키 개수 k = 2 → 보조 해시 테이블 크기 = 2² = 4
*무작위로 h<sub>1</sub>(x) = (a·x + b) mod p mod 4 라는 형식의 해시 함수 선택
*예: h<sub>1</sub>(11) = 0, h<sub>1</sub>(21) = 2 → 충돌 없음 → 이 해시 함수 채택
다른 슬롯들에도 동일 방식으로 적용하여 모두 충돌 없이 배치 가능하도록 무작위 함수를 반복 시도
==공간 분석==
*1단계 테이블 크기: n
*2단계 테이블의 총 공간은 각 슬롯 i에 대해 k<sub>i</sub>²의 합으로 계산됨
*이 합의 기대값은 O(n)임이 증명되어 있음
==시간 복잡도==
*초기 구성 시간: 기대 O(n)
*탐색: 최악의 경우에도 O(1)
*삽입/삭제는 정적 구조에서는 지원하지 않음
==장점==
*매우 빠른 탐색 (O(1), 최악의 경우 포함)
*정적 집합에서 완전 해싱 구현 가능
*해시 함수 선택 실패 시에도 재시도로 성공 가능 (확률적으로 보장됨)
==단점==
*정적 집합에만 적합 (삽입/삭제가 없는 경우)
*초기 설정이 다소 복잡하고 메모리 낭비 가능성 존재 (k² 사용)
==같이 보기==
*[[완전 해싱]]
*[[유니버설 해시 함수]]
*[[해시 테이블]]
*[[무작위화 알고리즘]]
*[[동적 완전 해싱]]
==참고 문헌==
*Fredman, M. L., Komlós, J., & Szemerédi, E. (1984). Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3), 538–544.
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
[[분류:알고리즘]]