- 综合排序
- 最热优先
- 最新优先
- 来自专栏木鸟杂记
布谷鸟哈希与布谷鸟过滤器
本文我们介绍一种新的数据结构：布谷鸟过滤器，在紧凑的使用内存同时，支持删除。本着刨根问底的精神，我们从最基础的哈希说起。 实现 布谷鸟过滤器的实现很简单， 论文中也给出了伪代码，贴在这里。 [i1] or bucket[i2] has f then remove a copy of f from this bucket; return True; return False; 参考 布谷鸟哈希和布谷鸟过滤器 Cuckoo_hashing#cite_note-Cuckoo-1 布谷鸟过滤器 Cuckoo Filter: Practically Better Than Bloom https://www.cs.cmu.edu /~binfan/papers/conext14_cuckoofilter.pdf 布谷鸟过滤器实现：[https://coolshell.cn/articles/17225.html]
2K11编辑于 2021-12-09 - 来自专栏luozhiyun的技术学习
Go语言实现布谷鸟过滤器
想要体验布隆过滤器的插入步骤的可以看看这里：https://www.jasondavies.com/bloomfilter/ 于是布谷鸟过滤器(Cuckoo filter)华丽降世了。 当 Z 插入完毕之后如下： [Cuckoo Filter Insert2] 布谷鸟过滤器 布谷鸟过滤器和上面的实现原理结构是差不多的，不同的是上面的数组结构会存储整个元素，而布谷鸟过滤器中只会存储元素的几个 除此之外还有一个约束条件是布谷鸟过滤器强制数组的长度必须是 2 的指数，所以在布谷鸟过滤器中不需要对数组的长度取模，取而代之的是取 hash 值的最后 n 位。 如一个布谷鸟过滤器中数组的长度2^8即256，那么取 hash 值的最后 n 位即：hash & 255这样就可以得到最终的位置信息。 ，我们不妨想一下，如果布谷鸟过滤器对同一个元素进行多次连续的插入会怎样？
1.4K20发布于 2021-02-28 - 来自专栏架构之美
Redis 之布隆过滤器与布谷鸟过滤器
- 布谷鸟过滤器 - 为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。 相比布谷鸟过滤器，布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。 空间效率低是因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。 而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。 为啥要取名布谷鸟呢? 有个成语，「鸠占鹊巢」,布谷鸟也是,布谷鸟从来不自己筑巢。它将自己的蛋产在别人的巢里，让别人来帮忙孵化。 布谷鸟过滤器 布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。
1.1K20发布于 2021-11-23 - 来自专栏码洞
布隆过滤器过时了，未来属于布谷鸟过滤器？
为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。 空间效率低是因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。 而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。 但是经过我一段时间的调查研究发现，布谷鸟过滤器并没有它声称的那么美好。 在向读者具体说明这个问题之前，还是先给读者仔细讲解一下布谷鸟过滤器的原理。 布谷鸟哈希 布谷鸟过滤器源于布谷鸟哈希算法，布谷鸟哈希算法源于生活 —— 那个热爱「鸠占鹊巢」的布谷鸟。 布谷鸟过滤器 布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。
3.6K40发布于 2019-06-17 - 来自专栏OSChina
由布隆过滤器和布谷鸟过滤器引发得感想
public static void main(String[] args) { int total = 100000000; System.out.println("
34410发布于 2021-03-12 - 来自专栏IT大咖说
高级算法篇：布隆过滤器？非也，布谷鸟过滤器是也
过滤器在数据科学中的应用十分广泛，包括数据库查询、数据快速检索，数据去重等等。过滤器的出现是为了解决在大量数据的环境下，能够更好更快的（节省计算资源或者存储资源）筛查数据的需求。 但实际上邮件地址太多，如果全部储存的话占用大量存储资源并且在比较的时候也会占用大量的计算资源，所以用过滤器来存储判断可以解决问题。 接下来介绍最基本的两个过滤器，帮助大家理解过滤器技术的实现。 当然这个过程可能无限反复下去，那么一般会对踢出操作设一个阈值，超过阈值则认为过滤器容量不足，需要对其进行扩容。 这个踢出的过程类似于布谷鸟下蛋的过程，所以称其为布谷鸟过滤器。 附：散列技术 散列技术（也就是 hash 映射）因为在 bloom 过滤器 与 cuckoo 过滤器中就使用到了 hash 技术去映射，主要是散列表查找（哈希表）： 引入 在顺序表查找（逐个比较）乃至有序表查找
3.5K10发布于 2019-11-26 - 来自专栏猿天地
居然还有布谷鸟过滤器，有何用处呢？
增强版 布谷鸟过滤器 为了解决布隆过滤器不能删除元素的问题， 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。 相比布谷鸟过滤器，布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。 空间效率低是因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省40%多。不过布隆过滤器并没有要求位图的长度必须是2的指数，而布谷鸟过滤器必须有这个要求。 而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。 为啥要取名布谷鸟呢? 有个成语，「鸠占鹊巢」，布谷鸟也是，布谷鸟从来不自己筑巢。它将自己的蛋产在别人的巢里，让别人来帮忙孵化。 布谷鸟过滤器 布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。
80120编辑于 2022-08-26 - 来自专栏Java技术栈
拼夕夕二面：说说布隆过滤器与布谷鸟过滤器？应用场景？我懵了。。
布谷鸟过滤器 ---- 为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。 空间效率低是因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。 而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。 为啥要取名布谷鸟呢? 有个成语，「鸠占鹊巢」,布谷鸟也是,布谷鸟从来不自己筑巢。它将自己的蛋产在别人的巢里，让别人来帮忙孵化。 布谷鸟过滤器 ---- 布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。 首先布谷鸟过滤器还是只会选用两个 hash 函数，但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊，因为过滤器中只能存储指纹信息。
59020编辑于 2023-02-27 - 来自专栏福大大架构师每日一题
2020-11-09：谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点？
福哥答案2020-11-09： 相同点： 都是过滤器。 不同点： 算法：布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。 能否删除：布隆过滤器无法删除元素。 布谷鸟过滤器可以删除元素，有误删可能。 空间是否2的指数：布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。 空间利用率：相同误判下，布谷鸟空间节省40%多。 查询性能：布隆过滤器查询性能弱，原因是使用了多个hash函数，内存跨度大，缓存行命中率低。布谷鸟过滤器访问内存次数低，效率相对高。 哈希相关：布隆过滤器的多个函数函数之间没关系。 布谷鸟过滤器的两个哈希函数可互相推导，两者有关系，用到了【空间是2的指数】和【按位与】。 重复插入相同元素：布隆过滤器天然自带重复过滤。布谷鸟过滤器会发生挤兑循环问题。 *** Redis布隆Bloom过滤器 布隆过滤器过时了，未来属于布谷鸟过滤器？ 【Redis 第七篇】面试加分项：缓存穿透，布隆过滤器-计数过滤器-布谷鸟过滤器（好文005）
2.1K10发布于 2020-11-09 - 来自专栏周拱壹卒
【译】Cuckoo filter
布谷鸟过滤器的指纹大小将直接决定误报率。 适用场景 定向广告活动（广告，零售） 此类应用程序回答了这个问题：用户是否已注册此活动？ 为每个活动使用一个布谷鸟过滤器，填充目标用户的 ID。 尝试下一个广告/布谷鸟过滤器。 折扣码/优惠券验证（零售，在线商店） 此类应用程序回答了这个问题：此折扣码/优惠券是否已被使用？ 使用一个填充所有折扣码/优惠券的布谷鸟过滤器。 注意：除了这两种场景，布谷鸟过滤器还非常适用于所有布隆过滤器的使用场景。 示例 你会了解到如何创建一个初始容量为 1,000 个元素的空布谷鸟过滤器，添加元素，检查它们的存在性，再删除它们。 布谷鸟过滤器 布隆过滤器通常在插入元素时表现出更好的性能和可扩展性（因此，如果您经常向数据集中添加元素，那么布隆过滤器可能是理想的选择）。布谷鸟过滤器在检查操作上更快，并且还允许删除操作。 请注意，在布谷鸟过滤器中重复插入相同元素会导致多次添加这些元素，从而使过滤器被填满。 由于布谷鸟过滤器的工作原理，过滤器可能会在达到容量之前就声明自己已满，因此填充率可能永远不会达到 100%。
10310编辑于 2026-03-16 - 来自专栏Java技术栈
面试官：大量请求 Redis 不存在的数据，从而打倒数据库，你有什么方案？
布谷鸟过滤器 为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。 相比布谷鸟过滤器，布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。 空间效率低是因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。 而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。 点击关注公众号，Java干货及时送达 为啥要取名布谷鸟呢? 有个成语，「鸠占鹊巢」,布谷鸟也是,布谷鸟从来不自己筑巢。 布谷鸟过滤器 布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。
49610编辑于 2022-06-06 - 来自专栏物流IT圈
Redis布隆Bloom过滤器
Redis提供了三种强大数据结构：HyperLogLog，布隆过滤器和布谷鸟过滤器。 布隆不够时：布谷鸟Cuckoo过滤器 布隆过滤器是一种经过时间考验的惊人数据结构，可满足大多数需求，但它们并不完美，他们最大的缺点是无法删除项目，由于是一种数据存储在过滤器内的方式，一旦添加了项目，就无法将其与其他数据项完全分开 Cuckoo过滤器提供更新的概率数据结构，它以不同方式存储信息，导致性能特征略有不同，并且能够在需要时删除项目。 布谷鸟过滤器在下面情况比布隆过滤器更好： 1. 删除项目 2. 更快的插入（当过滤器的填充率低于80％时） 在以下情况下，布谷鸟过滤器比布隆过滤器更糟糕： 1. 你的填充率超过80％;在这种情况下，布谷鸟过滤器的插入速度很快就会低于布隆。 2. 你有更宽松的目标错误率（大于3％），使布谷鸟过滤器的空间效率降低 3.
1.7K40发布于 2019-07-16 - 来自专栏程序员面试小技巧
5分钟教你认识布隆过滤器
我们只能去开新的bitmap去使用对于布隆过滤器，无法删除，有两个解决办法，一个是计数布隆过滤器，另一个就是布谷鸟过滤器，在文末做补充。 ，就出现了一个计数布隆过滤器或者叫做增强版布隆过滤器，这个过滤器简单来说就是原来的布隆过滤器采用bitmap，而计数过滤器使用的是数组。 当变量进入布隆过滤器那么就+1，当删除时就-1.这样就解决了布隆过滤器不能删除的问题，但是这个计数过滤器依旧也还是有误判的概率拓展：布谷鸟过滤器布谷鸟过滤器的原理简单来说就是，一个变量进行函数运算，算出两个位置 ，如果有空位则插入，如果没有空位就会挤走一个指纹，并且为这个指纹重新去寻找新的位置（当然不会去无限寻找的情况，一般会设置一个阈值，超过阈值就会去扩容）布谷鸟过滤器是可以进行删除的。 之后我将新开一篇文章给大家详细讲一下布谷鸟过滤器的原理。总结5分钟教你认识布隆过滤器，你会了吗？
77130编辑于 2023-02-14 - 来自专栏Java面试教程
原来布隆，他还会.......
我们只能去开新的bitmap去使用 对于布隆过滤器，无法删除，有两个解决办法，一个是计数布隆过滤器，另一个就是布谷鸟过滤器，在文末做补充。 ，就出现了一个计数布隆过滤器或者叫做增强版布隆过滤器，这个过滤器简单来说就是 原来的布隆过滤器采用bitmap，而计数过滤器使用的是数组。 当变量进入布隆过滤器经过函数运算那么就+1，当删除时就-1，无法删除的问题这样子可以去解决，但是这个计数过滤器仍然也还是有误判的概率 拓展：布谷鸟过滤器 布谷鸟过滤器的原理简单来说就是，一个变量进行函数运算 ，算出两个位置，如果有空位则插入，如果没有空位就会挤走一个指纹，并且为这个指纹重新去寻找新的位置（当然不会去无限寻找的情况，一般会设置一个阈值，超过阈值就会去扩容） 布谷鸟过滤器是可以进行删除的。 之后我将新开一篇文章给大家详细讲一下布谷鸟过滤器的原理。 总结 布隆.....过滤器~ 你懂了吗~
32530编辑于 2023-03-20 - 来自专栏爱可生开源社区
技术分享 | 缓存穿透 - Redis Module 之布隆过滤器
布隆过滤器就是一个用来确认一个元素是否存在于集合内的工具。 介绍： 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。 对于业务来说，当返回某个数据存在与过滤器时，这个数据可能不存在与数据库；当返回某个数据不存在时，那么这个数据一定不存在； 布隆过滤器并不能删除元素（布谷鸟过滤器支持） 原理： 插入一个key，通过k次取模算出每次转换后对应的 仓库地址：https://github.com/RedisBloom/RedisBloom 文档地址：https://redis.io/docs/stack/bloom RedisBloom同时提供了布隆过滤器与布谷鸟过滤器 ，适用场景如下： 布隆过滤器：插入性能、可伸缩性较好 布谷鸟过滤器：查询性能较好、允许删除集合中的元素 五、案例说明 前置工作略过（下载、编译、加载、重启 Redis） # redis-cli # BF 否 32 布谷鸟过滤器的默认最大扩展 六、总结 布隆过滤器或布谷鸟过滤器可以用来解决缓存穿透的问题； 需要注意数据同步（如新增用户时需要在过滤器添加用户ID）与缓存预热（空过滤器启动前需要把已有数据先写入
63230编辑于 2022-12-21 - 来自专栏技术汇总专栏
布谷鸟搜索算法（Cuckoo Search）
布谷鸟搜索算法（Cuckoo Search, CS）就是其中的一种，它模拟了布谷鸟的繁殖行为，用于求解复杂的全局优化问题。 布谷鸟搜索算法概述算法背景布谷鸟搜索算法是由Yang和Deb于2009年提出的。它基于布谷鸟的繁殖策略，即布谷鸟将自己的蛋放在其他鸟类的巢中，借此利用其他鸟的育雏行为。 而布谷鸟的繁殖行为中，最关键的两点是“放置蛋的位置”和“被发现的概率”。通过模拟这些行为，布谷鸟搜索算法能够在解空间中进行探索与开发，从而找到最优解。 算法原理布谷鸟搜索算法的基本步骤可以分为以下几个部分：初始化种群： 在解空间内随机生成初始解（鸟巢）。繁殖过程： 每只布谷鸟通过跳跃（即用Lévy飞行）来探索解空间。 布谷鸟搜索算法的实际应用布谷鸟搜索算法因其强大的全局优化能力，被广泛应用于各个领域，以下是一些典型的应用场景：1.
90410编辑于 2025-02-10 - 来自专栏java学习java
Redis之布隆过滤器（Bloom Filter）解读
隆过滤器定义 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。 当实际元素数量超过初始化数量时,应该对布隆过滤器进行重建,重新分配一个 size更大的过滤器,再将所有的历史元素批量add进行 布隆过滤器优缺点 优点：高效插入和查询，内存占用空间少。 ,判断邮件地址是否在布隆过滤器中即可 布谷鸟过滤器(了解) ①. 为了解决布隆过滤器不能删除元素的问题,布谷鸟过滤器横空出世。论文《Cuckoo Filter:Better Than Bloom》 ②. 作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。 相比布谷鸟过滤器而言布隆过滤器有以下不足:查询性能弱、空间利用效率低、不支持反向操作(删除)以及不支持计数
1.2K50编辑于 2023-10-15 - 来自专栏进阶之路
【JAVA今法修真】 第四章 redis特性 击穿雪崩！
所以布隆过滤器存在误判的情况，但是如果布隆过滤器判断某个元素不在布隆过滤器中，那么这个值就一定不在。 让我们继续深入 1、5布谷鸟过滤器 为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。 相比布隆过滤器，布谷鸟过滤器有以下几点：查询性能更强、空间利用效率更高、支持反向操作（删除）以及计数。 布谷鸟过滤器名称源于采取了一种和布谷鸟一样的养娃方法，最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希，得到桶中的两个位置。 如果两个位置都为为空则将key随机存入其中一个位置 如果只有一个位置为空则存入为空的位置 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置 布谷鸟过滤器源于布谷鸟哈希算法，他巧妙的设计了一个独特的
57530编辑于 2022-03-07 - 来自专栏小牛肉带你学Java
区块链技术中的Merkle树是如何实现优化Gossip协议的？
其实这种操作很常见，如果你做过黑马点评的话，就会用到一个数据结构叫做布隆过滤器。而布隆过滤器因为设计问题无法做到删除元素。为了改进这一点，我们设计出了布谷鸟过滤器。 布谷鸟哈希过滤器采用布谷鸟哈希结构。我们将数据进行哈希之后得到一个指纹，放入到这个布谷鸟哈希结构中。 每一个指纹会有两个位置可以放，以此来应对挤占情况。 如果你不了解布谷鸟过滤器，可以看一下我之前写的这一篇文章： 不知道什么是布谷鸟过滤器？
45010编辑于 2024-11-11 - 来自专栏韩曙亮的移动开发专栏
【FFmpeg】Filter 过滤器 ① ( FFmpeg 过滤器简介 | 过滤器概念 | 过滤器用法 | 过滤器工作流程 | 过滤器文档 | 过滤器分类 )
文章目录 一、FFmpeg 过滤器 Filter 简介 1、FFmpeg 过滤器概念 2、FFmpeg 过滤器用法 3、FFmpeg 过滤器工作流程 4、FFmpeg 过滤器文档 二、FFmpeg 过滤器 在 FFmpeg 命令行 中 , 将 过滤器 名称 作为参数进行传递 , 通过 命令行参数 -vf 设置视频过滤器 通过 命令行参数 -af 设置 音频过滤器 ; 过滤器链 : 多个过滤器 可以链式组合 复杂 过滤器图 Filter Graph ; 可实现 将 多个音视频流 通过 不同的 过滤器 进行处理 ; 3、FFmpeg 过滤器工作流程 FFmpeg 过滤器工作流程 : 输入 : 过滤器 接收 - 根据功能分类 根据过滤器的功能 , 可以将过滤器分为很多类型 : scale : 视频缩放 过滤器 ; overlay : 视频叠加 过滤器 ; crop : 视频裁剪 过滤器 ; trim : 视频截取 过滤器 ; rotate : 视频旋转 过滤器 ; movie : 视频加载 过滤器 ; 更多的 视频过滤器 参考 FFmpeg 过滤器文档 的 " 11 视频滤镜 " 章节 ;
1.8K10编辑于 2024-05-14
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号