ブルームフィルターの基礎

Bloomフィルターは確率的データ構造で、高速かつメモリ効率よく要素の非存在を確定し、存在は可能性として返すことができる。

ビットベクトルと複数のハッシュ関数を使い、要素追加時に対応ビットを1にセットし、検索時に同ハッシュでビットをチェックする。

ハッシュ関数は独立かつ均一分布かつ高速であることが望ましく、Murmur、xxHash、FNVシリーズなどが代表的に使われる。

誤判定率は(1−e^(−kn/m))^kで近似でき、要素数nとフィルターサイズmから最適なハッシュ数k=(m/n)ln2を算出して制御する。

挿入および検索はO(k)の時間計算量で、フィルターサイズとハッシュ数を調整して誤判定率とメモリ使用量のトレードオフを行う。