缓存(Cache)是用来解决当下软件性能问题时需要考虑的一个很重要的手段。 你的程序可能有密集的CPU操作，而你却不想一遍又一遍的折磨CPU。 相反， 你会将结果抽取出来并缓存到内存中。 有时候系统的瓶颈也可能是IO操作， 比如你不想重复执行数据库的查询，而是把查询结果缓存起来， 只是在数据库的数据改变的时候才去更新缓存。
类似地还有一些其它需要cache的情况如处理收到的request时我们需要执行一个快速的查询。例如， 你需要判断一个URL是否指向了一个恶意网站。 可能有非常多的（恶意网站的）URL， 如果我们将所有的恶意网址都缓存起来， 需要很大的空间。 又比如我们需要识别用户输入的字符串中是否包含美国的一个地方。 比如用户输入华盛顿的博物馆， 这个字符串中华盛顿是美国的一个地名。 我们要把美国所有的地名缓存起来以供查找？ 缓存会变得多大？没有数据库支持的这样做是否有效？
这就是我们淘汰map数据结构而去宣召一个更先进数据结构-boomfilter。 你可以把blommfilter看作类似java collection中的类。 可以把数据项放到它里面，可以检查某个数据项是否已经存在。 如果Bloomfilter说数据项不存在， 那数据项的确不存在， 不必怀疑。 但是如果它说数据项存在， 可能是误报， 有可能数据项真的不存在。 如果我们考虑周全， 就能减少误报的可能。
算法解释
Bloomfilter 设计为一个m bit的数组。 初始所有的bit为0.
增加项:
为了增加数据项， 需要提供k个hash函数。每个hash将会产生一个数字，对应bit数组的一个位置 （0 ~ m）。 我们会将此位置设置为 1. 例如hash1函数的计算数据项的值为x, hash2函数为y, hash3函数为z。
将bit数组中相应的位置设置为1:
|
|
查找项:
查找时的逻辑类似增加数据项， 通过hash1, hash2, hash3 ...计算出三个位置x, y, z。 我们需要检查bit数组中x, y, z的位置的值是否为1. 如果不全为1， 数据项肯定没有被增加过. 但是如果全为1, 也可能是假阳性的(数据项也可能从未被增加过)
调优
从上面的解释可以清晰的看出， 为了设计一个好的bloomfilter我们需要遵循一下的原则：
- 良好的hash函数确保尽可能快的产生一定范围的哈希值
- 数组的大小m至关重要. 如果太小， 可能很快所有的位置都被设置为1， 误报率会非常的高。
- hash functions的数量也非常重要。 所有的值要尽可能的均匀分布。
如果我们能预估我们会在bloomfilter存多少个数据项,我们就能计算出最优的k和m值。 跳过数学理论的细节， 下面的公式足够我们写出一个好的bloomfilter。
计算m的公式:
$m = - \frac{n\log^p}{(\log2)^2}$
这里的 p为 误报率。
计算k的公式:
$k = \frac{m}{n} \log2$
k是hash函数的数量。 m是bit数， n是数据项的数量。
在线计算: 点击这里
哈希
Hash函数也是影响bloomfilter性能的因素. 我们需要选择有效且不费时的hash函数。在论文 “Less Hashing, Same Performance: Building a Better Bloom Filter” 讨论了怎么使用两个hash函数产生k个哈希函数。 首先需要计算两个哈希函数h1(x) 和 h2(x)， 然后我们使用这两个hash函数模拟k个哈希函数。
$g_i(x) = h_1(x) + ih_2(x)$
i的值域为 {1..k}.
Google guava library 在它的bloomfilter实现中使用了这个技巧。 Hash的代码逻辑如下 :
|
|
应用
很清楚怎么使用数学公式计算合适的值来创建bloomfilter来处理问题。 我们需要很好的理解其意义。就像我们使用bloomfilter来处理美国所有的城市名一样。 城市的数学我们早已获悉，所以我们可以确定n的值的大小。 依照业务选择你期望的p值(误报率). 这样我们就可以使用有效的内存创建一个完美的cache， 查询时间也很短。
实现
Google guava 库实现了Bloomfilter. 构造函数需要传入期望的数据项和误报率.
|
|
