ブルームフィルタ
また、衝突の発生率を無視するならハッシュテーブル(ただし、配列には値が入っているか否かの情報のみを格納する)も時間的・空間的に有利であり、これは実質的に、k = 1 のブルームフィルタと同じものとなる。
ブルームフィルタの珍しい特徴は、要素の追加も要素の有無の質問も O(k)の固定時間しかかからず、格納されている要素数には全く影響されないことである。固定サイズのデータ構造でこのような特徴を持つデータ構造はないが、衝突のない疎なハッシュテーブルはブルームフィルタよりも高速である場合がある。ブルームフィルタをハードウェアで実装すると、k 個のハッシュ関数を論理回路化して並行動作できるため、高速化が容易である。
空間効率を理解するために、k = 1 のブルームフィルタの場合を考えて見よう。k = 1 のときに偽陽性発生率を十分低くするには、ビットが 1 となる割合を十分少なくしなければならない。つまり、ビット配列はかなり大きくなり、その内容のほとんどは 0 になる。このときの配列のもつ情報量もサイズに比較して低くなる。通常の(k が 1 より大きい)ブルームフィルタでは、1 となるビット数が増えても同程度の偽陽性発生率を維持できる。従って k と m というパラメータの組み合わせを適切にすれば、ほぼ半分程度のビットが 1 となるようにでき、ちょうど情報量を最大にして冗長性を最小にできる。
ブルームフィルタで偽陽性が発生していて両方のフィルタにキーが存在すると判定された場合には問題が発生する。連想配列であるから、同じキーを両方のブルームフィルタには追加していない。しかし、どちらのフィルタが嘘をついているのかを、このままでは判別できない。このため、別の小さな2つのフィルタ A1 と B1 を用意する。そうして 値が 0 でB0 では偽陽性となるキーを A1 に、また値が 1 でA0 では偽陽性となるキーを B1 に登録しておく。 そうして A0 にも B0 にも存在するとされたキーについては、そのキーを A1 と B1 で検証する。
しかしこの段階でもまだ偽陽性が発生する可能性はある。これに対しても同じ解決策を再帰的に適用する。フィルタのペアは上位のペアの片方にマップされていてもう片方で偽陽性となるものだけを登録するので、登録すべきキーの数は劇的に減っていき、ある段階になると確率的ではないデータ構造に収めることのできる数になる。また、このフィルタの階層構造を下っていかなければならない場合の数は非常に少ないため、全体としての検索時間は線形時間になる。また、全体で必要な空間のほとんどは最初のフィルタペアのものであり、n には無関係である。