HBase源码分析5—BloomFilter

源码分析的5和6两篇合起来准备一起探讨HBase的底层存储格式，BloomFilter Block也是HFile的一部分。但是BloomFilter这个东西思想上虽然很简单，但是原理上并不简单，所以把BloomFilter这部分单独拎出来讲一下。

BloomFilter介绍

是什么

BloomFilter是一种基于概率的存在检测算法。我们把BloomFilter看做是一个有m个bit位的数组 S[1..m] ，另外我们还拥有 k 个相互独立的哈希函数 H[1..k] 。当向BloomFilter中添加元素 x 时，先计算哈希结果 R=H(x) ，然后将R中的每个结果对应的 S[R[i]] 的位置1。当查询时，同样的计算哈希结果 R=H(x) ，然后查询