fastbloom

Rustで最速のブルームフィルター。精度を犠牲にしません。完全な並行処理対応で、あらゆるハッシャーと互換性があります。

概要

fastbloomはRustで実装された高速で柔軟かつ高精度なブルームフィルターです。fastbloomのデフォルトハッシャーはランダム化されたキーを使用するSipHash-1-3ですが、シードを設定したり任意のハッシャーを使用するように構成できます。fastbloomは既存のブルームフィルター実装よりも2〜20倍高速で、はるかに高精度です。fastbloomのAtomicBloomFilterはロック競合を回避する並行ブルームフィルターです。

使用法

0.17.xでは異なる（改善された！）アルゴリズムのため、ブルームフィルターのシリアライズ/デシリアライズは以前のバージョンと互換性がありません。

# Cargo.toml
[dependencies]
fastbloom = "0.17.0"

基本的な使い方:

use fastbloom::BloomFilter;
let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

ターゲットの誤検出率を指定してインスタンス化する:

use fastbloom::BloomFilter;
let filter = BloomFilter::with_false_pos(0.001).items(["42", "🦀"].iter());
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

任意のハッシャーを使用してください:

use fastbloom::BloomFilter;
use foldhash::fast::RandomState;
let filter = BloomFilter::with_num_bits(1024)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());

完全な同時実行サポート。AtomicBloomFilterはすべてのメソッドが&selfを取るため、RwLockの代わりにそのまま使えます：

use fastbloom::AtomicBloomFilter;
let filter = AtomicBloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

背景

ブルームフィルターは、アイテムの所属を追跡するための基盤となるビット配列によってサポートされる、空間効率の良い近似的な集合メンバーシップデータ構造です。メンバーシップの挿入/確認には、アイテムのハッシュに基づいた位置の複数のビットが設定/確認されます。メンバーシップチェックでの偽陽性はあり得ますが、偽陰性はありません。構築後は、ブルームフィルターの基盤となるメモリ使用量もアイテムあたりのビット数も変わりません。詳細はこちら。

hash(4) ──────┬─────┬───────────────┐
              ↓     ↓               ↓
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0
  ↑           ↑           ↑
  └───────────┴───────────┴──── hash(3) (not in the set)

実装

fastbloom は、各アイテムごとに実際のハッシュを1回だけ計算し、多くのインデックスビットを効率的に導出することで非常に高速です。また、Bloomフィルターに関する他の研究成果を活用しています。fastbloom は、元の64ビットハッシュの2つの32ビット半分に対して「ハッシュ合成」を行います。各後続のハッシュは、元のハッシュ値と異なる定数を組み合わせ、モジュラー演算とビット演算を用いて導出されます。これにより、同じ元のハッシュ関数から派生したにもかかわらず、実質的に独立かつ均一に分布したハッシュ関数の集合が得られます。2つの元のハッシュの合成を計算する方が、異なるシードで再度ハッシュを計算するよりも高速です。この手法はこの論文で詳細に説明されています。

速度

• AMD Ryzen 9 5900X 12コアプロセッサ (3.70 GHz)
• 64ビットオペレーティングシステム、x64ベースプロセッサ

使用したハッシャー:

- xxhash: sbbf

- Sip1-3: bloom, bloomfilter, probabilistic-collections

- foldhash: fastbloom

ベンチマークソース

精度

fastbloom は精度を犠牲にしません。以下は他のBloomフィルタークレートとの誤検知率の比較です:

ベンチマークソース

利用可能な機能

• rand - デフォルトで有効。DefaultHasher がハードウェアソースではなく thread_rng() を使用して乱数状態を取得します。ユーザースペースのソースからエントロピーを得る方がかなり高速ですが、追加の依存関係が必要です。この機能を default-features = false で無効にすると、DefaultHasher は foldhash を使ってエントロピーを取得し、速度の代わりにコードフットプリントがよりシンプルになります。
• serde - 可能な場合に BloomFilter が Serialize と Deserialize を実装します。
• loom - AtomicBloomFilter は loom のアトミックを使用し、loomテストに対応します。

参考文献

• Bloom filter - Wikipedia
• Bloom filters debunked: Dispelling 30 Years of bad math with Coq!
• Bloom Filter Interactive Demonstration
• Cache-, Hash- and Space-Efficient Bloom Filters
• Less hashing, same performance: Building a better Bloom filter
• A fast alternative to the modulo reduction

ライセンス

以下のいずれかの条件でライセンスされています

• Apache License, Version 2.0

(LICENSE-APACHE または http://www.apache.org/licenses/LICENSE-2.0)

• MIT ライセンス

(LICENSE-MIT または http://opensource.org/licenses/MIT)

お好みで選択可能です。

貢献

明示的に異なる表記がない限り、Apache-2.0ライセンスで定義される あなたによって意図的に提出された、本作品への貢献は、 追加の条項や条件なしに、上記の二重ライセンスとなります。

--- Tranlated By Open Ai Tx | Last indexed: 2026-05-15 ---