This repository demonstrates two Java implementations of a Bloom filter – a space-efficient probabilistic data structure used to test set membership with potential false positives.
Overview:
Utilizes Google Guava's BloomFilter class, offering a convenient and efficient way to create and manage Bloom filters.
Overview:
Implements a custom Bloom filter using MurmurHash3 – a widely-used non-cryptographic hash function.
Here's an example output illustrating that when the Bloom filter indicates an element is not present, it is undoubtedly absent. However, when the Bloom filter suggests an element is present, it is not definitive; there is a possibility that the element may or may not be present.
- Clone this repository.
- Explore the Guava and MurmurHash examples in the src directory.
- Copy and integrate the desired implementation into your project.
Bloom filters find applications in scenarios where quick and memory-efficient set membership tests with an acceptable probability of false positives are essential. Some common use cases include:
-
Caching Systems: Rapidly check if an item is in the cache before resource-intensive retrieval.
-
Network Routers: Build forwarding tables to make quick decisions about destination IP addresses.
-
Duplicate Detection: Identify likely duplicates in datasets.
-
Blockchain and Cryptocurrencies: Verify the presence of transactions in a blockchain without downloading the entire transaction history.