集合同士をO(1)で比較する（Zobrist Hash）

はじめに

集合を比較するとなると，基本的には$O(N)$かかる．
ところが状況によっては簡潔に管理したかったり，比較をもう少し速くやりたいケースも出てくる．
ここで，そんな時にぴったりなZobrist Hashを取り上げる．

Zobrist Hashの仕組み

集合の各要素に対してランダムに値を割り当てる．
ランダムに割り当てた要素のXORをとり，これを集合のハッシュとする．
ハッシュ値の比較をするだけで集合の一致判定が可能なので，定数時間で可能となる．

例

$\mathrm{hash}(A)=001,\mathrm{hash}(B)=101,\mathrm{hash}(C)=011$のとき，

• $\mathrm{hash}(\lbrace\rbrace)=000$
• $\mathrm{hash}(\lbrace A\rbrace)=001$
• $\mathrm{hash}(\lbrace B\rbrace)=101$
• $\mathrm{hash}(\lbrace C\rbrace)=011$
• $\mathrm{hash}(\lbrace A,B\rbrace)=001\oplus 101=100$
• $\mathrm{hash}(\lbrace A,C\rbrace)=001\oplus 011=010$
• $\mathrm{hash}(\lbrace B,C\rbrace)=101\oplus 011=110$
• $\mathrm{hash}(\lbrace A,B,C\rbrace)=001\oplus 101\oplus 011=111$

表現方法の正当性

XORの性質

1. $x_i\oplus (x_j\oplus x_k) = (x_i\oplus x_j)\oplus x_k$
2. $x_i\oplus x_j = x_j\oplus x_i$
3. $x_i\oplus x_i = 0$
4. $s_i=x_1\oplus\cdots\oplus x_i$に対し，$s_i$はランダムな数
5. $s_i$は一様乱数

衝突の確率

便宜上，部分集合の数を$2^n$，余剰bit数を$m$として話を進める．
すでにある一つの部分集合にハッシュ値が割り当てられているとき，次のハッシュ値決定時に衝突が起こらない確率は以下の通りである．

\frac{2^{n+m}-1}{2^{n+m}}

近似的にこれらの事象は独立であると仮定すると，衝突が起こらない確率は以下の通りとなる．

\Bigl( 1-\frac{1}{2^{n+m}} \Bigr)^{2^n}\simeq \exp(2^{-m})

m	衝突が起こらない確率
0	0.37
1	0.60
2	0.78
4	0.93

上記の数式と表からわかる通り，衝突が起こる確率は極めて低いため，よほど集合の要素数が多く無い限りは衝突のことはあまり気にする必要はないだろう．

例

ABC250 E - Prefix Equality (diff:1421 水)

問題文は以下のリンクを参考にされたし．
https://atcoder.jp/contests/abc250/tasks/abc250_e

集合の比較を行う必要がある．ナイーブな実装では，計算量が$O(NQ)$となるので改善の必要がある．
Zobrist Hashの出番である．
$i=1,\cdots,N$に対し，集合の初めの$i$個の要素を持つ集合をそれぞれハッシュ化し，配列で保存することにより，各クエリの処理を定数時間で行うことを考えよう．
全体の計算量は$O(N+Q)$となる．

実装例

Rust

use proconio::input;
use rand::prelude::*;
use std::collections::{HashMap, HashSet};

fn main() {
    input! {
        n: usize,
        a: [i64; n],
        b: [i64; n],
        q: usize
    };

    let mut items = a.clone();
    items.extend(b.clone());

    // Erase duplicated items
    items.sort_unstable();
    items.dedup();

    let zobrist = Zobrist::new(items);

    // A,Bの部分集合のHash値をあらかじめ計算
    let mut hash_a = vec![0; n]; // i番目までの要素のXORのHash値 
    let mut set_a: HashSet<i64> = std::collections::HashSet::new();
    for (i, &a_item) in a.iter().enumerate() {
        if set_a.contains(&a_item) {
            if i > 0 {
                hash_a[i] = hash_a[i - 1];
            }
        } else {
            set_a.insert(a_item);
            if i > 0 {
                hash_a[i] = hash_a[i - 1] ^ zobrist.hash_table.get(&a_item).unwrap();
            } else {
                let &item_hash = zobrist.hash_table.get(&a_item).unwrap();
                hash_a[i] = item_hash;
            }
        }
    }

    let mut hash_b = vec![0; n];
    let mut set_b: HashSet<i64> = std::collections::HashSet::new();
    for (i, &b_item) in b.iter().enumerate() {
        if set_b.contains(&b_item) {
            if i > 0 {
                hash_b[i] = hash_b[i - 1];
            }
        } else {
            set_b.insert(b_item);
            if i > 0 {
                hash_b[i] = hash_b[i - 1] ^ zobrist.hash_table.get(&b_item).unwrap();
            } else {
                let &item_hash = zobrist.hash_table.get(&b_item).unwrap();
                hash_b[i] = item_hash;
            }
        }
    }

    for _ in 0..q {
        input! {
            x: usize,
            y: usize
        };
        if hash_a[x - 1] == hash_b[y - 1] {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}

#[derive(Debug, Clone)]
struct Zobrist<T: std::hash::Hash + std::cmp::Eq + Copy> {
    items: Vec<T>,
    hash_table: HashMap<T, u32>,
}

impl<T: std::hash::Hash + std::cmp::Eq + Copy> Zobrist<T> {
    fn new(items: Vec<T>) -> Zobrist<T> {
        let mut rng = rand::rngs::StdRng::seed_from_u64(0);

        let mut hash_table = HashMap::new();
        for &item in items.iter() {
            hash_table.insert(item, rng.gen::<u32>());
        }
        Zobrist { items, hash_table }
    }
}

尚，この問題の想定解法とは異なるやり方である．
他にも手法は何通りかあるらしいので余力があれば考えてみるといいだろう．

参考文献

Albert L. Zobrist, A New Hashing Method with Application for Game Playing, 1970