网站建设中广告图片尺寸,中关村网站建设的公司,php网站做分享到朋友圈,怀远网站建设哪家好#x1f44f;作者简介#xff1a;大家好#xff0c;我是爱吃芝士的土豆倪#xff0c;24届校招生Java选手#xff0c;很高兴认识大家#x1f4d5;系列专栏#xff1a;Spring源码、JUC源码、Kafka原理、分布式技术原理、数据库技术#x1f525;如果感觉博主的文章还不错的… 作者简介大家好我是爱吃芝士的土豆倪24届校招生Java选手很高兴认识大家系列专栏Spring源码、JUC源码、Kafka原理、分布式技术原理、数据库技术如果感觉博主的文章还不错的话请三连支持一下博主哦博主正在努力完成2023计划中源码溯源一探究竟联系方式nhs19990716加我进群大家一起学习一起进步一起对抗互联网寒冬 文章目录 Redis布隆过滤器BloomFilter经典面试题简介作用原理基本原理和数据结构hash冲突导致数据不准确 使用步骤布隆过滤器误判率为什么不要删除小总结 使用场景解决缓存穿透问题和redis结合bitmap使用黑名单校验识别垃圾邮件 布隆过滤器实现步骤设计步骤redis的setbit/getbitsetbit构建过程getbit查询是否存在 Redis布隆过滤器BloomFilter
经典面试题
现有50亿个电话号码现有10个电话号码如何要快速准确的判断这些电话号码是否已经存在
1、通过数据库查询-------实现快速有点难。
2、数据预放到内存集合中50亿*8字节大约40G内存太大了。
判断是否存在布隆过滤器了解过吗安全连接网址全球数10亿的网址判断黑名单校验识别垃圾邮件白名单校验识别出合法用户进行后续处理
简介
由一个初值都为零的bit数组和多个哈希函数构成用来快速判断集合中是否存在某个元素 目的减少内存占用方式不保存数据信息只是在内存中做一个是否存在的标记flag
本质上就是判断具体数据是否存在于一个大的集合中
布隆过滤器英语Bloom Filter是 1970 年由布隆提出的。
它实际上是一个很长的二进制数组(00000000)一系列随机hash算法映射函数主要用于判断一个元素是否在集合中。
通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景一般想到的是将集合中所有元素保存起来然后通过比较确定。
链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的增加我们需要的存储空间也会呈现线性增长最终达到瓶颈。同时检索速度也越来越慢上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这个时候布隆过滤器Bloom Filter就应运而生
作用
高效地插入和查询占用空间少返回的结果是不确定性不够完美
重点一个元素如果判定结果存在时元素不一定存在但是判断结果为不存在时则一定不存在
且布隆过滤器可以添加元素但是不能删除元素由于涉及hashcode判断依据删掉元素会导致误判率增加。
总结
如果存在是可能存在
如果不存在则一定不存在可以保证的是如果布隆过滤器判断一个元素不在一个集合中那么这个元素一定不会在集合中
原理
基本原理和数据结构
布隆过滤器原理
布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。
实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样它也一样有那么一点点不精确也存在一定的误判概率
添加key时
使用多个hash函数对key进行hash运算得到一个整数索引值对位数组长度进行取模运算得到一个位置
每个hash函数都会得到一个不同的位置将这几个位置都置1就完成了add操作。
查询key时
只要有其中一位是零就表示这个key不存在但如果都是1则不一定存在对应的key。
结论有是可能有 无是肯定无
hash冲突导致数据不准确
当有变量被加入集合时通过N个映射函数将这个变量映射成位图中的N个点
把它们置为 1假定有两个变量都通过 3 个映射函数。 查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了
如果这些点有任何一个为零则被查询变量一定不在
如果都是 1则被查询变量很可能存在
为什么说是可能存在而不是一定存在呢那是因为映射函数本身就是散列函数散列函数是会有碰撞的。见上图3号坑两个对象都1 哈希函数的概念是将任意大小的输入数据转换成特定大小的输出数据的函数转换后的数据称为哈希值或哈希编码也叫散列值 如果两个散列值是不相同的根据同一函数那么这两个散列值的原始输入也是不相同的。
这个特性是散列函数具有确定性的结果具有这种性质的散列函数称为单向散列函数。
散列函数的输入和输出不是唯一对应关系的如果两个散列值相同两个输入值很可能是相同的但也可能不同
这种情况称为“散列碰撞collision”。
用 hash表存储大数据量时空间效率还是很低当只有一个 hash 函数时还很容易发生哈希碰撞。
使用步骤
布隆过滤器 本质上 是由长度为 m 的位向量或位列表仅包含 0 或 1 位值的列表组成最初所有的值均设置为 0 当我们向布隆过滤器中添加数据时为了尽量地址不冲突会使用多个 hash 函数对 key 进行运算算得一个下标索引值然后对位数组长度进行取模运算得到一个位置每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。
例如我们添加一个字符串wmyskxz对字符串进行多次hash(key) → 取模运行→ 得到坑位 向布隆过滤器查询某个key是否存在时先把这个 key 通过相同的多个 hash 函数进行运算查看对应的位置是否都为 1
只要有一个位为零那么说明布隆过滤器中这个 key 不存在
如果这几个位置全都是 1那么说明极有可能存在
因为这些位置的 1 可能是因为其他的 key 存在导致的也就是前面说过的hash冲突。。。。。
就比如我们在 add 了字符串wmyskxz数据之后很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的
此时我们查询一个没添加过的不存在的字符串inexistent-key它有可能计算后坑位也是1/3/5 这就是误判了…笔记见最下面 布隆过滤器误判率为什么不要删除
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了这样就无法判断究竟是哪个输入产生的
因此误判的根源在于相同的 bit 位被多次映射且置 1。
这种情况也造成了布隆过滤器的删除问题因为布隆过滤器的每一个 bit 并不是独占的很有可能多个元素共享了某一位。
如果我们直接删除这一位的话会影响其他的元素
特性
布隆过滤器可以添加元素但是不能删除元素。因为删掉元素会导致误判率增加。
小总结
是否存在有是很可能有无是肯定无
使用时最好不要让实际元素数量远大于初始化数量一次给够避免扩容
当实际元素数量超过初始化数量时应该对布隆过滤器进行重建重新分配一个size更大的过滤器再将所有的历史元素批量add进行
使用场景
解决缓存穿透问题和redis结合bitmap使用
缓存穿透是什么
一般情况下先查询缓存redis是否有该条数据缓存中没有时再查询数据库。
当数据库也不存在该条数据时每次查询都要访问数据库这就是缓存穿透。
缓存透带来的问题是当有大量请求查询数据库不存在的数据时就会给数据库带来压力甚至会拖垮数据库。
可以使用布隆过滤器解决缓存穿透的问题
把已存在数据的key存在布隆过滤器中相当于redis前面挡着一个布隆过滤器。
当有新的请求时先到布隆过滤器中查询是否存在
如果布隆过滤器中不存在该条数据则直接返回
如果布隆过滤器中已存在才去查询缓存redis如果redis里没查询到则再查询Mysql数据库 黑名单校验识别垃圾邮件
发现存在黑名单中的就执行特定操作。比如识别垃圾邮件只要是邮箱在黑名单中的邮件就识别为垃圾邮件。
假设黑名单的数量是数以亿计的存放起来就是非常耗费存储空间的布隆过滤器则是一个较好的解决方案。
把所有黑名单都放在布隆过滤器中在收到邮件时判断邮件地址是否在布隆过滤器中即可。
布隆过滤器实现步骤
结合bitmap类型手写一个简单的布隆过滤器体会设计思想 设计步骤
redis的setbit/getbit setbit构建过程
PostConstruct初始化白名单数据计算元素的hash值通过上一步hash值算出对应的二进制数组的坑位将对应坑位的值修改为数字1表示存在
getbit查询是否存在
计算元素的hash值通过上一步hash值算出对应的二进制数组的坑位返回对应坑位的值零表示无1表示存在
