ZobristHash
クラス · Zobrist ハッシュ
template <internal::hashable T, std::uniform_random_bit_generator UniformRandomBitGenerator = Xoroshiro128>
struct ZobristHash;
概要
Zobrist ハッシュ
値ごとに独立な乱数を割り当てて記憶する。複数の値の合成は用途に応じて呼び出し側が選ぶ。 - 総和で合成（Add<result_type> 相当）: 多重集合のハッシュ。同じ値が複数回現れても 打ち消し合わず区別できる（木の同型判定など、部分木の多重集合を比較する場面向き）。 - XOR で合成（Xor<result_type> 相当）: 集合の要素の有無を表すハッシュ。 同じ値をもう一度 XOR すれば打ち消せるため要素の追加・削除を $O(1)$ で反映できるが、 同じ値が偶数回現れると消えてしまうため多重集合の区別には使えない。
テンプレートパラメータ
| 名前 |
説明 |
T |
値の型（hashable であること） |
UniformRandomBitGenerator |
乱数生成器 |
計算量
構築・破棄
| 名前 |
説明 |
計算量 |
(constructor) |
空の対応表を乱数 seed 付きで構築する |
$O(1)$ |
演算子
| 名前 |
説明 |
計算量 |
operator() |
値 x に割り当てられた乱数を返す（初回はその場で割り当てて記憶する） |
期待 $O(1)$ |
メンバ型
| 名前 |
説明 |
計算量 |
result_type |
ハッシュ値の型 |
型エイリアスで実行時計算量はない |