布隆过滤器算法

绝地灬酷狼 2024-03-29 16:28 42阅读 0赞

#### 目录 ####

*   *  布隆过滤器主要有下面的参数：
     *  结论
     *  举例

### 布隆过滤器主要有下面的参数： ###

1.假设数据量为n，预期的失误率为p（布隆过滤器大小和每个样本的大小无关）。  
2.根据n和p，算出BloomFilter一共需要多少个bit位，向上取整，记为m。  
3.根据m和n，算出BloomFilter需要多少个哈希函数，向上取整，记为k。  
4.根据修正公式，算出真实的失误率p\_true。  
![在这里插入图片描述][ec862a2b3836443799ebe098bc80f7f9.png]

### 结论 ###

当k固定的时候，m/n越大，误判率越小  
当m/n固定的时候，k越大，误判率越大  
布隆过滤器只和样本量和失误率有关，与单样本大小无关  
**这里贴一个参考资料中m/n、k和False Positive Rate之间的关系图：**

![在这里插入图片描述][89061f41d6bf4f209865bfda3c785e8b.png]  
![在这里插入图片描述][96808d3eaf4e473f81fb246a94c24831.png]

### 举例 ###

假设n为100亿，p=0.0001  
m≈1917亿 1917亿/8/1024/1024/1024约等于22.3G  
k=13.4≈14  
**如果要的空间大，比原本的失误率还要小(当k固定的时候，m/n越大，误判率越小)**

[ec862a2b3836443799ebe098bc80f7f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ae7d8e092c614d50adcc177a1dd99baa.png
[89061f41d6bf4f209865bfda3c785e8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/1ff1ef0161cb4542996b8d27016c0bb3.png
[96808d3eaf4e473f81fb246a94c24831.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/fe007588e4604d498ff269574f4c5795.png

发表评论取消回复

表情：

评论列表（有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

相关布隆过滤器算法

目录布隆过滤器主要有下面的参数：结论举例布隆过滤器主要有下面的参数： 1.假设数据量为n，预期的失误率为p（布隆过

绝地灬酷狼/ 2024年03月29日 16:28/ 0 赞/ 43 阅读

相关布隆过滤器 - Redis 布隆过滤器，Guava 布隆过滤器 BloomFilter - 代码实践

文章目录布隆过滤器 - Redis 布隆过滤器，Guava 布隆过滤器 BloomFilter - 代码实践 1、通过guava 实现的布

ゝ一世哀愁。/ 2023年10月09日 04:22/ 0 赞/ 70 阅读

相关布隆过滤器

布隆过滤器什么是布隆过滤器？布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的`二进制向量`和`一系列随机映射函数`。布

古城微笑少年丶/ 2022年10月15日 12:53/ 0 赞/ 245 阅读

相关布隆过滤器

布隆过滤器实际上就是哈希和位图的结合它的优点：速度快并且节省空间它的缺点：存在误判（比如存在不同的字符串可能存在相同的ASCII，这样我们在判断的时候就会出现误判）

末蓝、/ 2022年06月12日 22:14/ 0 赞/ 281 阅读

相关【算法】——布隆过滤器

前言在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否

快来打我*/ 2022年04月24日 01:32/ 0 赞/ 163 阅读

相关布隆过滤器

布隆过滤器原理布隆过滤器有什么用？布隆过滤器是可以用于判断一个元素是不是在一个集合里，并且相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。特

系统管理员/ 2022年03月25日 07:37/ 0 赞/ 283 阅读

相关布隆过滤器

使用场景 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4u

缺乏、安全感/ 2022年03月01日 11:28/ 0 赞/ 300 阅读

相关布隆过滤器

布隆过滤器介绍 > 布隆过滤器在wiki上的介绍: 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布

喜欢ヅ旅行/ 2021年12月16日 01:01/ 0 赞/ 348 阅读

相关布隆过滤器

布隆过滤器常常被用来检测某个元素是否是巨量数据集合中的成员 1、基本原理： (1)将长度为m的位数组元素全部置为0； (2)对集合S中的某个成员a，分别用k个哈希函数对其

亦凉/ 2021年12月15日 12:59/ 0 赞/ 365 阅读

相关布隆过滤器

布隆过滤器前言布隆过滤器原理布隆过滤器优缺点优点缺点使用场景前言 Hash(散列)函数在计算机

本是古典何须时尚/ 2021年11月04日 13:34/ 0 赞/ 413 阅读