最終更新: 2026-07-13

ブルームフィルタのサイズ

ブルームフィルタは「この要素をおそらく以前に見たか？」という 1 つの問いに答えるための省メモリなデータ構造です。キーそのものは保持せずビット配列だけを持ち、小さく調整可能な偽陽性の確率と引き換えに大きなメモリ削減を得ます。その形を決めるのは 2 つの数、すなわち格納する想定要素数と許容できる偽の一致の頻度で、そこから最適なビット配列長とハッシュ関数の数が直接導かれます。

計算式

想定要素数 $n$、目標偽陽性率 $p$ に対して、メモリを最小化するビット配列長は次のとおりです。

このとき最適なハッシュ関数の数は

を最も近い整数に丸めたものになります。ここで $m$ はビット数、$k$ は各要素に適用する独立なハッシュ関数の数、$\ln 2 \approx 0.693$ です。$p$ は 1 未満の確率なので自然対数は負になり、どちらの式も正の値を返します。

計算例。 100 万要素（$n = 1{,}000{,}000$）を偽陽性率 1%（$p = 0.01$）で扱うフィルタ：

100 万要素を 1% で扱うには約 1.14 MiB のメモリと 7 個のハッシュ関数が必要で、要素あたり約 9.6 ビットに相当します。この値はその精度であれば要素数によらず一定です。

要素あたりのビット数と精度の階段

サイズの式は $n$ に比例するため、要素あたりの記憶コスト $m / n = -\ln p / (\ln 2)^2$ は目標率だけで決まります。これは精度の予算を比べるうえで分かりやすい指標です。

偽陽性率が 10 分の 1 になるごとに、要素あたり約 4.8 ビットとハッシュ関数およそ 3 個が加わります。メモリは線形にしか増えないのに誤り率は幾何級数的に下がる点が、ブルームフィルタの魅力です。

ハッシュ関数の数が重要な理由

配列サイズを固定したとき、ハッシュ関数が少なすぎるとビットが疎になり偶然一致しやすくなり、多すぎるとほぼすべてのビットが立つほど密に埋まります。ちょうど半分のビットを立てる均衡点が $k = (m/n)\ln 2$ です。$k$ は整数でなければならないので丸められ、実際の偽陽性率はその丸めた値から再計算します。

上の例では丸めた $k = 7$ により約 1.004% となり、理想の $k$ が 6.64 で整数でなかったぶん、1% の目標をわずかに上回ります。

ブルームフィルタにできること・できないこと

ブルームフィルタは偽陰性を出しません。「要素は存在しない」と言えば、それは確実です。唯一の誤りは偽陽性で、本計算はその率を設計します。標準のフィルタは挿入と照会に対応しますが削除には対応しません。ビットが要素間で共有されており、ある要素のビットを消すと他が壊れるためです。削除が必要なときは、各ビットを小さなカウンタに置き換えるカウンティングブルームフィルタ（メモリは数倍）や、同程度のサイズで削除を提供するクックーフィルタが選択肢になります。

注意点が 1 つあります。フィルタは固定の $n$ に合わせて設計されます。想定よりずっと多くの要素を挿入すると配列が飽和し、偽陽性率が目標を超えます。増加が見込まれる場合は最初から大きめの数で設計するか、複数のフィルタを連結するスケーラブルな方式を使ってください。

実装での丸め

式から得られる $m$ がきりのよい数になることはまれです。実際の実装はマシンワードやメモリページ単位で確保するため $m$ を切り上げ、その結果、達成される偽陽性率は目標をわずかに下回ります（うれしい誤差です）。ここに表示されるサイズは、その丸め前の理論的な最小値です。

関連する計算

ブルームフィルタはハッシュに依存するため、2 つの要素が同じハッシュを共有する確率は同じ誕生日の数学に支配されます。ハッシュ衝突確率の計算 をご覧ください。固定長の識別子については UUID 衝突確率の計算 が UUID に同じ考え方を適用し、シャノンエントロピーの計算 はデータが持つ情報量を測ります。