A memory-efficient Bloom filter implementation written in pure C, focused on probabilistic data structures, predictable memory usage, and system-level programming.
BloomFilterCore implements a Bloom filter for fast probabilistic membership queries.
A Bloom filter can answer:
- Definitely not present
- Possibly present
It may produce false positives, but a correctly configured Bloom filter does not produce false negatives.
- Configurable bit-array size
- Multiple hash functions
- Fast insertion and membership queries
- Memory-efficient probabilistic representation
- Small, focused C API
- Separate source, header, and test directories
For a Bloom filter with a fixed number of hash functions:
| Operation | Expected complexity |
|---|---|
| Insert | O(k) |
| Query | O(k) |
| Memory | O(m) |
Where k is the number of hash functions and m is the size of the bit array.
BloomFilterCore/
├── includes/
├── sources/
├── tests/
├── LICENSE
└── README.md
The project is written in standard C. Build it with your preferred C compiler and include the includes directory.
Example:
cc -Iincludes sources/*.c -o bloomfilterThe exact command can be adapted to the compiler and source layout used in your environment.
The repository includes a dedicated tests/ directory. Build and run the test sources with the same compiler configuration used for the library.
This project explores the implementation details behind a classic probabilistic data structure while keeping the implementation small enough to study and reuse.
It is particularly useful for learning about:
- Hashing
- Bit manipulation
- Probabilistic algorithms
- Memory-efficient data structures
- C API design
MIT License.