Day 106-Q3 — FKS完全ハッシュ法（Perfect Hashing）

2026-07-29 赤色 Master / Phase 8+ ★★★★★★★★★ 2段階ユニバーサルハッシュ・最悪O(1)検索

問題

$N$個の相異なる整数からなる静的集合$A=\{A_1,\dots,A_N\}$が与えられる。続く$Q$個のクエリ整数$x_1,\dots,x_Q$それぞれについて$x_j\in A$かどうかを判定せよ。

通常のハッシュテーブルは最悪$O(N)$になり得るが、FKS完全ハッシュ法（Fredman–Komlós–Szemerédi）は2段階のユニバーサルハッシュでクエリ1件あたり最悪$O(1)$を保証する。1段目で$N$個を$N$バケツに振り分け「バケツサイズの2乗和$\le4N$」となる関数を見つけ、2段目で各バケツをサイズ$m_i^2$のテーブルに衝突なく詰め込む。

入力形式

N Q
A_1 A_2 ... A_N
x_1
...
x_Q

制約

$1 \le N,Q \le 10^5$
$0 \le A_i \le 10^{18}$（相異なる）
$0 \le x_j \le 10^{18}$

入出力例

入力例1

5 4
3 7 15 21 42
7
8
21
1000000000

出力例1

Yes
No
Yes
No

概念図: 2段階ハッシュテーブル

1段目でバケツに振り分け、2段目で各バケツを衝突なく敷き詰める h1(x) bucket 0 bucket 1 bucket 2 bucket 3 要素 x → h1で振り分け 2段目: サイズ$m^2$のテーブル (bucket 0, m=2) h2で衝突なく配置（衝突したらa2,b2を再抽選） クエリ: h1でバケツ特定 → そのバケツのh2でスロット特定 → 一致確認、で終わり（配列参照2回のみ）

ヒント（段階的開示）

ヒント1: 方向性
Pythonのsetは実用上高速だが最悪計算量を理論的に保証したことにはならない。「1つのハッシュ関数だけで全要素を1つのテーブルに詰め込む」発想を捨て、「衝突が起きた要素同士を、さらに別のハッシュ関数で再分配する」入れ子構造を考える。
ヒント2: アプローチ
ユニバーサルハッシュ$h_{a,b}(x)=((ax+b)\bmod p)\bmod m$を使う。1段目は「バケツサイズの2乗和$\le4N$」を満たすまで$(a,b)$を選び直す（マルコフの不等式より確率$1/2$以上で成功）。2段目は各バケツを「サイズ$m^2$のテーブルに衝突なく詰め込める」まで選び直す（birthday paradoxの逆で確率$1/2$以上）。正しさは乱数の値に依存せず、構築時間だけに影響する。
ヒント3: 誘導（コード骨格） 
while True:
    a1, b1 = 乱数
    buckets = [[] for _ in range(N)]
    for x in A: buckets[h(a1,b1,x,N)].append(x)
    if sum(len(b)**2 for b in buckets) <= 4*N: break

for bucket in buckets:
    size = max(len(bucket)**2, 1)
    while True:
        a2, b2 = 乱数
        # bucketの全要素をh(a2,b2,x,size)でslotsに入れ衝突チェック
        # 衝突なければ採用

模範解答 (Python)

import sys
import random

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    values = []
    for _ in range(n):
        values.append(int(data[idx])); idx += 1
    queries = []
    for _ in range(q):
        queries.append(int(data[idx])); idx += 1

    rnd = random.Random(12345)
    P = (1 << 61) - 1

    def rand_ab():
        return rnd.randint(1, P - 1), rnd.randint(0, P - 1)

    def h(a, b, x, mod):
        return ((a * x + b) % P) % mod

    while True:
        a1, b1 = rand_ab()
        buckets = [[] for _ in range(n)]
        for x in values:
            buckets[h(a1, b1, x, n)].append(x)
        if sum(len(bk) ** 2 for bk in buckets) <= 4 * n:
            break

    level2 = []
    for bucket in buckets:
        sz = len(bucket)
        size = max(sz * sz, 1)
        while True:
            a2, b2 = rand_ab()
            slots = [None] * size
            ok = True
            for x in bucket:
                pos = h(a2, b2, x, size)
                if slots[pos] is not None:
                    ok = False
                    break
                slots[pos] = x
            if ok:
                level2.append((a2, b2, size, slots))
                break

    out = []
    for x in queries:
        i = h(a1, b1, x, n)
        a2, b2, size, slots = level2[i]
        pos = h(a2, b2, x, size)
        found = slots[pos] == x
        out.append("Yes" if found else "No")
    print("\n".join(out))


solve()
計算量: 構築 期待$O(N)$、クエリ1件$O(1)$（配列参照2回のみ）。ランダム200ケースでPython setとの一致を確認済み。

Step-by-Step 解説

1ユニバーサルハッシュ関数
$h_{a,b}(x)=((ax+b)\bmod p)\bmod m$は、異なる2値が同じ値に写る確率が$\le1/m$という性質を持つ。
21段目: バケツサイズの2乗和を抑える
$\sum\binom{m_i}{2}$の期待値は$N/2$未満。マルコフの不等式より、$\sum m_i^2\le3N$程度に収まる試行が高確率で（期待2回程度で）見つかる。
32段目: 衝突なしテーブルの構築
サイズ$m$のバケツをサイズ$m^2$のテーブルに詰め込むとき、衝突が1つも起きない確率は$1/2$超（Booleの不等式）。期待2回程度の再抽選で成功する。
4クエリ処理
$h_1$で該当バケツ、そのバケツの$h_2$でスロットを特定するだけ。構築にどれだけ乱択の再試行がかかっても、構築後のクエリは常に厳密$O(1)$。

よくあるミス

ミス原因正しい書き方
slots[pos]がNoneでなければ即Yesとする存在しない値がたまたま既存要素と同じスロットに写像されうる必ずslots[pos]==xまで確認する
2段目のテーブルサイズをバケツサイズmのまま使う衝突回避には$\Omega(m^2)$のサイズが必要各バケツのテーブルサイズは$m^2$（$m=0$なら1）にする
1段目の再抽選条件を「衝突なし」にするN個をN個のバケツに完全衝突なく振り分ける試行は指数時間かかりうる「バケツサイズの2乗和が$O(N)$」という緩い条件で十分
乱数シード固定に過度にこだわる正当性は乱数値に依存しないため本質的な問題ではない再現性が必要な場合のみ固定シードを使う

次のステップ

  • 発展: 動的集合（追加・削除）に対応する完全ハッシュ（Dynamic Perfect Hashing）
  • 発展: Cuckoo Hashing（かっこうハッシュ）との実装・定数倍の比較
  • 次回予告: Simplex法（線形計画法の単体法・Bland's ruleによるcycling回避）

自己評価

自分の回答

気づき・メモ