J B*_*J B 16 algorithm hash filter
你更喜欢哪个？为什么？
它们都可以用来完成类似的任务,但我很好奇,看看人们在实际应用中使用了什么,以及他们这样做的推理.
Mar*_*son 18
Bloom过滤器和Cuckoo过滤器在类似的情况下使用,但在下面有很多差异,通常决定哪个是更好的选择.
Bloom过滤器在数据库引擎内部使用,特别是Apache Cassandra.正如其他海报所说,其原因是为了降低慢速操作的成本.基本上,任何"这可能或肯定不存在"的高成本操作都可以使用Bloom过滤器来减少完成的检查次数.
今天的SaaS模型的另一个常见示例是具有每次呼叫成本的远程REST服务.任何具有二进制答案的API调用(例如"此地址无效")都可以使用布隆过滤器来消除超过90%的重复查询!请注意,由于Bloom和Cuckoo过滤器具有误报,因此对于反向操作无效"此地址有效"
重要的是要记住,Bloom和Cuckoo过滤器没有假阴性.这使得这些过滤器对于"这绝对不是或可能是垃圾邮件"等检查非常有用,但对于误报不可接受的操作(例如检查用户权限)则无效.在这方面,它们在概念上可以被认为是高速缓存的反面.Bloom/Cuckoo过滤器和缓存主要用于通过布尔答案降低昂贵操作的成本,除了缓存没有误报并且Bloom/Cuckoo没有误报.
Cuckoo/Bloom之间的显着差异包括:
组合.只要使用相同的参数创建布隆过滤器,就可以有效地合并布隆过滤器.快速且带宽很小.这就是为什么你看到它们在大规模分布式系统中经常使用,交换Bloom过滤器的速度很快.咕咕过滤器不易组合,在这些情况下不太有用.
误报率.咕咕过滤器更节省空间.两种结构的许多用例都集中在低级网络上.在弱硬件上,对于相同的误报率,Cuckoo滤波器效率提高约40%非常重要.在c ++中,参考实现对每个存储桶中的项目进行排序,以节省更多空间,利用项目在存储桶中的位置来存储较小的指纹.我稍后会提到的其他库(包括我的)似乎没有这样做.如果有人使用我的库我可能会添加它:).
持续误报率.布隆过滤器的误报率渐渐恶化,因为它们超过了他们的设计尺寸.您可以永久插入物品,但最终您的误报率将接近100%.基于Cuckoo散列的Cuckoo过滤器具有设置容量,其中插入实际上将失败.重复插入非随机项哈希可能会导致Cuckoo过滤器无法插入,可能远在其设计的填充级别之前.
速度.这是主观的,并且在很大程度上取决于硬件,但Cuckoo过滤器在一般情况下通常更快(根据我的经验).大多数Bloom过滤器设计运行两次哈希函数.特别是当使用安全散列函数时,与仅仅插入一次插入项目的Cuckoo过滤器相比,这可能是一个很大的障碍.我见过的代码为Bloom和Cuckoo过滤器使用了各种散列函数.Google的Guava Bloom使用Murmur3,许多其他实现使用SHA1或其他东西.如果可以为您使用案例利用哈希冲突,请确保库使用安全哈希.重要的是要知道Bloom过滤器需要大致恒定的时间来插入,而Cuckoo过滤器具有恒定时间的AVERAGE情况.由于Cuckoo过滤器的容量只有百分之几,因此插入速度会大大降低.即使这样,只有插入速度减慢,所有其他操作都是恒定的平均时间.
灵活性.Bloom过滤器仅支持insert和contains.Cuckoo过滤器还支持删除和限制计数.在参考设计中,Cuckoo过滤器可以确定项目插入的次数,最多可以确定7次.布隆过滤器只能确定是 - 否.Cuckoo过滤器还支持删除插入的项目,与Bloom相比,在很多用例中都是一个很大的好处.使用Bloom过滤器时,由于您无法删除旧项目,因此在"满"(估计误报率超过阈值)时从头开始重新创建过滤器是非常标准的.请注意,当插入开始失败时,Cuckoo过滤器仍然会重建过滤器,因此根据用例,这可能没有实际意义.在某些情况下,Cuckoo过滤器更有用,因为您可以删除项目以保持在过滤器限制内而不是重建.
支持.Cuckoo过滤器是新的,并且不存在许多语言的稳定库.
Bloom过滤器的最大优点是它们在大多数语言中都有更成熟的库支持.科学家们也更好地理解布卢姆滤波器背后的数学.杜鹃过滤器的大多数特征都是凭经验确定的,而布隆过滤器具有坚实的数值基础.这排除了实时和关键系统的Cuckoo过滤器,必须验证其性能,即使实验证据表明Cuckoo过滤器在大多数情况下表现更好.
无耻的插件:我是Java的Cuckoo过滤器库的开发者.CuckooFilter4J.它缺少纸张中使用的桶式半排序,因此空间效率略低于参考实施.在项目自述文件中,我链接到我所知道的其他实现.哪种结构更好取决于您的用例,但主要取决于您的语言是否存在可靠的Cuckoo过滤器实现.
在生产中使用Cuckoo/Bloom过滤器之前,您一定要查看源代码.我在编写自己的库之前阅读了各种库...由于32位底层数组或明显的性能问题,他们中的许多都有静默的大小限制.大多数人没有测试.谷歌的Guava Bloom实现到目前为止最好的代码质量和测试(并支持64位数组限制).Guava的Bloom唯一的缺点是它没有使用安全散列函数的选项,也没有多线程.
在生产系统中,您可能需要多线程来提高速度.Guava的Bloom的答案是为每个线程制作一个不同的过滤器并偶尔组合它们.由于Cuckoo过滤器无法组合,我将并发线程添加到我的Cuckoo过滤器库中.另一个我知道的不是线程安全或不是并发的.
您更喜欢哪种葡萄酒还是奶酪？
一个布隆过滤器是当你有有限的空间,高性价比的查询,并且大多是负面的查询.
在这种情况下,一个布隆过滤器与每个键对应的8位和4个的散列函数为您提供了2.5%的假阳性率 ; 您处理查询的速度比以前快了近40倍,每个密钥只需1个字节.
另一方面,如果以前的任何条件都不成立,那么充当缓存的哈希表是有意义的,尽管显然每个条目需要多于一个字节 :-)
如果它是缓存,你甚至可以跳过cuckoo哈希的硬边案例.这也使得布谷鸟哈希表(或线性哈希以外的任何东西)的大小增加问题没有实际意义.
咕咕过滤器.
"布谷鸟过滤器:实际上比布鲁姆好." Bin Fan,David Andersen,Michael Kaminsky,Michael Mitzenmacher CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994
来自作者的一篇博客:
让我来描述一个布谷鸟过滤器以及本文中的一些内容.如果你想避免技术讨论,你需要知道的是,对于相当大的集合,与相应的布隆过滤器相同的误报率,布谷鸟过滤器使用的空间比布隆过滤器少,查找速度更快(但速度较慢)在插入/构造),并且令人惊讶地还允许删除键(Bloom过滤器不能做).如果你想查看代码,你甚至可以使用github存储库来获取布谷鸟过滤器的代码.
我更喜欢布谷鸟哈希。我对填充系数较高的布隆过滤器可能出现的误报持谨慎态度。
在一个应用程序中使用了布谷鸟哈希，我们有非常大的哈希表并且遇到了内存压力问题。请参阅我的 eCollections 库，网址为http://codeplex.com/ecollections，了解 Cuckoo 哈希变体的实现。
亲切的问候，