布隆过滤器简介

news/2024/11/23 0:10:33/

布隆过滤器

什么是布隆过滤器

布隆过滤器能够实现使用较少的空间来判断一个指定的元素是否包含在一个集合中

布隆过滤器并不保存这些数据,所以只能判断是否存在,而并不能取出该元素

使用情景:凡是判断一个元素是否在一个集合中的操作,都可以使用它

布隆过滤器常见使用场景

  1. idea中编写代码,一个单词是否包含在正确拼写的词库中(拼写不正确划绿线的提示)

  2. 公安系统,根据身份证号\人脸信息,判断该人是否在追逃名单中

  3. 爬虫检查一个网址是否被爬取过

为什么使用布隆过滤器

常规的检查一个元素是否在一个集合中的思路是遍历集合,判断元素是否相等

这样的查询效率非常低下

要保证快速确定一个元素是否在一个集合中,我们可以使用HashMap

因为HashMap内部的散列机制,保证更快更高效的找到元素

所以当数据量较小时,用HashMap或HashSet保存对象然后使用它来判定元素是否存在是不错的选择

但是如果数据量太大,每个元素都要生成哈希值来保存,我们也要依靠哈希值来判定是否存在,一般情况下,我们为了保证尽量少的哈希值冲突需要8字节哈希值做保存

long取值范围:-9223372036854775808-----9223372036854775807

5亿条数据 每条8字节计算后结果为需要3.72G内存,随着数据数量增长,占用内存数字可能更大

所以Hash散列或类似算法可以保证高效判断元素是否存在,但是消耗内存较多

所以我们使用布隆过滤器实现,高效判断是否存在的同时,还能节省内存的效果

但是布隆过滤器的算法天生会有误判情况,需要能够容忍,才能使用

布隆过滤器原理

  • 巴顿.布隆于⼀九七零年提出
  • ⼀个很长的⼆进制向量(位数组)
  • ⼀系列随机函数 (哈希)
  • 空间效率和查询效率⾼(又小又快)
  • 有⼀定的误判率(哈希表是精确匹配)

在这里插入图片描述

如果我们向布隆过滤器中保存一个单词

semlinker

我们使用3个hash算法,找到布隆过滤器的位置

算法1:semlinker–> 2

算法2:semlinker–> 4

算法3:semlinker–> 6

会在布隆过滤器中产生如下影响

在这里插入图片描述

查询"Good"在不在布隆过滤器中

算法1:Good–>7

算法2:Good–>3

算法3:Good–>6

我们判断Good单词生成的3,6,7三个位置,只要有一个位置是0

就表示当前集合中没有Good这个单词

一个布隆过滤器不可能存一个单词,一般布隆过滤器都是保存大量数据的

如果有新的元素保存在布隆过滤器中

kakuqo

算法1:kakuqo–>3

算法2:kakuqo–>4

算法3:kakuqo–>7

在这里插入图片描述

新的单词生成3,4,7三个位置

那么现在这个布隆过滤器中2,3,4,6,7都是1了

假如现在有单词bad

算法1:bad–>2

算法2:bad–>3

算法3:bad–>6

判断布隆过滤器2,3,6都是1,所以布隆过滤器会认为bad是存在于这个集合中的

误判就是这样产生的

布隆过滤器误判的效果:

  • 布隆过滤器判断不存在的,一定不在集合中
  • 布隆过滤器判断存在的,有可能不在集合中

过短的布隆过滤器如果保存了很多的数据,可能造成二进制位置值都是1的情况,一旦发送这种情况,布隆过滤器就会判断任何元素都在当前集合中,布隆过滤器也就失效了

所以我们要给布隆过滤器一个合适的大小才能让它更好的为程序服务

  • 优点

空间效率和查询效率⾼

  • 缺点
    • 有⼀定误判率即可(在可接受范围内)。
    • 删除元素困难(不能将该元素hash算法结果位置修改为0,因为可能会影响其他元素)
    • 极端情况下,如果布隆过滤器所有为位置都是1,那么任何元素都会被判断为存在于集合中

设计布隆过滤器

