Bloomフィルタの容量・誤陽性率

標準Bloomフィルタのビット配列容量、必要ハッシュ数、非登録要素の誤陽性率を概算する。

サイズはビット配列のみ。バイト数は8 bitを1 Bとして切り上げ、実装の管理領域は含めません。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

計算する内容

0より大きく100未満の数値。例:1%なら1を入力。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

n=異なる登録要素数、m=配列のビット数、k=ハッシュ数。誤陽性率の近似 p≈(1−e^(−kn/m))^k。理論上の連続最適値は k≈(m/n)ln2、m≈−n ln(p)/(ln2)^2。目標値からは k≈−ln(p)/ln2 の隣接整数を比較し、pを超えない最小整数mを採用。格納B=ceil(m/8)。近似であり実測保証ではありません。

必要ビット数、切り上げ格納バイト数、整数ハッシュ数、近似誤陽性率、1件当たりビット数、推定ビット占有率。

計算例(架空の数値)

計算例:異なる1,000件、目標1%なら7個のハッシュ関数、9,593 bit(1,200 B)で推定誤陽性率は約0.99998%。

適用対象と限界

集合への所属を近似判定する標準Bloomフィルタ。想定登録件数に対する初期容量設計・容量比較。実際のハッシュ関数、ビット相関、データ偏り、重複登録、削除、カウンティング/スケーラブルBloomフィルタ、ヘッダ等の実装メモリ、誤陽性保証値は計算対象外。。

採用した方式

  • 標準Bloomフィルタの近似誤陽性率と容量逆算(Broder–Mitzenmacher 2004 §2.1 / discrete sizing v1.0):対象範囲 独立で一様なハッシュ、標準のビット配列、nは異なる登録要素数/適用地域 global

方法と出典

方法:Broder–Mitzenmacher (2004) §2.1 asymptotic model; discrete sizing v1.0。データ記録日:2026-11-13。