Rust Bloom Filter Implementation

This project provides a Rust implementation of a Bloom filter, inspired by LevelDB's Bloom filter. A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set.

Features

Custom bits per key configuration
Optimized hash function
Efficient filter creation and querying

Usage

Creating a Bloom Filter

To create a new Bloom filter:

let bits_per_key = 10;
let bloom_filter = BloomFilter::new(bits_per_key);

The bits_per_key parameter determines the size and accuracy of the filter. A higher value will result in a larger filter with a lower false positive rate.

Creating a Filter from Keys

To create a filter from a set of keys:

let keys: Vec<Vec<u8> > = vec![
    b"apple".to_vec(),
    b"banana".to_vec(),
    b"cherry".to_vec(),
];
let filter = bloom_filter.create_filter( & keys);

Checking for Key Presence

To check if a key may be present in the filter:

let key = b"apple";
let may_exist = bloom_filter.key_may_match(key, & filter);

Note that Bloom filters may return false positives but never false negatives. A true result means the key may be present, while a false result means the key is definitely not present.

Implementation Details

The number of hash functions (k) is calculated based on the bits_per_key parameter, optimized for best performance.
The filter uses a single hash function with a rotating delta to simulate multiple hash functions, improving performance.
The filter size is adjusted to be a multiple of 8 bits for efficient storage.

Performance Considerations

The Bloom filter is designed to be space-efficient while maintaining a low false positive rate.
The implementation uses bitwise operations for efficient querying.
The filter size grows linearly with the number of keys, making it suitable for large datasets.

Dependencies

This implementation relies on a custom hash function bloom_hash defined in the hash module.

License

MIT

Contributing

[Include information about how to contribute to the project]

monadbobo/bloomfilter-rs