布隆过滤器

✍ dations ◷ 2025-07-08 17:11:53 #函数,散列

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 O ( n ) , O ( log n ) , O ( 1 ) {\displaystyle O(n),O(\log n),O(1)}

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数( O ( k ) {\displaystyle O(k)} )。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

k {\displaystyle k} m {\displaystyle m} 相同,使用同一组散列函数的两个布隆过滤器的交并运算可以使用位操作进行。

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

相关

  • 艸部,为汉字索引中的部首之一,康熙字典214个部首中的第一百四十个(六划的则为第二十三个)。在正体中文中,艸部归于六划部首,而在简体中文中,将汉字部首规范的《汉字部首表》中,将“
  • 视黄酸维A酸(Tretinoin、ATRA),又称全反式维甲酸及视黄酸,分子式:C20H28O2,分子量300.44,CAS号302-79-4,熔点180℃。医学导航: 皮肤附件解剖/生理/发育病理/先天/肿瘤, 症状/齐名手术,
  • 胃食管反流疾病胃食道逆流(英文:Gastroesophageal reflux disease、heartburn reflux,缩写:GERD),或称作胃食管反流病、胃酸倒流等,是指胃酸(有时加上十二指肠液)长期不正常地向上反流进入食道甚至
  • 瓜达卢佩·伊达戈尔条约《瓜达卢佩-伊达尔戈条约》(英语:Treaty of Guadalupe Hidalgo,西班牙语:Tratado de Guadalupe Hidalgo)是美国与墨西哥签订的结束美墨战争的和平条约,美军攻陷墨西哥首都墨西哥城
  • 节食节食指限制吃的食物分量,通常是以减肥瘦身作为目的。根据美国卫生研究局(National Institutes of Health, NIH)、美国营养学会(American Society for Nutrition, ASN) 的建议
  • 007 (消歧义)007可以指:
  • 苕酥苕酥是大宜昌、鄂西、重庆一带的小吃。由四川小吃苕酥糖演变而来。“苕”在四川、湖北的方言中是指红薯的意思,苕酥是以红薯为主料,加入部分糯米,制成微小颗粒,由鸡蛋浆粘合在一
  • 良六世教宗良六世(拉丁语:Leo PP. VI;914年-928年)是一位罗马人,928年5月或6月接替教宗若望十世(914年3月或4月-928年5月或6月在位)岀任教宗。他于928年5月或6月-928年12月或929年1月在位教
  • 加尔卡尔内自治市加尔卡尔内自治市(拉脱维亚语:Garkalnes novads),是拉脱维亚的一个自治市,设立于2009年。位于该国中部,人口6722人,面积150.5平方公里,人口密度约45人/km2。
  • 侯琎侯琎(1398年-1450年),字廷玉。山西泽州人。明朝政治人物。永乐二十一年(1423年)癸卯科山西乡试第一名举人。宣德二年(1427年)进士,授行人司行人。当时云南土官乌撒、乌蒙相争,明宣宗命