アルゴリズムクイックリファレンス 第2版

5.4

 ブルームフィルタ

■

131

れた個別ビット位置に基づいて、

k

ビットがビット配列にセットされる。このコード

は、ビット単位のシフト演算

<<

を用いて、

1

を適切なビット位置にシフトする。そ

して、ビット単位の

or

演算（

|

）を用いてビット値をセットする。値が追加されたの

かどうかを決定するには、このハッシュ関数から得た同じ

k

ビットをビット単位

and

演算（

&

）を用いて調べる。いずれかのビット位置が

0

なら、値が追加されていない

ことがわかるので、

False

を返す。しかし、この

k

ビット位置がすべて

1

にセットさ

れているなら、値が追加された「かもしれない」（偽陽性）とだけ言える。

5.4.4

 分析

ブルームフィルタ

に必要な全ストレージは、

m

ビットに固定されており、これは

追加格納される値の個数にかかわらず増えることがない。さらに、アルゴリズムは、

固定個数

k

個の探査しか必要としないので、それぞれの挿入と探索を

O(k)

時間で処

理できる。これは定数と

考えてよい。こういった理由から、このアルゴリズムは、

本章の他のアルゴリズムの代替と考えることができる。ビット配列に挿入される値

のために、計算されたビットをうまく分配する効果的ハッシュ関数を設計するのは、

挑戦的だ。ビット配列のサイズは定数だが、偽陽性率を減らすには、十分大きい必

要がある。最後に、他の値の処理を壊す可能性があるので、フィルタから要素を取

り除くことはできない。

ブルームフィルタ

が使える理由は、

k

個のハッシュ関数が一様にランダムと仮定す

るなら、予測