ブルームフィルタ
「この要素は集合に含まれるか」に答える確率的データ構造。答えは「たぶんある」か「確実にない」。偽陰性はなく、偽陽性率は調整できる。
Burton Bloomが1970年に考案した。ビット配列とk個のハッシュ関数でできている。メモリ効率は極めて高く、偽陽性率1%なら要素の大きさにかかわらず1要素あたり約10ビットで済む。BitcoinのSPVノード、BigTableやHBaseの行レベルフィルタ、CDNのキャッシュ存在確認、ブラウザの悪意あるURLリストなどで使われる。2014年登場のCuckooフィルタは、削除に対応した現代的な代替だ。