ブルームフィルタ
逆にそれらの位置にある全てのビットが 1 であれば、その要素はその集合に含まれているか、またはそれらのビットは他の要素を追加したときにたまたま全部 1 になった(偽陽性)ものであると考えられる。
この単純なブルームフィルタからは要素を削除することはできない。要素は k 個のビットにマッピングされており、そのうちの一箇所でもビットを 0 にすれば削除できる。しかし、異なる要素についても同じビットが 1 になることで表されている可能性があるので、ビットを 0 にすると他の要素までも削除してしまうことになる。そうしていまのデータ構造だけからではそのような衝突が発生しているのかどうかは判定できない。したがって無理やり削除すると、本来であれば発生しないはずの偽陰性が発生してしまう。
それでも、キー値すべてを列挙するようなデータ構造を用いたのでは巨大になりすぎる場合にはブルームフィルターは役に立つ。要素を追加していって偽陽性発生率が高くなりすぎた場合には、ブルームフィルタを再生成する必要が生じるが、これは比較的まれな事象である。