一、布隆过滤器的应用价值
有时候咱们须要判断一个元素是否在一个汇合中。比方，在字处理软件中，须要查看一个单词是否拼写正确（也就是要判断它是否在已知的字典里）；在警察零碎中，一个嫌疑人的名字是否呈现在嫌疑名单上；在网络爬虫里，一个网址是否曾经被拜访过，等等。
最间接的办法就是讲汇合中的元素存在计算机中，遇到一个新元素时，将它和汇合中的元素间接比拟即可。一般来讲，计算机中的汇合是用哈希表（Hash Table）来存储的。它的益处是疾速精确，毛病是消耗存储空间。
为什么说消耗存储空间呢？其根本原因是哈希表办法须要把实实在在的具备特定长度（每个Email地址对应成一个8字节的信息指纹）的元素的信息指纹存储在内存或硬盘中的哈希表中，这个存储量在理论利用中个别是相当大的。比方每存储一亿个Email地址，须要0.8G大小的数字指纹存储空间，思考到哈希表的存储空间利用率个别只有一半，所以须要1.6G的存储空间。如果存储几十亿上百亿的Email地址，那就须要百亿字节的内存存储空间。
而布隆过滤器只须要哈希表1/8到1/4的大小就能解决同样的问题，它实际上是一个很长的二进制向量和一系列的随机映射函数。
上面以WEB页面地址的存储为例来阐明布隆过滤器的工作原理。
假设存储一亿个WEB页面地址，先建设一个16亿二进制（比特），即2亿字节的向量，而后将这16亿个二进制位清零。对于每一个WEB页面地址X，用8个随机数产生器（f1,f2,...,f8）。再用一个随机数产生器G把这8个信息指纹映射到1-16亿中的8个自然数g1,g2,...g8。当初把这8个地位的二进制位都置为1。对着一亿个WEB页面地址都进行这样的解决后，一个针对WEB页面的布隆过滤器就建成了，见下图。
布隆迪过滤器的映射办法
当初，让咱们看看如何用布隆过滤器来检测一个WEB网页地址Y是否曾经被咱们收录。用雷同的8个随机数生成器（f1,f2,...,f8）对这个WEB网页地址产生8个信息指纹s1,s2,...s8，而后将这8个指纹对应到布隆过滤器的8个二进制位，别离是t1,t2,...,t8。如果Y已被收录，显然t1,t2,...,t8对应的8个二进制位肯定是1。通过这样的形式咱们可能很快地确定一个WEB页面是否已被咱们收录。
二、布隆过滤器的实现
布隆过滤器实现代码：
#encoding=UTF-8 '''Created on 2014年6月21日@author: jin'''import BitVector class MyHash():#哈希类，依据不同参数初始化后作为不同的哈希函数 def __init__(self, cap, seed): self.cap = cap self.seed = seed def hash(self, value): #计算哈希值得过程 ret = 0 for i in range(len(value)): ret += self.seed*ret + ord(value[i]) #ord()函数计算传入的url字符串中每一个字符在ASCII码表中对应的程序值 return (self.cap-1) & ret #返回哈希值，即在比特序列中的地位 class BloomFilter(): def __init__(self, BIT_SIZE=1<<31): self.BIT_SIZE = 1 << 31 #不拢过滤器的比特数, self.seeds = [5, 7, 11, 13,19, 31, 37, 61] #8个种子，用于产生hash函数 self.bitset = BitVector.BitVector(size=self.BIT_SIZE) self.hashFuncList = [] for i in range(len(self.seeds)): self.hashFuncList.append(MyHash(self.BIT_SIZE, self.seeds[i])) #对每个种子，创立一个MyHash对象，一共8个 def insert(self, value): #插入值，这里并非真正地插入并存储，而是把该值对应的8个地位的比特地位为1 for function in self.hashFuncList: locationBit = function.hash(value) #计算应该置为1的比特位 self.bitset[locationBit] = 1 def isContaions(self, value): if value == None: return False ret = True for f in self.hashFuncList: locationBit = f.hash(value) ret = ret & self.bitset[locationBit] #能够看出，对8个哈希函数，只有有一个为0，那么将返回0，即该值尚未存在 return ret def Main(): #主函数 fd = open("urls.txt") #有反复的网址 http://www.kalsey.com/tools/buttonmaker/ bloomfilter = BloomFilter() while True: url = fd.readline() if cmp(url, 'exit') == 0: print 'complete and exit now' break elif bloomfilter.isContaions(url) == False: bloomfilter.insert(url) else: print 'url :%s has exist' % url Main() url.txt外部存储有一系列网址，最初一行是‘exit’，内容如下：
http://sourceforge.net/robots.txthttp://sourceforge.net/http://sourceforge.nethttp://sourceforge.net and https://sourceforge.nethttp://sourceforge.net/sitemap.xmlhttp://sourceforge.net/allura_sitemap/sitemap.xmlhttp://sourceforge.net/directory_sitemap.xmlhttp://a.fsdn.comhttp://a.fsdn.com/con/img/sftheme/favicon.icohttp://a.fsdn.com/con/js/min/sf.head.jshttp://a.fsdn.com/con/js/sftheme/dd_belatedpng.jshttp://fonts.googleapis.comhttp://fonts.googleapis.com/csshttp://a.fsdn.com/con/css/sf.csshttp://sourceforge.net/blog/feed/http://email.playtime.uni.cc/ http://services.nexodyne.com/email/ http://gizmo967.mgs3.org/Gmail/ http://www.hkwebs.net/catalog/tools/gmail/ http://sagittarius.dip.jp/~toshi/cgi-bin/designmail/designmail.html http://www.eoool.com/http://sourceforge.netandhttps://sourceforge.nethttp://a.fsdn.com/con/js/adframe.jshttp://sourceforge.net/directory/http://kalsey.com/tools/buttonmaker/ http://www.lucazappa.com/brilliantMaker/buttonImage.php http://www.feedforall.com/public/rss-graphic-tool.htm http://www.yugatech.com/make.php http://www.hkwebs.net/catalog/tools/buttonmaker/index.phphttp://phorum.com.tw/Generator.aspx http://www.logoyes.com/lc_leftframe.htm http://cooltext.com/Default.aspxexit运行成果如下，能够看到未产生存储地址抵触：
complete and exit now往url.txt外面再减少一个原来未有的网址:
http://www.kalsey.com/tools/buttonmaker/再次运行，居然产生了抵触，如下：
url :http://www.kalsey.com/tools/buttonmaker/ has existcomplete and exit now这阐明此网址和另外一个网址对应的8个信息指纹雷同，尽管它们自身的值是不同的，这就产生了抵触。
能够看到布隆过滤器有肯定的误识别率。上面咱们对其进行剖析。
三、误识别率的问题
假设布隆过滤器有m比特，外面有n个元素，每个元素对应k个信息指纹的哈希函数，当然m个比特里有0也有1。咱们假设某个比特为0,在这个布隆过滤器里插入一个元素，他的第一个哈希函数会把过滤器中的某个比特置为1，现实状况下，任一比特位被置1的概率是1/m，它仍然为0的概率则是1-1/m。
对于过滤器中的一个特定地位，如果这个元素的k个哈希函数都没有把它设置成1，其概率是
。如果过滤器插入第二个元素，这个特定地位仍不被置1的概率是
，相似的，插入n个元素其仍为0的概率是
。反过来，一个比特在插入n个元素后，被置1的概率则是
。
当初假设这n个元素都放到布隆过滤器中了，新来的一个不在汇合中的元素，因为它的信息指纹的哈希函数都是随机的，因而，它的第一个哈希函数正好命中某个值为1的比特的概率就是上述概率。一个不再汇合中的元素被误辨认为曾经在汇合中，须要所有的哈希函数对应的比特值均为1，其概率为
咱们上面对简化的误识别率的公式进行钻研。
图2 误识别率与m/n的关系
图2的代码：
k=8r = np.linspace(1,50,1000)p = np.power(1-np.exp(-k/r),k)plt.title('misjudgment & m/n')plt.plot(r,p)plt.xlabel('m/n') plt.ylabel('misjudgment') plt.show() 图3 误识别率与k的关系
图3的代码：
r = 30;k = np.linspace(1,10,100)p = np.power(1-np.exp(-k/r),k)plt.title('misjudgment & k')plt.xlabel('k') plt.ylabel('misjudgment') plt.plot(k,p)plt.show()首先祝贺您，可能认真的浏览到这里，如果对局部了解不太明确，倡议先将文章珍藏起来，而后对不分明的知识点进行查阅，而后在进行浏览，相应你会有更深的认知。如果您喜爱这篇文章，就点个赞或者【关注我】吧！！