- 空間効率の良い[[確率的データ構造]] - あるデータが集合に含まれているかの判定ができる。偽陽性（含まれていないのに含まれていると誤判定）がある。偽陰性（含まれているのに、含まれていないと誤判定）はない。 - 集合に要素を追加することはできるが、削除することはできない。 # アルゴリズム - 長さ$m$、初期値0のビット配列$B$がある - $k$個の異なるハッシュ関数がある（キーを$m$ビット配列のいずれかにマップする） ## 要素の追加 - 要素を$k$個のハッシュ関数に入力し、$k$個の配列インデックス$i_0, ..., i_{k-1}$を得る - $\forall i \in \lbrace 0, ..., k-1 \rbrace: B[i_i] = 1$とする ## 要素のクエリ - 要素を$k$個のハッシュ関数に入力し、$k$個の配列インデックス$i_0, ..., i_{k-1}$を得る - $\forall i \in \lbrace 0, ..., k-1 \rbrace: B[i_i]$のうち、1つでも0があれば含まれていないことがわかる - すべてが1であれば、含まれているとする（たまたま他の要素で1となってしまった偽陽性の可能性はある） # 参考 - https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF