极核getshell 2025-11-23 12:36 采纳率: 31.8%
浏览 5
已结题

布隆过滤器是如何通过多个哈希函数和位数组来判断元素“可能存在”或“绝对不存在”的？它的误判率与位数组大小、哈希函数个数之间存在怎样的数学关系？

布隆过滤器是如何通过多个哈希函数和位数组来判断元素“可能存在”或“绝对不存在”的？它的误判率与位数组大小、哈希函数个数之间存在怎样的数学关系？

  • 写回答

4条回答 默认 最新

  • Seal^_^ 优质创作者: 云计算技术领域 2025-11-23 23:36
    关注

    传统布隆过滤器无法安全删除元素

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(3条)

报告相同问题？

  • 哈希的应用——布隆过滤器
    2023-09-09 15:43
    YIN_尹的博客 哈希的应用——布隆过滤器
  • 布隆过滤器：基于哈希函数的原理、应用解析
    2024-04-01 19:34
    无敌岩雀的博客 布隆过滤器（Bloom Filter） 是一种空间效率极高的概率型数据结构，它利用位图和哈希函数来快速判断一个元素是否属于某个集合。布隆过滤器不是传统意义上的过滤器，它不能完整地存储数据，而是以一种紧凑的方式表示...
  • 布隆过滤器原理与应用
    2025-10-31 11:23
    布隆过滤器可以将一个元素映射到一个位数组中，其原理基于哈希函数。当向布隆过滤器中添加元素时，通过多个独立的哈希函数对元素进行哈希，将得到的多个哈希值指向的位数组中的位依次置为1。当查询元素是否存在时，...
  • 布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法
    2020-12-20 03:00
    误判是布隆过滤器的主要缺点，但可以通过调整位数组的长度（m）和哈希函数的数量（k）来控制误判率。当元素数量（n）增加时，误判率也随之上升。理论上，可以通过数学模型分析误判率与m、n、k的关系，优化参数以获得...
  • 利用Java手写一个布隆过滤器Bloom Filter
    2023-05-19 17:21
    布隆过滤器是一种数据结构，主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中，比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...
  • 布隆过滤器的概述及Python实现方法
    2020-09-18 07:55
    在布隆过滤器中，使用了多个哈希函数，当插入一个元素时，这些哈希函数会计算出多个索引位置，这些位置在位数组中的值将被设置为1。当检测元素是否存在时，布隆过滤器检查对应索引位置的位是否都为1。如果都为1，则...
  • Redis 中的布隆过滤器的实现
    2020-12-16 15:04
    【布隆过滤器】是一种非常高效的空间节省型数据结构，用于判断一个元素是否可能存在于一个大规模集合中。它主要用于去重，特别是在处理大量数据时，如网页爬虫判断已访问URL的情况。传统的做法是将URL存入数据库或...
  • 布隆过滤器：大数据量下的快速存在性判断
    2024-08-10 18:15
    三余知行的博客 哈希表适用于精确查找，是一种功能强大且高效的数据...而布隆过滤器适用于在大数据量下的快速存在性判断，是一种高效的概率数据结构。尽管存在一定的误判率，但其高效的空间和时间性能使其在很多应用场景中非常有用。
  • 布隆过滤器到底是什么东西？它有什么用
    2025-02-13 20:46
    梦城忆的博客 布隆过滤器可以用于检索一个元素是否在一个集合中如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是...
  • Redis实现布隆过滤器的方法及原理
    2020-09-08 23:47
    然而，布隆过滤器的主要缺点是存在一定的误识别率，可能会将不存在的元素判断为存在，但不会将存在的元素判断为不存在。 在Redis中，布隆过滤器是作为插件提供的，自Redis 4.0版本开始引入。要使用它，首先需要安装...
  • 《用 Python 实现布隆过滤器：为什么我们需要多个哈希函数？》
    2026-01-13 07:34
    铭渊老黄的博客 布隆过滤器通过位数组和多个哈希函数，以低内存代价提供"可能存在/一定不存在"的判断能力。文章详细讲解了为何需要多个哈希函数（降低误判率），并给出了误判率公式和最优哈希函数数量计算方法。通过爬虫...
  • 布隆过滤器C源码-bloomfilter.rar
    2022-01-10 00:08
    但需要注意的是，可能存在误判，即布隆过滤器可能会将不存在的元素判断为存在，这就是它的概率性质。 6. **容量与误判率**：布隆过滤器的大小（位数组的长度）和使用的哈希函数数量直接影响其误判率。更大的位数组...
  • 布隆过滤器+CBF scala实现+代码详解
    2021-01-20 12:25
    布隆过滤器的核心在于一个位数组和多个独立的哈希函数。 在【描述】中提到，布隆过滤器主要由两部分组成： 1. 位数组（Bit Array）：一个很长的二进制向量，初始状态下所有位都是0。 2. k个独立的哈希函数：每个...
  • 布隆过滤器参数深度解析：如何根据误判率计算位数组大小与哈希函数数量
    2025-12-02 10:29
    Knight_AL的博客 其核心参数是预计元素数量(n)和误判率(p)，由此可计算位数组大小(m)和哈希函数数量(k)。例如存储10万患者ID、1%误判率仅需约117KB内存和6-7个哈希函数。实际应用中，Redisson等工具会自动完成这些计算，开发者只需...
  • 【快速判断是否存在利器】布隆过滤器和布谷鸟过滤器
    2025-05-02 13:54
    雲明的博客 它利用多个哈希函数将一个元素映射到一个位数组中，用于判断一个元素是否属于某个集合。布谷鸟过滤器是布隆过滤器的一种改进版本，由 Bin Fan 等人在 2014 年提出。它通过使用布谷鸟哈希（Cuckoo Hashing）来解决...
  • 没有解决我的问题, 去提问

问题事件

  • 系统已结题 12月1日
  • 已采纳回答 11月23日
  • 创建了问题 11月23日