第30卷第9期2013年9月计算机应用与软件Vo130No•9ComputrApp1catonsandSofwarSep・20131er对数据集合采用一个位串表示并能有效支持集合元索的哈希査找操作，以允许一定的谋判率为代价,获御很鬲的查找效率和很小的空间消耗。由于哈希查找的常数时间和存储空间开销较少，使它具冇很好的实用价值。自从它在1970年由BuronB1om提出后［门，就在数据库领域广泛使用，近十年来在网络中也逐渐受到了国内外学者的广泛关注，成为11前很热门的方法。2004年AndriBrder］总结了B1omf1er在网络中的应用，但当时更着重于在P2P/盖网络中的应用，包括分布式文件存储和路由查找等，在网络流量测量及网络安全方面的应用还不是很多。此外，肖明忠［3］和严华云［4］也分别做了综述性的研究。本文则重新归纳了Blomf1cr及其改进结构，着重于综述分析近年來出现在计算机网络领域的新应用，以期对以后的Blomf(Sh(S的元素被置成1。某位可能被多次置1•但仅第一次设置真正起作用，这将导致某个元索不属于集合而被指称属于集合的问题，其概率谋差称，濮判率”。在表示算法中，每次赋值使得某位为1的概率为1/,为0的概率为1一1/。插入n个元素后，某位仍为0的概率是：则误判率为:给定m,n的情况下，求f的般小值，即是求g=kn(1-e-kn/m)的最小值。=1(1-e-ko/m)+m1—e-kn/mk=(m/)12时，上式为0,即g和f均取故小值。再将式(1)代入g,有：工作有所裨益。(4)1标准BlomFitfon同样，g关于p求导当p=1/时，g有最小值，从而「有BlomFitf及其在网络中的应用综述刘元珍(盐城工学院优集学院江苏盐城224051)摘耍Blomfier是用来表示集合的数据结构，并以较小的谋判率为代价，实现较少的存储空间开销和常数的查找时间。对B1omf1er及其改进结构作了分析研究，并着重介绍最近儿年在网络中包括在流量测量和网络安全方面出现的新应用。在一定谋判率存在的情况下，Blomf1er为大规模数据集合元素表示、成员査询及多重集和动态集的元素频率査询等提供了解决方案。关键词Blomf1er网络应用哈希误判率T卩393文献标识码ADOI10・3969/.is.100086x・2013・09.060SURVEYONBLOOMFITERANDISAPPLIATINSINETWORKSLiYuanzen(UGSColeeYanceglsiutofTehnolgyYanceg224051,激ngs,Chia)AbsractBlomfieritedatsrctrfrrprsntngastandisa1ercosofmijdgementrt.iachivessorgesacesvigandisantsarhigtme.1tipaperwefrtsudyandanalsteBlomflerandisiprved$rctr,andtenemphatcalyitoduceisnewapp1catonsiavaretofnetorasecticldigtetafimeasrmentandnetorscurtircentvear・Icondiinofhavigceraimijdgementrt.Blomf1erprviegoodsltonsfrlreca1datstie1mentrprsnttonandmcmbcrhiqucr^andfrmu1istordynamistielmentfequcncyquercta1KeywordsBlomf1erNetorapplcatonsHasigMijdgementrt最小值，即：Blomf1er］使用长为m的位串V表达n个元素的集合Sf_(、J=1m/nin?=0.6185"(5)e11t「G一［—1丿2=(久・£・・・立乃hl/H询禾URG利I存储r初始彳P位"IMl彳寸-个元索为0,设有k个具有均匀分布特性的哈希函数hi,且其值牧稲日期：2012-08-07,刘元珍，讲师，主妍领域：网络淤槪测裁域为{1.........m},对于毎个元素sS■位卑中对应于h(s■h和网络安全。2013计算机应用与软件oitmmD—1-=emtf=(1—p0)k=1—1—1eo[2oitu(1—e=ek1n(1-e)(2)1kne-kn?m0itnn1(P)1(1-P)o1eoo2oit[1t(h2nGi)2B1omFit门旳改进结构调整。假设第j项的CBFV和0FV值分别为Cj和0Fj,则计数器的值Vj=2xxOFj+Cj。DCF中最大的计数器决定了整个结构所占的空间，在计数杂的索引结Blomf1e『提出后根据不同的需要谨行的改进很多，我器的值普遍不大的情况下，DCF不用维护复们认为实质性的改进结构冇支持集合元素删除的CountngBlomfler］,在CountngBlomfler基础上改进的支持动态计数器[6]构，占用空间比SBF要少。但如果将计数器的值逐渐増大,间占用上的优势则会比较明显。2.3CompresedBlomFiSBF在空DynamiCounler]及针对压缩环境的ComprsedBlomtr］o另外，文献［4］中捉到了支持动态数据集的矩阵式Blomfler如SpltBlomfler及DynamiBlomfief但矩阵式Blomf1er并没冇改变Blomfler本身的结构，只是由向就构成了向童矩阵，支持某些比如元...