Please note, this project is deprecated and no longer being maintained, please use an up-to-date version at jonalmeida/bloom-filter.
Bloom filter library implemented in Rust -- includes MurmurHash3 implementation, and simple bit vector library
Still early implementation. Currently includes: working bloom filter
library, working 32-bit murmurhash3 implementation, as well as a
working bit vector library that can set
, unset
, flip
bits.
Libraries were built and tested using the master branch of Rust pulled on Feb 18, 2014. Libraries can be built using the included Makefile.
The bloom crate exports one module, bloom_filter. The bloom_filter
module exports a single object, BloomFilter
with three public methods,
new
, insert
, and maybe_present
. The new
method is static and
can be used to create a new BloomFilter
with specified expected number
of insertions, and desired false positive rate. Example:
// Create new BloomFilter with 1000 expected elements, and false positive rate of 3%
let mut bf = BloomFilter::new(1000, 0.03);
insert
will insert a string value into the bloom filter, and
maybe_present
will return true if queried value might be present, or
false if it is definitely not present.
The murmur library exports two public functions, murmur3_32_seeded
and murmur3_32
. The murmur3_32
function is simply a convenience
function that calls murmur3_32_seeded
with a seed value of 0. Both
functions take a &str
to be hashed and return a u32
value.
The bit_vec library contains a struct, Bit_vec
that stores an vector
of u8
bytes, and the desired size of the bit vector as an
uint
. Bounds checking is provided by checking against the size
value.
A Bit_vec
can be created with the constructor function new
with
a single uint
size parameter.
let my_bv: Bit_vec = Bit_vec::new(24);
The struct has four public methods available, set
, unset
, flip
,
and is_set
. set
will set a bit at the specified index position to
1, unset
will set a bit at the specified index position to 0. flip
will invert a bit at the specified index position, e.g. a 0 becomes a
1 and a 1 becomes a 0. is_set
will return true if the bit at the
specified index position is a 1, and false otherwise.
extern mod bit_vec;
use bit_vec::bit_vec::Bit_vec;
fn main() {
let mut bv = Bit_vec::new(8);
bv.set(5);
test_for_5(&bv);
bv.unset(5);
test_for_5(&bv);
}
fn test_for_5(bv: &Bit_vec) {
if bv.is_set(5) == true { println!("Hooray!"); } else { println!("Boo!"); }
}
Should result in the following output:
Hooray!
Boo!