Baike.dev
All toolsOnline toolsAI codingTrendingOpen sourceNewsSubmit
Log in
< Back to tools
F

fastbloom

> 编程语言
Open source

The fastest Bloom filter in Rust. No accuracy compromises. Full concurrency support and compatible with any hasher.

353 stars0 likes0 views
WebsiteGitHub

About

The fastest Bloom filter in Rust. No accuracy compromises. Full concurrency support and compatible with any hasher.

fastbloom

The fastest Bloom filter in Rust. No accuracy compromises. Full concurrency support and compatible with any hasher.

Overview

fastbloom is a fast, flexible, and accurate Bloom filter implemented in Rust. fastbloom's default hasher is SipHash-1-3 using randomized keys but can be seeded or configured to use any hasher. fastbloom is 2-20 times faster and magnitudes more accurate than existing Bloom filter implementations. fastbloom's AtomicBloomFilter is a concurrent Bloom filter that avoids lock contention.

Usage

Due to a different (improved!) algorithm in 0.17.x, Bloomfilters have incompatible serialization/deserialization with prior versions.

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

Basic usage:

rust
use fastbloom::BloomFilter;

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

Instantiate with a target false positive rate:

rust
use fastbloom::BloomFilter;

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

Use any hasher:

rust
use fastbloom::BloomFilter;
use foldhash::fast::RandomState;

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

Full concurrency support. AtomicBloomFilter is a drop-in replacement for RwLock because all methods take &self:

rust
use fastbloom::AtomicBloomFilter;

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

Background

Bloom filters are space-efficient approximate membership set data structures supported by an underlying bit array to track item membership. To insert/check membership, a number of bits are set/checked at positions based on the item's hash. False positives from a membership check are possible, but false negatives are not. Once constructed, neither the Bloom filter's underlying memory usage nor number of bits per item change. See more.

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)

Implementation

fastbloom is blazingly fast because it efficiently derives many index bits from only one real hash per item and leverages other research findings on Bloom filters. fastbloom employs "hash composition" on two 32-bit halves of an original 64-bit hash. Each subsequent hash is derived by combining the original hash value with a different constant using modular arithmetic and bitwise operations. This results in a set of hash functions that are effectively independent and uniformly distributed, even though they are derived from the same original hash function. Computing the composition of two original hashes is faster than re-computing the hash with a different seed. This technique is explained in depth in this paper.

Speed

  • AMD Ryzen 9 5900X 12-Core Processor (3.70 GHz)
  • 64-bit operating system, x64-based processor

Hashers used:

  • xxhash: sbbf
  • Sip1-3: bloom, bloomfilter, probabilistic-collections
  • foldhash: fastbloom

Benchmark source

Accuracy

fastbloom does not compromise accuracy. Below is a comparison of false positive rates with other Bloom filter crates:

Benchmark source

Available Features

  • rand - Enabled by default, this has the DefaultHasher source its random state using thread_rng() instead of hardware sources. Getting entropy from a user-space source is considerably faster, but requires additional dependencies to achieve this. Disabling this feature by using default-features = false makes DefaultHasher source its entropy using foldhash, which will have a much simpler code footprint at the expense of speed.
  • serde - BloomFilters implement Serialize and Deserialize when possible.
  • loom - AtomicBloomFilters use loom atomics, making it compatible with loom testing.

References

  • 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

License

Licensed under either of

  • Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
  • MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Issues· 0 open

View all issuesOpen on GitHub

No open issues yet, or sync has not completed.

> Tags

Rustbloombloom-filterbloomfilterfilter

No comments yet. Be the first to share.

> Details

PublishedAug 1, 2026
UpdatedSep 17, 2026
Category编程语言
PricingOpen source

> Related tools

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言