#bloom-filter #bloom #filter #bit-vector

bloomy

A simple Bloom filter using only two hash functions

4 stable releases

1.2.0 Sep 13, 2022
1.1.0 Sep 13, 2022
1.0.1 Sep 13, 2022
1.0.0 Sep 11, 2022

#1938 in Data structures

Download history 1801/week @ 2024-01-06 1236/week @ 2024-01-13 1258/week @ 2024-01-20 760/week @ 2024-01-27 1117/week @ 2024-02-03 1244/week @ 2024-02-10 885/week @ 2024-02-17 760/week @ 2024-02-24 929/week @ 2024-03-02 914/week @ 2024-03-09 945/week @ 2024-03-16 1431/week @ 2024-03-23 928/week @ 2024-03-30 891/week @ 2024-04-06 887/week @ 2024-04-13 558/week @ 2024-04-20

3,601 downloads per month
Used in radicle-node

MIT license

315KB
653 lines

Bloomy

A minimal implementation of a Bloom filter in Rust.

Bloom filters are a space-efficient probabilistic data structure invented by Burton Howard Bloom in the 1970s.

This crate combines ideas and code from various other Bloom filter crates.

The underlying bit vector implementation is adapted from existing code by Helge Wrede, Alexander Schultheiß and Lukas Simon.

In comparison with other crates, bloomy combines the following advantages:

  • Computationally efficient by using a double hashing technique pioneered by Adam Kirsch and Michael Mitzenmacher. You can find a copy of the paper in the docs/ folder.
  • Has only a single dependency: siphasher, from which multiple hashers are derived, and hence doesn't depend on the bitvec or bit-vec crates.
  • Supports union and intersection operations.
  • Supports counting items and similarity metrics.

Usage

Add the following to your Cargo.toml:

[dependencies]
bloomy = "1"

Check the examples/ folder for usage examples.

License

Licensed under the MIT license.

Dependencies