布隆过滤器是Burton Bloom 在1970年提出的，用于解决打标记的问题。对于每个字符串，利用k种不同的字符串hash算法，生成k个哈希值，然后把这k个值打入大小为m个bit的槽中，用以标记这个字符串已经出现。举个简单的例子，对于字符串”blog.vvbin.com”，利用k=4种不同的字符串哈希算法，产生4个哈希值：4216，3054，1017，2222。然后采用求模的方式打入m=31的bit槽中，结果如下图：
在查询时，只要查看对应的k个bit位是否为1，就可以知道当前字符串是否已经存在。
布隆过滤器通常只需传统哈希表1/8的存储空间，就可达到很好的哈希效果。假设我们有10万个字符串，鉴于hash表的存储效率大约是50%，这样我们需要20万个槽，每个槽是一个32位（8字节）的DWORD，这样我们需要160万字节空间来存储。而如果采用布隆过滤器，对于10万个字符串，我们采用160万个槽来存储，每个槽是一个bit，那么我们总共只需160万bit，也就是20万字节，即可达到比较理想的哈希效果。
当然，布隆过滤器不是万能的，它会存在误判问题。对于一个已经存在的字符串，对应的k位肯定置为1，布隆过滤器可以识别出来，但是对于一个不存在的字符串，有一定的概率计算出来的k位也都是1，但其实它并没有存在。这就是布隆过滤器的误判问题，并且这种误判不像哈希表那样可以通过开地址等方法解决。
那么这种误判的概率有多大呢？这是可以通过数学公式计算得出的，完整的计算就不在这里列出。但给出几种常见状态下的误判概率，让大家对此有一个大概的认识。假设我们采用m个bit长度的布隆过滤器，存放n个字符串，每个字符串采用k种不同哈希算法，差生k个标记。这样的情况下误判概率如下表：
（完整的表以及数学计算参见《数学之美》 第23章）
套回上面的例子，m为160万（160万个槽），n为10万（10万个字符串），m/n == 16，如果我们采用8个不同的哈希算法，误判的概率为0.000574 。大约是万分之六。只用八分之一的存储空间达到这个效果，也是十分不错的。当然，布隆过滤器对每个样例要进行k次哈希计算，速度上肯定有所损失，所以这个算法也可以看作是用时间换空间。
当然，准确率要求100%的应用，无论误判率多低，多省空间，布隆过滤器都是不适用的。但对于另外一些情况却可以起到很好的效果。例如网站上的资源非常多，其中有10万个是缓存在高速服务器上的，对于资源的请求，要判断是否在缓存服务器上，就可利用布隆过滤器。因为就算出现了误判，在缓存服务器上找不到，再到其他服务器上找也是可以的。再把这些误判的用例加入到一张白名单中，下次就可避免误判了，并且往后训练次数越多，准确率越高。
嗯，对于布隆过滤器，暂时只挖到这里了。
关电脑赶车回家，放假神马的最开心啦，哈哈。