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) ，然后查询 S 中对应的位是不是已经置1了，如果全为1，则有可能存在，否则则不存在。
参数分析
首先假定几个参数，为了后面分析代码方便，我们这里先告诉大家他们在HBase源码中叫什么名字。
| 参数名 | HBase源码中的变量名 | 含义 |
|---|---|---|
| n | maxKeys | 插入到BloomFilter的元素个数 |
| m | bitSize | BloomFilter的长度 |
| k | hashCount (nbHash) | 哈希函数个数 |
| e | err | 误正率（False Positive Rate） |
首先很显然，BloomFilter对于判断不存在是完全准确的，但是对于判断存在可能会出错，这是由于插入元素不断增加，哈希碰撞的概率会变大。首先我们估计一下误正率（False Positive Rate） f 。我们假设哈希函数是完全随机的，那么BloomFilter中的某一位在插入 n 个元素后仍然是0的概率是
1/m 是某个哈希函数选中这一位的概率，有 k 个函数和 n 个元素。后面这个是求极限用洛必达法则导出来的（数学捉急了）……
那么，误正率为：
求上式的最小值，可以得到m、n确定下的合适的k的取值
在这个课件中放了一些不同的 m 、 n 、 k 计算出的误正率的对比，也可以看出我们的结论是对的。
另外当m和误正率f固定的情况下，最优的m可以得到
这两个结论是贯穿代码的两个结论，大部分函数都可以由这俩方程变换一下得到。
关于本部分内容可以详细参考以下材料
Network Applications of Bloom Filters: A Survey
CS 6550: Bloom Filters and Hashing
BloomFilter折叠
这部分没看到哪里有讲解，但是在代码中发现了有类似 compactBloom这种函数，只能从论文中找找相关分析。
V1的BloomFilter为什么叫 ByteBloomFilter ？是因为它使用了一个 ByteBuffer 做为BloomFilter的存储数组，每个byte可以存8个标志位（因为1 byte=8 bit）。我们从前一部分知道，m的最佳大小由 f 和 n 影响，所以