bloom_filter.cpp

/**
 * Simple Bloom filter: m bits, k hash seeds derived from std::hash + salt.
 */
#include <bitset>
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>

template <std::size_t M, std::size_t K>
class BloomFilter {
    std::bitset<M> bits_{};

    static std::size_t h(std::size_t seed, const std::string& x) {
        std::size_t a = std::hash<std::string>{}(x);
        std::size_t b = seed * 0x9e3779b97f4a7c15ULL + 1;
        return (a ^ b) % M;
    }

public:
    void insert(const std::string& key) {
        for (std::size_t i = 0; i < K; ++i) bits_.set(h(i, key));
    }

    bool maybeContains(const std::string& key) const {
        for (std::size_t i = 0; i < K; ++i) {
            if (!bits_.test(h(i, key))) return false;
        }
        return true;
    }
};

int main() {
    constexpr std::size_t M = 1024;
    constexpr std::size_t K = 4;
    BloomFilter<M, K> bf;
    bf.insert("alice");
    bf.insert("bob");
    std::cout << std::boolalpha;
    std::cout << "alice? " << bf.maybeContains("alice") << "\n";
    std::cout << "bob?   " << bf.maybeContains("bob") << "\n";
    std::cout << "carol? " << bf.maybeContains("carol") << " (may false positive)\n";
    return 0;
}