FKS 해싱 편집하기 (부분)

== 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단계 해시는 충돌이 없는 해시 함수를 무작위로 선택하여 반복 구성하며, 평균적으로 빠르게 종료된다.