fork download
copy 
  1. #include <cmath>
  2. #include <cstdint>
  3. #include <iostream>
  4. #include <stdexcept>
  5. #include <string>
  6. #include <utility>
  7. #include <vector>
  8.  
  9. namespace util {
  10.  
  11. class BloomFilter {
  12. public:
  13.     BloomFilter(std::uint64_t expected_n, double fpr = 0.01) {
  14.         if (expected_n == 0 || !(fpr > 0.0 && fpr < 1.0)) {
  15.             throw std::invalid_argument("invalid BloomFilter params");
  16.         }
  17.  
  18.         const double ln2 = std::log(2.0);
  19.         const std::uint64_t bits = static_cast<std::uint64_t>(
  20.             -static_cast<double>(expected_n) * std::log(fpr) / (ln2 * ln2) + 0.5);
  21.  
  22.         m_ = next_pow2(bits < 64 ? 64 : bits);
  23.         mask_ = m_ - 1;
  24.  
  25.         std::uint64_t hashes = static_cast<std::uint64_t>(
  26.             static_cast<double>(m_) / expected_n * ln2 + 0.5);
  27.         if (hashes < 1) hashes = 1;
  28.         if (hashes > 16) hashes = 16;
  29.         k_ = hashes;
  30.  
  31.         words_.assign(m_ >> 6, 0);
  32.     }
  33.  
  34.     void add(std::uint64_t key) { insert(hash64(key)); }
  35.     void add(const std::string& key) { insert(hash64(key)); }
  36.  
  37.     bool may_contain(std::uint64_t key) const { return probe(hash64(key)); }
  38.     bool may_contain(const std::string& key) const { return probe(hash64(key)); }
  39.  
  40.     std::uint64_t bit_count() const { return m_; }
  41.     std::uint64_t hash_count() const { return k_; }
  42.     std::size_t memory_bytes() const { return words_.size() * 8; }
  43.  
  44. private:
  45.     std::uint64_t m_;
  46.     std::uint64_t mask_;
  47.     std::uint64_t k_;
  48.     std::vector<std::uint64_t> words_;
  49.  
  50.     static std::uint64_t next_pow2(std::uint64_t x) {
  51.         --x;
  52.         x |= x >> 1;
  53.         x |= x >> 2;
  54.         x |= x >> 4;
  55.         x |= x >> 8;
  56.         x |= x >> 16;
  57.         x |= x >> 32;
  58.         return x + 1;
  59.     }
  60.  
  61.     void set_bit(std::uint64_t i) { words_[i >> 6] |= 1ULL << (i & 63); }
  62.     bool test_bit(std::uint64_t i) const {
  63.         return (words_[i >> 6] >> (i & 63)) & 1ULL;
  64.     }
  65.  
  66.     std::uint64_t slot(std::uint64_t h1, std::uint64_t h2, std::uint64_t i) const {
  67.         return (h1 + i * (h2 | 1ULL)) & mask_;
  68.     }
  69.  
  70.     void insert(std::pair<std::uint64_t, std::uint64_t> h) {
  71.         for (std::uint64_t i = 0; i < k_; ++i) {
  72.             set_bit(slot(h.first, h.second, i));
  73.         }
  74.     }
  75.  
  76.     bool probe(std::pair<std::uint64_t, std::uint64_t> h) const {
  77.         for (std::uint64_t i = 0; i < k_; ++i) {
  78.             if (!test_bit(slot(h.first, h.second, i))) return false;
  79.         }
  80.         return true;
  81.     }
  82.  
  83.     static std::uint64_t mix64(std::uint64_t x) {
  84.         x += 0x9e3779b97f4a7c15ULL;
  85.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
  86.         x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
  87.         return x ^ (x >> 31);
  88.     }
  89.  
  90.     static std::pair<std::uint64_t, std::uint64_t> hash64(std::uint64_t key) {
  91.         return std::make_pair(mix64(key), mix64(key ^ 0x9e3779b97f4a7c15ULL));
  92.     }
  93.  
  94.     static std::pair<std::uint64_t, std::uint64_t> hash64(const std::string& s) {
  95.         std::uint64_t h1 = 0xcbf29ce484222325ULL;
  96.         std::uint64_t h2 = 0x9e3779b97f4a7c15ULL;
  97.         for (std::size_t i = 0; i < s.size(); ++i) {
  98.             unsigned char c = static_cast<unsigned char>(s[i]);
  99.             h1 = mix64(h1 ^ c);
  100.             h2 = mix64(h2 ^ c);
  101.         }
  102.         return std::make_pair(mix64(h1 ^ s.size()), mix64(h2 ^ s.size()));
  103.     }
  104. };
  105.  
  106. }  // namespace util
  107.  
  108. int main() {
  109.     const std::uint64_t N = 100000;
  110.     util::BloomFilter bf(N, 0.01);
  111.  
  112.     std::cout << "m=" << bf.bit_count()
  113.               << " k=" << bf.hash_count()
  114.               << " bytes=" << bf.memory_bytes() << "\n";
  115.  
  116.     for (std::uint64_t i = 0; i < N; ++i) bf.add(i);
  117.  
  118.     std::uint64_t fp = 0;
  119.     for (std::uint64_t i = N; i < 2 * N; ++i) {
  120.         if (bf.may_contain(i)) ++fp;
  121.     }
  122.  
  123.     std::cout << "has 42=" << bf.may_contain(static_cast<std::uint64_t>(42)) << "\n";
  124.     std::cout << "has 999999=" << bf.may_contain(static_cast<std::uint64_t>(999999)) << "\n";
  125.     std::cout << "false_positives=" << fp << "/" << N << "\n";
  126. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
m=1048576 k=7 bytes=131072
has 42=1
has 999999=0
false_positives=650/100000
https://ideone.com/gGII0v
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!