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

はじめに 集合を比較するとなると，基本的には$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\r