我们在启动布隆过滤器时,需要给它分配一个合理大小的内存

这个大小应该满足

1.内存占用在一个可接受范围

2.不能有太高的误判率(<1%)

内存约节省,误判率越高

内存越大,误判率越低

数学家已经给我们了公式计算误判率

在这里插入图片描述

上面是根据误判率计算布隆过滤器长度的公式

n 是已经添加元素的数量;

k 哈希的次数;

m 布隆过滤器的长度(位数的大小)

Pfp计算结果就是误判率

如果我们已经确定可接受的误判率,想计算需要多少位数既布隆过滤器的长度

在这里插入图片描述

布隆过滤器计算器

https://hur.st/bloomfilter

windows安装redisbloom布隆过滤器

https://blog.csdn.net/weixin_44770915/article/details/107918770


http://www.ppmy.cn/news/529334.html

相关文章

一口好牙能抵千金,瑞尔集团价值几何?

“你们来跟我学牙医吧&#xff01;” 有次朋友聚会&#xff0c;大家半开玩笑似的聊起了各自的工作&#xff0c;他趁着酒兴随口说了这么一句让我们几个跟他学牙医。当时觉得也没什么&#xff0c;现在看瑞尔集团前披露的财务数据&#xff0c;全职牙医平均年收入在百万以上&#…

【C++篇】OOP上部分:封装类和对象

友情链接&#xff1a;C/C系列系统学习目录 知识总结顺序参考C Primer Plus&#xff08;第六版&#xff09;和谭浩强老师的C程序设计&#xff08;第五版&#xff09;等&#xff0c;内容以书中为标准&#xff0c;同时参考其它各类书籍以及优质文章&#xff0c;以至减少知识点上的…

android 无线音乐播放器,玩转Openwrt(二) — 配合Android手机打造无线音乐播放器...

前一篇文章大概介绍了刷入带ADSL驱动的openwrt以及简单的配置,这次就总结下一个好玩的应用,使用android手机+mpd打造一台无线音乐播放器。 所需装备: DB120或者RG100A或者其它BCM6358芯片的路由一台 USB声卡一件(我手里的两个声卡都能很好的工作,一个是steelseries 5HV2,一…

电动车NFC一键启动(仪表总成、电源锁)_Ci522 13.56M非接触式读写器芯片

13.56MHz 非接触式读写器芯片--Ci522&#xff08;A卡&#xff0c;小体积超低成本&#xff09; Ci522是一个高度集成的&#xff0c;工作在13.56MHz的非接触式读写器芯片&#xff0c;阅读器支持ISO/IEC 14443 A/MIFARE。 无需外围其他电路&#xff0c;Ci522的内部发送器可驱动读…

一款实用电动车蓝牙钥匙方案

一款实用电动车蓝牙钥匙方案 电动车因便利&#xff0c;已走进千家万户&#xff0c;科技的发展&#xff0c;蓝牙也慢慢透入到电动车行业。下面介绍一款用电动车蓝牙钥匙方案。 一&#xff1a;电动车蓝牙钥匙功能介绍 蓝牙电动车车载钥匙方案是通过蓝牙连接车钥匙&#xff0c;手…

入门项目·电动车报警器

文章目录 目录 前言 1.3.1 硬件清单列表 1.3.2 振动传感器控制灯 1.3.3 继电器工作逻辑 1.3.4 遥控发送接收433M 1.3.5 项目开发 二. 定时器 1.4 简介 1.5 定时器怎么定时 1.6 定时器编程 1.7 定时器中断方式控制 1.8 遇见潇潇遇见你&#xff0c;不负代码不负卿 前言 1.3.1 硬…

共享单车上的智能锁,做出来有多难?

最早共享单车运营品牌之一的摩拜单车&#xff0c;传闻仅仅开发其独立自主品牌的单车智能锁就使用了半年时间&#xff0c;那么问题来了&#xff0c;共享单车上的智能锁&#xff0c;做出来有多难&#xff1f; 共享单车作为现阶段的资本风口&#xff0c;媒体对共享单车的兴趣和报道…