leveldb::Options options;
options.filter_policy = NewBloomFilterPolicy(10);
leveldb::DB* db;
leveldb::DB::Open(options, "/tmp/testdb", &db);
... use the database ...
delete db;
// 注意，关闭leveldb的时候需要手动释放过滤器所占用内存空间
delete options.filter_policy;

namespace leveldb {
class Slice;
class LEVELDB_EXPORT FilterPolicy {
public:
virtual ~FilterPolicy();
// Return the name of this policy. Note that if the filter encoding
// changes in an incompatible way, the name returned by this method
// must be changed. Otherwise, old incompatible filters may be
// passed to methods of this type.
/*返回该策略的名称。注意如果过滤器的编码变化，此方法返回的名称必须被改变。否则不兼容旧的过滤器可能被传递给这种类型的方法。
*/
virtual const char* Name() const = 0;
// keys[0,n-1] contains a list of keys (potentially with duplicates)
// that are ordered according to the user supplied comparator.
// Append a filter that summarizes keys[0,n-1] to *dst.
//
// Warning: do not change the initial contents of *dst. Instead,
// append the newly constructed filter to *dst.
/* keys[0,n-1] 包含一个键的列表（可能有重复的）。根据用户提供的比较器进行排序。将一个总结keys[0,n-1]的过滤器追加到*dst。
 警告：不要改变*dst的初始内容。 相反将新构建的过滤器追加到*dst中。
*/
virtual void CreateFilter(const Slice* keys, int n,
std::string* dst) const = 0;
// "filter" contains the data appended by a preceding call to
// CreateFilter() on this class. This method must return true if
// the key was in the list of keys passed to CreateFilter().
// This method may return true or false if the key was not on the
// list, but it should aim to return false with a high probability.
/*
 "filter "包含了前面对这个类的CreateFilter()的调用所附加的数据。如果键在传递给CreateFilter()的键列表中，该方法必须返回true。如果键不在列表中，该方法可能会返回true或false，但它应该以返回false的概率大为目标。
*/
virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
};
// 这一部分注释较多，放到后文介绍
LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
} // namespace leveldb
#endif // STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_

// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.
#include "leveldb/filter_policy.h"
#include "leveldb/Slice.h"
#include "util/hash.h"
namespace leveldb {
namespace {
// 哈希函数
static uint32_t BloomHash(const Slice& key) {
  // 注意 0xbc9f1d34
  return Hash(key.data(), key.size(), 0xbc9f1d34);
}
class BloomFilterPolicy : 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 "leveldb.BuiltinBloomFilter2"; }
void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
  // Compute bloom filter size (in both bits and bytes)
  // 计算布过滤器的大小（包括比特和字节）。
  size_t bits = n * bits_per_key_;
  // For small n, we can see a very high false positive rate. Fix it
  // by enforcing a minimum bloom filter length.
  // 对于小的n，我们可以看到一个非常高的误判率。通过强制执行最小Bloom filter长度来解决这个问题。
  // tip: 这里就是之前说的如果bit位数过小会增加误判率
  if (bits < 64) bits = 64;
  size_t bytes = (bits + 7) / 8;
  // 至少有64个bits
  bits = bytes * 8;
  const size_t init_size = dst->size();
  // 调整容器的大小，使其包含_n个_元素。
  dst->resize(init_size + bytes, 0);
  dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
  char* array = &(*dst)[init_size];
  for (int i = 0; i < n; i++) {
    // Use double-hashing to generate a sequence of hash values.
    // See analysis in [Kirsch,Mitzenmacher 2006].
    // 使用双重哈希法生成一连串的哈希值。见[Kirsch,Mitzenmacher 2006]中的分析。
    // tips: 原始论文请看参考资料 -> LNCS 4168 - Less Hashing, Same Performance: Building a Better Bloom Filter (harvard.edu)
    uint32_t h = BloomHash(keys[i]);
    const uint32_t delta = (h >> 17) | (h << 15); // // 向右旋转17位
    for (size_t j = 0; j < k_; j++) {
    const uint32_t bitpos = h % bits;
    array[bitpos / 8] |= (1 << (bitpos % 8));
    h += delta;
  }
}
}
  /*
    关键函数：
  */
  bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
  const size_t len = bloom_filter.size();
  // 只有1位的过滤器无意义
  if (len < 2) return false;
  const char* array = bloom_filter.data();
  const size_t bits = (len - 1) * 8;  
  // Use the encoded k so that we can read filters generated by
  // bloom filters created using different parameters.
  // 使用编码的k，这样我们就可以读取由 使用不同参数创建的bloom过滤器。
  const size_t k = array[len - 1];
  if (k > 30) {
    // 超过我们设定 k 个数，直接返回 true，不滤掉该 SSTable.
    // Reserved for potentially new encodings for short bloom filters.
    // Consider it a match.
    // 保留给可能出现的新编码的短Bloom过滤器。认为它是一种匹配。
    return true;
  }
  // 关键：哈希函数
  uint32_t h = BloomHash(key);
  // 右旋17位
  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_;
    size_t k_;
    };
  } // namespace
  // 新的布隆过滤器策略（请看下文注释）
  const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
    return new BloomFilterPolicy(bits_per_key);
  }
} // namespace leveldb

/*
data：bit 位数
n：n 个 key
seed：种子，实际固定为 0xbc9f1d34
*/
uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  // Similar to murmur hash
  // 类似杂音哈希
  const uint32_t m = 0xc6a4a793;
  const uint32_t r = 24;
  // limit指向了char*数组的最后一个位置的下一个位置，类似于迭代器end()
  const char* limit = data + n;
  uint32_t h = seed ^ (n * m);
  // Pick up four bytes at a time
  // 以4个字节作为一次解析  
  while (data + 4 <= limit) {
    //  每次解码前4个字节，直到最后剩下小于4个字节
    // DecodeFixed32 低级别的Get...版本，直接从字符缓冲区读取 而不进行任何边界检查，最近的clang和gcc将其优化为一条 mov / ldr 指令。
    uint32_t w = DecodeFixed32(data);
    data += 4;
    h += w;
    h *= m;
    h ^= (h >> 16);
  }
  // Pick up remaining bytes
  // 处理剩余的字节  
  switch (limit - data) {
    // 将剩下的字节转化到uint32_t里面
    case 3:
      // static_cast 表示的是良性转换，含义表示
      h += static_cast<uint8_t>(data[2]) << 16;
      // FALLTHROUGH_INTENDED宏可以用来注解开关标签之间的隐性落差。真正的定义应该由外部提供。 这个是为不支持的编译器提供的后备版本。
      /*
      #ifndef FALLTHROUGH_INTENDED
      #define FALLTHROUGH_INTENDED \
      do { \
      } while (0)
      #endif
      */
      FALLTHROUGH_INTENDED;
    case 2:
      h += static_cast<uint8_t>(data[1]) << 8;
      FALLTHROUGH_INTENDED;
    case 1:
      h += static_cast<uint8_t>(data[0]);
      h *= m;
      h ^= (h >> r);
      break;
  }
  return h;
}

leveldb::Slice s1 = "hello";
std::string str("world");
leveldb::Slice s2 = str;

std::string str = s1.ToString();
assert(str == std::string("hello"));

leveldb::Slice Slice;
if (...) {
  std::string str = ...;
  Slice = str;
}
Use(Slice);