Day 108-Q3 | Cuckoo Hashing（カッコウハッシュ）

問題

整数の集合 $S$（初期状態は空）に対して、$Q$個のクエリを順に処理せよ。

1 x: $S$に$x$を追加する（既に存在する場合は何もしない）
2 x: $S$から$x$を削除する（存在しない場合は何もしない）
3 x: $S$に$x$が存在すれば1、存在しなければ0を出力する

Cuckoo Hashing（カッコウハッシュ）を実装せよ。2つのハッシュテーブル$T_1, T_2$と2つのハッシュ関数$h_1,h_2$を用意し、要素$x$は必ず$T_1[h_1(x)]$または$T_2[h_2(x)]$のどちらかに格納する。挿入時に衝突したら既存の要素を「追い出して」もう一方のテーブルへ玉突き的に押し出す。押し出しの連鎖が一定回数を超えたら、新しいハッシュ関数でテーブル全体を再構築（rehash）する。

この構成により、クエリ3 x（存在判定）は必ず2箇所だけを見れば済むため最悪計算量$O(1)$、1 x（挿入）は償却期待$O(1)$で処理できる。

入力形式

Q
query_1
query_2
...
query_Q

制約

$1 \le Q \le 2\times10^5$

$0 \le x \le 10^9$

入出力例

入力例1

出力例1

15,23,8を追加。23は存在するので1、100は存在しないので0。15を削除。15は存在しないので0。42を追加し存在するので1。8はまだ存在するので1。

概念図: 玉突き挿入（eviction chain）

ヒント（段階的開示）

ヒント1: 方向性

Pythonのdict/setは内部でオープンアドレッシング法のハッシュテーブルを使っており平均$O(1)$だが、最悪ケースでの探索回数の保証（「必ず高々2箇所しか見ない」という強い性質）は持たない。Cuckoo Hashingは、探索を「2つの固定候補位置だけを見ればよい」という設計にすることで、探索だけは最悪計算量でも$O(1)$という強い保証を得る珍しい方式である。

ヒント2: アプローチ

要素$x$は常に$T_1[h_1(x)]$か$T_2[h_2(x)]$のどちらかにいる、という不変条件を維持する。挿入時、$T_1[h_1(x)]$が空ならそこに置いて終了。埋まっていたら、そこにいた要素$y$を追い出して$x$を置き、追い出された$y$を今度は$T_2[h_2(y)]$に入れようとする（また埋まっていたらさらに追い出して…と$T_1,T_2$を交互に繰り返す）。この「玉突き」が一定回数を超えて収束しない場合はサイクルに陥ったとみなし、新しいランダムなハッシュ関数でテーブル全体（現在の全要素＋玉突きの途中で手放せなくなった要素）を再構築する。

削除は単純：$T_1[h_1(x)]==x$か$T_2[h_2(x)]==x$のどちらかを見つけてNoneにするだけ。

ヒント3: 誘導（コード骨格）

def raw_insert(x, max_chain):
    # 玉突き挿入。成功したら (True, None)。
    # max_chain回動かしても収まらない場合は (False, はぐれた要素) を返す。
    # ★重要: 失敗時、それまでに動かした要素は全てテーブルのどこかに書き戻り済みで、
    #   最後に「手元に残った1個」だけが未配置。この要素を rehash 側で必ず拾うこと。
    cur = x
    table = 1
    for _ in range(max_chain):
        if table == 1:
            p = h1(cur)
            if T1[p] is None:
                T1[p] = cur
                return True, None
            cur, T1[p] = T1[p], cur  # 追い出し
            table = 2
        else:
            p = h2(cur)
            if T2[p] is None:
                T2[p] = cur
                return True, None
            cur, T2[p] = T2[p], cur
            table = 1
    return False, cur  # curが「はぐれた要素」

模範解答 (Python)

import sys, random

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    Q = int(data[idx]); idx += 1

    rnd = random.Random(2024)
    MOD = (1 << 61) - 1
    size = 4

    def rand_params():
        return (rnd.randrange(1, MOD), rnd.randrange(0, MOD))
    a1, b1 = rand_params()
    a2, b2 = rand_params()
    T1 = [None] * size
    T2 = [None] * size

    def h1(x):
        return ((a1 * x + b1) % MOD) % size

    def h2(x):
        return ((a2 * x + b2) % MOD) % size

    def raw_insert(x, max_chain):
        cur = x
        table = 1
        for _ in range(max_chain):
            if table == 1:
                p = h1(cur)
                if T1[p] is None:
                    T1[p] = cur
                    return True, None
                cur, T1[p] = T1[p], cur
                table = 2
            else:
                p = h2(cur)
                if T2[p] is None:
                    T2[p] = cur
                    return True, None
                cur, T2[p] = T2[p], cur
                table = 1
        return False, cur

    def rehash(new_size, extra):
        nonlocal T1, T2, a1, b1, a2, b2, size
        elems = [v for v in T1 if v is not None] + [v for v in T2 if v is not None]
        if extra is not None:
            elems.append(extra)
        size = new_size
        while True:
            a1, b1 = rand_params()
            a2, b2 = rand_params()
            T1 = [None] * size
            T2 = [None] * size
            max_chain = max(8, 4 * size.bit_length())
            ok = True
            for v in elems:
                succ, leftover = raw_insert(v, max_chain)
                if not succ:
                    ok = False
                    break
            if ok:
                break

    def exists(x):
        p1 = h1(x)
        if T1[p1] == x:
            return 1
        p2 = h2(x)
        if T2[p2] == x:
            return 1
        return 0

    def insert(x):
        if exists(x):
            return
        max_chain = max(8, 4 * size.bit_length())
        ok, leftover = raw_insert(x, max_chain)
        while not ok:
            rehash(size * 2, leftover)
            max_chain = max(8, 4 * size.bit_length())
            ok, leftover = (True, None) if exists(x) else raw_insert(x, max_chain)

    def delete(x):
        p1 = h1(x)
        if T1[p1] == x:
            T1[p1] = None
            return
        p2 = h2(x)
        if T2[p2] == x:
            T2[p2] = None
            return

    out = []
    for _ in range(Q):
        t = data[idx]; idx += 1
        x = int(data[idx]); idx += 1
        if t == b'1':
            insert(x)
        elif t == b'2':
            delete(x)
        else:
            out.append(str(exists(x)))
    print("\n".join(out))


