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 → 충돌 없음 → 이 해시 함수 채택
다른 슬롯들에도 동일 방식으로 적용하여 모두 충돌 없이 배치 가능하도록 무작위 함수를 반복 시도

== FKS 해싱 Python 예제 ==

아래는 간단한 FKS 해싱 구조를 파이썬으로 구현한 예제이다. 이 코드는 1단계 해시와 2단계 보조 테이블을 구성하며, 보조 해시 함수는 충돌이 없도록 반복 시도하여 선택한다.

<syntaxhighlight lang="python">
import random

# 유니버설 해시 함수 생성기
def generate_hash_function(p, m):
    a = random.randint(1, p - 1)
    b = random.randint(0, p - 1)
    return lambda x: ((a * x + b) % p) % m

# 2차 해싱: 완전 해시 테이블 생성
def build_secondary_table(keys, p):
    n = len(keys)
    if n == 0:
        return None, None
    size = n * n
    while True:
        h = generate_hash_function(p, size)
        table = [None] * size
        collision = False
        for key in keys:
            idx = h(key)
            if table[idx] is not None:
                collision = True
                break
            table[idx] = key
        if not collision:
            return h, table

# FKS 해싱 전체 구성
def build_fks_table(keys):
    p = 1000003  # 큰 소수
    n = len(keys)
    h1 = generate_hash_function(p, n)
    
    # 1단계 테이블 구성
    buckets = [[] for _ in range(n)]
    for key in keys:
        idx = h1(key)
        buckets[idx].append(key)
    
    # 2단계 보조 테이블 구성
    second_level = []
    for bucket in buckets:
        h2, table = build_secondary_table(bucket, p)
        second_level.append((h2, table))
    
    return h1, second_level

# 탐색 함수
def fks_lookup(h1, second_level, key):
    idx = h1(key)
    h2, table = second_level[idx]
    if h2 is None:
        return False
    pos = h2(key)
    return table[pos] == key

# 예제 실행
keys = [3, 8, 11, 14, 18, 19, 21, 24, 27, 30]
h1, second_level = build_fks_table(keys)

# 검색 테스트
test_keys = [14, 22, 30, 7]
for k in test_keys:
    result = fks_lookup(h1, second_level, k)
    print(f"Key {k} found? {result}")
</syntaxhighlight>'''출력 예시'''<syntaxhighlight lang="text">
Key 14 found? True
Key 22 found? False
Key 30 found? True
Key 7 found? False
</syntaxhighlight>

이 코드는 정적 키 집합을 기반으로 FKS 해싱 구조를 구성하고, 주어진 키가 존재하는지 O(1) 시간에 탐색할 수 있는지를 테스트한다. 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.
[[분류:알고리즘]]