基本理论
详细理论及证明请看这篇博文--Bloom Filter概念和原理。强烈建议花半个小时仔细去阅读一下这篇文章，本文后续的介绍将以上述文章作为基础。
这里将几个结论先列出来(证明请参考上面的超链接)：
结论一： 在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）
结论二： Bloom Filter通过极少的错误换取了存储空间的极大节省
结论三： k = ln2· (m/n)时取得最优的哈希函数的个数
结论四： 在错误率不大于є的情况下，m至少要等于n log2(1/є)才能表示任意n个元素的集合。
结论五： 在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍。
源码实现
成员变量
private:
size_t bits_per_key_;
size_t k_;
bits_per_key_表示m／n，k_表示选取哈希函数的个数，当然在leveldb中并不是真的使用了k_种哈希函数，而是采用的double hashing来模拟多个hash函数。模拟原理如下：
Gi(x)=H1(x)+iH2(x)
H2(x)=(H1(x)>>17) | (H1(x)<<15)
成员函数
构造函数
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;
}
看看结论三，应该就知道为何要用bits_per_key_*0.69了吧😄。
CreateFilter(const Slice* keys, int n, std::string* dst)
// 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.
if (bits < 64) bits = 64;
size_t bytes = (bits + 7) / 8;
bits = bytes * 8;
const size_t init_size = dst->size();
dst->resize(init_size + bytes, 0);
首先根据n的值计算出m(bytes)，然后计算并分配所需空间。
dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
在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].
uint32_t h = BloomHash(keys[i]);
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;
array[bitpos/8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
对于每个key采用double hash的方式生成k_个bitpos，然后在array的相应位置设置1。
KeyMayMatch(const Slice& key, const Slice& bloom_filter)
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;
// Use the encoded k so that we can read filters generated by
// bloom filters created using different parameters.
const size_t k = array[len-1];
if (k > 30) {
// Reserved for potentially new encodings for short bloom filters.
// Consider it a match.
return true;
}
准备工作，以及一些基本的判断
uint32_t h = BloomHash(key);
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;
计算key的hash值，重复计算阶段的步骤，循环计算k_个hash值，只要有一个结果对应的bit位为0，就认为不匹配，否则认为匹配
