Bloom Filter

Membership - Bloom Filter

Refs:

• Bloom, B.H. (1970) “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM, Vol. 13 (7), pp. 422–426.

Simple usage:

#include <membership/bloom_filter.h>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> urls{
        "https://google.com",
        "https://instagram.com",
        "https://youtube.com",
        "https://facebook.com",
        "https://twitter.com"};
    // Define bloom filter with 4 hash functions and 128 memory bits
    bloom_filter<4, 128> url_bloom_filter;
    std::for_each(urls.begin(), urls.end(), [&url_bloom_filter](auto& item) {
        // Insert items into bloom filter
        url_bloom_filter.insert(item);
    });

    // Check that bloom filter contains an item or not
    if (url_bloom_filter.contains("https://gmail.com")) {
        std::cout << "FOUND!!!!!" << std::endl;
    } else {
        std::cout << "NOT FOUND" << std::endl;
    }
    if (url_bloom_filter.contains("https://facebook.com")) {
        std::cout << "FOUND" << std::endl;
    } else {
        std::cout << "NOT FOUND!!!!!" << std::endl;
    }
}