布隆过滤器
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
背景介绍：
在一个集合内想要快速查找一个元素是否存在，如果是整数集合的话，可以直接采用位图，可以在O(1)的时间复杂度内判断出是否存在，但是位图的缺陷很明显，就是只可以针对整数进行操作。
如果是一个类似字符串的话，我们还可以采用哈希表，先通过Hash函数，将字符串转化成对应的一个无符号整数，然后基本上也可以实现在O(1)的时间复杂度判断是否存在，但同样的，哈希表最严重的的问题就是哈希冲突，那么这样为了缓解哈希冲突就要设定负载因子，导致哈希表的空间浪费特别大。
那么这时候就可以考虑布隆过滤器这个数据结构来解决这一类问题。
算法思想：
- 底层代用位图的结构
- 对一个字符串采用多个哈希函数，让一个字符串对应成多个无符号整型。
- 将对应的这多个数的对应比特位都置位1，用来标识该字符串存在。
综合分析：
优点：
- 布隆过滤器底层采用位图的结构，所以相比于哈希表的结构，在空间利用率上节省很大。
- 可以在O(1)时间复杂度内快速判断一个元素是否存在于一个集合内(主要针对于字符串的处理，整数的话直接采用位图就好)
缺点：
- 由于是采用哈希映射，并且多个值来同时标识一个字符串，那么就有可能存在误判的可能性，因为哈希的映射并不是一一对应的。
对于布隆过滤器来说，判断一个元素不在集合内是准确的。
如果在的话，对应位上的1可能是其他数改变的。
布隆误判率(下面的演算是别人计算结果，我最后会附上原链接和一些相关比较好的博客)
假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：
那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是：
如果我们插入了 n 个元素，那么某一位仍然为 “0” 的概率是：
因而该位为 “1”的概率是：
现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：
其实上述结果是在假定由每个 Hash 计算出需要设置的位（bit） 的位置是相互独立为前提计算出来的，不难看出，随着 m （位数组大小）的增加，假正例（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升，对于给定的m，n，如何选择Hash函数个数 k 由以下公式确定：
此时False Positives的概率为：
而对于给定的False Positives概率 p，如何选择最优的位数组大小 m 呢，
上式表明，位数组的大小最好与插入元素的个数成线性关系，对于给定的 m，n，k，假正例概率最大为：
下图是布隆过滤器假正例概率 p 与位数组大小 m 和集合中插入元素个数 n 的关系图，假定 Hash 函数个数选取最优数目：
实现代码：https://github.com/treasureb/Datastruct/tree/master/Bloom%20Filter
字符串算法(Hash函数)：http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
布隆过滤器：http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html