FKS 해싱

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

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

1 개요

FKS 해싱은 다음과 같은 조건에서 동작하도록 설계된다:

• 키 집합이 고정(static)되어 있으며, 삽입/삭제는 없다고 가정
• 각 검색 연산이 최악의 경우에도 O(1) 시간에 완료됨
• 기대 공간 복잡도는 O(n)이며, 간단한 무작위 해시 함수(universal hashing)를 사용

전체 구조는 다음과 같이 구성된다.

2 알고리즘 구조

2.1 1단계 해싱

• 해시 함수 h: U → {0, 1, ..., m−1} 를 사용하여 키 집합 S의 각 키를 m개의 버킷(bucket)으로 분할함
• 보통 m = n (키 개수)로 설정하여 각 슬롯에 평균적으로 1개의 키가 들어가도록 함

2.2 2단계 해싱

• 각 슬롯 i에 대해서 별도의 해시 테이블 T_i를 구성
• T_i의 크기는 해당 슬롯의 키 개수 k_i의 제곱, 즉 k_i²
• 무작위 해시 함수 h_i를 이용해 T_i 내에서 충돌 없이 키를 배치 (완전 해싱)

3 동작 예시

고정된 키 집합이 다음과 같다고 가정하자:

S = {3, 8, 11, 14, 18, 19, 21, 24, 27, 30} → n = 10, 따라서 m = 10 (1단계 테이블 크기)

3.1 1단계: h(x) = x mod 10

각 키를 아래와 같이 슬롯에 배치:

슬롯 번호 (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차 해시 테이블 구성

3.2 2단계 예시: 슬롯 1 (키: 11, 21)

• 키 개수 k = 2 → 보조 해시 테이블 크기 = 2² = 4
• 무작위로 h₁(x) = (a·x + b) mod p mod 4 라는 형식의 해시 함수 선택
• 예: h₁(11) = 0, h₁(21) = 2 → 충돌 없음 → 이 해시 함수 채택

다른 슬롯들에도 동일 방식으로 적용하여 모두 충돌 없이 배치 가능하도록 무작위 함수를 반복 시도

4 FKS 해싱 Python 예제

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

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}")

출력 예시

Key 14 found? True
Key 22 found? False
Key 30 found? True
Key 7 found? False

이 코드는 정적 키 집합을 기반으로 FKS 해싱 구조를 구성하고, 주어진 키가 존재하는지 O(1) 시간에 탐색할 수 있는지를 테스트한다. 2단계 해시는 충돌이 없는 해시 함수를 무작위로 선택하여 반복 구성하며, 평균적으로 빠르게 종료된다.

5 공간 분석

• 1단계 테이블 크기: n
• 2단계 테이블의 총 공간은 각 슬롯 i에 대해 k_i²의 합으로 계산됨
• 이 합의 기대값은 O(n)임이 증명되어 있음

6 시간 복잡도

• 초기 구성 시간: 기대 O(n)
• 탐색: 최악의 경우에도 O(1)
• 삽입/삭제는 정적 구조에서는 지원하지 않음

7 장점

• 매우 빠른 탐색 (O(1), 최악의 경우 포함)
• 정적 집합에서 완전 해싱 구현 가능
• 해시 함수 선택 실패 시에도 재시도로 성공 가능 (확률적으로 보장됨)

8 단점

• 정적 집합에만 적합 (삽입/삭제가 없는 경우)
• 초기 설정이 다소 복잡하고 메모리 낭비 가능성 존재 (k² 사용)

9 같이 보기

• 완전 해싱
• 유니버설 해시 함수
• 해시 테이블
• 무작위화 알고리즘
• 동적 완전 해싱

10 참고 문헌

• 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.