布隆过滤器(BloomFilter)

class BloomFilterPolicy final : public FilterPolicy {
 public:
  explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;
  }

  const char* Name() const override { return "BloomFilter2"; }

  /***
   * BloomFilter 生成 放置到 ${dst} 中
   * @param keys
   * @param n
   * @param dst
   */
  void CreateFilter(const std::string* keys, int n,
                    std::string* dst) override {
    
    /***
     * 计算需要多少字节来存储这些 key 的bloom filter 标识
     */
    size_t bits = n * bits_per_key_;
    if (bits < 64) bits = 64;
    size_t bytes = (bits + 7) / 8;
    bits = bytes * 8;  // 向上对齐

    /***
     * 初始化 BloomFilter 位, 置空
     */
    const size_t init_size = dst->size();   // 获取原始大小
    dst->resize(init_size + bytes, 0);      // 扩大新的位大小， 并且填空新的元素为 0[初始化 bloom 过滤器]
    dst->push_back(static_cast<char>(k_));  // 将最后一位存放这个过滤器用了多少个 hash 函数

    char* array = &(*dst)[init_size];       // 获取到 bloom 过滤器的首部位置
    
    /***
     * 设置每个key的BloomFilter位
     */
    for (int i = 0; i < n; i++) {
    
      // 获取 key 的 hash 值
      uint32_t h = hash_func_.MurMurHash2(keys[i].c_str(), keys[i].size());

      // 高低位转换 : 17 + 15 = 32, 用与 hash 偏移因子
      const uint32_t delta = (h >> 17) | (h << 15);  

      for (size_t j = 0; j < k_; j++) {            // k 个hash 函数
        // 取bits有效值，并设置对应位为1

        const uint32_t bitpos = h % bits;          
        array[bitpos / 8] |= (1 << (bitpos % 8));  
        
        h += delta;  // hash 偏移
      }
    }
  }

  /**
   * Bloom 过滤器校验
   * @param key 用户校验的key
   * @param bloom_filter 存放的bloom 过滤器值
   * @return
   */
  bool KeyMayMatch(const std::string& key,
                   const std::string& bloom_filter) override {

    /***
     * 获取 bloom 过滤器的长度
     */
    const size_t len = bloom_filter.size();
    if (len < 2) return false;

    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8;

    // 获得有多少个 hash 函数，最多30个
    const size_t k = array[len - 1];
    if (k > 30) {
      return true;
    }
    
    uint32_t h = hash_func_.MurMurHash2(key.c_str(), key.size());
    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
    for (size_t j = 0; j < k; j++) {
      const uint32_t bitpos = h % bits;
      if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
      h += delta;
    }
    return true;
  }

 private:
  size_t bits_per_key_;   // 预估每个key大概需要多少位可以存储
  size_t k_;              // k 个 hash 函数, 默认 30 个
  HashFunc hash_func_;    // hash 函数
};

class BloomTest final {
 public:
  BloomTest(uint32_t bit_per_key = 10)
      : policy_(std::make_unique<BloomFilterPolicy>(bit_per_key)) {}

  ~BloomTest() {}

  void Reset() {
    keys_.clear();
    filter_.clear();
  }
  void SetData(std::vector<std::string>&& keys) { keys_ = std::move(keys); }
  void SetData(const std::vector<std::string>& keys) { keys_ = (keys); }

  void Add(const std::string& s) { keys_.emplace_back(s); }

  void Build() {
    filter_.clear();
    policy_->CreateFilter(&keys_[0], static_cast<int>(keys_.size()), &filter_);
    keys_.clear();
  }

  size_t FilterSize() const { return filter_.size(); }
  bool Matches(const std::string& s) {
    if (!keys_.empty()) {
      Build();
    }
    return policy_->KeyMayMatch(s, filter_);
  }

  double FalsePositiveRate(const std::vector<std::string>& data) {
    double result = 0;
    for (const auto& item : data) {
      if (Matches(item)) {
        result++;
      }
    }
    return result / 10000.0;
  }
  double FalsePositiveRate(const std::string& data) {
    double result = 0;
    {
      if (Matches(data)) {
        result++;
      }
    }
    return result / 10000.0;
  }

 private:
  std::unique_ptr<FilterPolicy> policy_;
  std::string filter_;
  std::vector<std::string> keys_;
};