solve()

計算量: existsは常に定数回（2箇所）のみ参照するため最悪$O(1)$。insertは玉突きが収まれば償却$O(1)$、収まらなければ再ハッシュ（$O($現在の要素数$)$）が発生するが、テーブルを毎回2倍に拡張するため償却計算量は$O(1)$に収まる。20,000回のランダムな挿入・削除・存在判定をsetベースの参照実装と突き合わせるストレステストで一致を確認済み。

Step-by-Step 解説

12つのハッシュ関数を乗法ハッシュで作る
$h_i(x) = ((a_i \cdot x + b_i) \bmod M) \bmod \text{size}$の形の乗法ハッシュを使う。$M$には大きな素数（メルセンヌ素数$2^{61}-1$）を使い、$a_i,b_i$を毎回ランダムに選び直せるようにしておく。

2玉突き挿入で不変条件を保つ
raw_insertは新要素$x$を$T_1[h_1(x)]$に置こうとし、埋まっていたら既存の要素を追い出して$T_2$側へ、そこでも埋まっていたらまた追い出して$T_1$側へ、と交互に繰り返す。これにより常に「動かした要素は全てどこかのテーブルに存在する」という不変条件が保たれる（最後に「手に持ったまま行き場のない1個」が残る場合を除く）。

3失敗時の「はぐれた要素」を必ず回収してから再ハッシュする
max_chain回追い出しても収まらない場合、それまでの玉突きで動かした要素は全てテーブル内のどこかに書き戻り済みだが、最後に手元に残った1個（cur）だけはテーブルのどこにも存在しない。この要素を明示的にextraとしてrehashに渡すことが正しさの要である。

4再ハッシュはテーブルサイズを2倍にしランダムパラメータを取り直す
rehashは現在の全要素（＋はぐれた要素）を新しいランダムなハッシュ関数で作り直したテーブルに再挿入する。1回で全要素が収まらなければさらに別のランダムパラメータで再試行する。

よくあるミス

ミス	原因	正しい書き方
挿入失敗時、玉突き中に「はぐれた要素」を回収せず再ハッシュする	`rehash`が`T1`,`T2`の中身だけをスキャンして再構築対象を決めてしまい、最後に手元に残っていた要素を見落として消失させる（本問題の検証中に実際に発生したバグ）	失敗を表す戻り値に「はぐれた要素」を含め、`rehash`の対象リストへ明示的に追加する
`exists`の実装で内部の`set`/`dict`など別の補助構造を参照してしまう	Cuckoo Hashingの本質（2箇所だけを見れば存在判定できる）を検証できなくなる	`exists`は必ず`T1[h1(x)]`と`T2[h2(x)]`の2箇所だけを参照する実装にする
削除時に$T_1$側だけ確認して$T_2$側の確認を省略する	要素が$T_2$側に格納されているケースを削除し損なう	`T1[h1(x)]==x`を確認し、一致しなければ必ず`T2[h2(x)]==x`も確認する
再ハッシュの度にテーブルサイズを固定のままハッシュ関数だけ変える	要素数がテーブルサイズに対して増えすぎると玉突きが収束しにくくなり、再ハッシュが無限ループに近づく	再ハッシュのたびにテーブルサイズを2倍に拡張し、負荷率を一定以下に保つ

次のステップ

発展: 3つ以上のハッシュテーブル・ハッシュ関数を使う「d-ary Cuckoo Hashing」に拡張し、負荷率をさらに高める
発展: 「バケット」（1スロットに複数要素を許す）を導入したCuckoo Hashing with Bucketsに拡張し、玉突きの発生頻度自体を減らす
次回予告: 複数文字列の最長共通部分文字列（一般化Suffix Array + LCP配列 + スライディングウィンドウ）

自己評価

完全理解おおむね理解要復習

Day 108-Q3 — Cuckoo Hashing（カッコウハッシュ）

問題