00:00
来,同学们接下来给大家介绍一下布隆过滤器,它到底是什么?为什么可以用它来解决上面这些面试题,走起。一句话,由一个初始都为零的比特数组和多个哈希函数构成,那么注意比特map加多个哈希函数构成的干嘛的?用来快速判断集合中是否存在某个元素的一种数据结构?那么来同学们,我相信我们在小白篇已经讲过bit map了。尤其是用于签到这个事说过很多遍了,那么布隆过滤器它初始状态就这么一个东东,那么来同学们,我们可以随便演示一下,比方说set beat,那么现在customer,假设这个时候就是109这个用户。签到。假设现在就是一月份,那么一月份。
01:02
一个月最多31天,你第一天来了我就签个一,你第二天来了我就签个一,你第三天来了再签个一,后续没有那么默认,第四个就是零,反正你隔一天我就更新一下,针对于每一个用户,他单月。登录和签到的情况,该怎么做总结就做总结,该怎么合并就后续合并,那么取也简单。那么。Get beat customer谁呀,109号这个用户,那么现在一月份,请问一月一二号你登录了吗?有一就是登陆,没有一就是没登录,OK so easy,那杨哥这这不就是我们讲的bit map吗?跟这个布过滤器有毛线关系,那别忘了上面这句话。什么动作,哈希函数,哎,所以说放到这两个一起打G,让同学们锻炼这个抽象思维,更加深这个难度,因为到后面咱们呢,自己手写一个好,那么接下来我们来看一下它的设计思想啊。
02:17
首先他的目的是减少内存占用,我不保存数据信息啊,至于说这个109号这个客户,他的各种是个什么样的客户的,不管我们只有010些,只是在内存中做一个是否存在,哎,Yes or no,类似于这样的一个标记flag,那么好了,接下来你可能会阉格,那么请问这个哈希函数用到哪?同学们,我先提出这个问题。待会儿我们来碰。但是在提出这个问题之前,我先引导大家。我们刚才都晓得了,这个bit map已经落地了,那么问题是这个mid map它就一到30位,那么请问再说bit map之前我们结合Java,咱们Java是不是学过一种集合类,里面有种东西叫哈希map,那么哈希map的底层数据结构是个什么?是不是数组加链表加红黑数,那么默认是16个一个node类型的数组,它到底落到哪个位置上?那么这个时候是不是需要靠我们的哈希函数来进行落地来?
03:26
得到我对应扎进去的这个坑,OK,那比如说某个T通过哈希函数的一次或者多次运算好,最后你在五号坑好,那么这个时候五号坑就表明也许是一个安全的。网址也许是一个黑名单的一个非法邮件,那么以后我就来判断这个五号坑有没有,如果有就说明它可能是合法的,也可能是非法的,最后我们来决定放行还是过滤后面的程序,那么所以说一句话,它呢本质就是判断具体数据是否存在于一个大的集合当中,能够给你快速的检索出来,那在这同学们可能会有第二个积分,那杨哥这个废什么话,你前面不是讲过一个牛逼的。
04:16
二的六十四次方都可以保存的hyper log log嘛,你别忘了hyper log log用在什么?它只会给你出一个数字啊。现在大致上。有多少人访问了我的首页,UV只算一次啊,假设现在有9000万的人进来了就没了,但是他现在是更复杂的,比如说含签到,含判断,黑名单,白名单,大数据判断等等,我要求具体的某些坑要有些什么东西,哎。它功能上和hyper log log有点相似,但是它实际的实现上是完全不一样的,那么这个就是我们的布隆过滤器,那么接下来看好布隆过滤器说到底呢,是有种类似什么set的数据结构,Set什么意思啊,是不是气巢无序无重复,只是统计结果在巨量的数据下面,它有点小瑕疵啊,不够完美。
05:12
因为本身世界上就不存在完美的东西,那么下面同学们先复习第一个知识点,请问hyper log log的小瑕疵啊?它的误判率,它的误差是多少?请同学们回忆一下,知道的同学请把答案打在对话框,谢谢同学们的回复啊,记得不错,有些同学呢,立刻答出来了。0.81 OK,那么涉及到这对标,那杨哥布隆过滤器它的误差率是多少呢?它的算法和我们hi log log不一样,为什么它不够完美呢?不够完美说明有误差,为什么?因为只要有哈希函数的地方就会有冲突,有人的地方就恩怨,有哈希函数的地方就有江湖,就有冲突。OK,来吧,过来看布隆过滤器,那七零年有布隆这个科学家提出来的,它实际上就是一个很长很长的初始值都是000000的。
06:08
一大堆比特位的二进制数组,再加注意,不是一个,是一系列随机的哈希函数算法映射的一个函数,主要用于判断一个元素是否在集合当中。首先啊,我们会遇到很多要判断一个元素是否在某个集合当中的业务场景,那一般想到集合中所有元素保存起来过一遍,然后通过比较,那么比如说可以是链表,哎,在这个列表里面有没有这个节点可以是二叉树,最经典的是不是可以我们的哈西那K如果出现了标个一,又出现第二次了,从一变成二,出现第三次了。是三,那么我们就每个来判断,每一个K是一的就代表不重复,那么之前这三种数据结构都可以干这个活,但是随着集合中元素的增加,二,我们需要的存储空间就会呈线性的增长,量表越来越长,数越来越深,哈希表的值越来越多,那么弟兄们还是那句话,量变引起质变,数据多了就麻烦,那么我们要求数据量不管再多,你的检索要快啊,你不能说检索越来越慢,那么上面量表数,哈希他们的时间复杂度都这个,那么这个时候我们会发现在中小型的公司啊,这三个够用了,在大厂这样海量级的数据,我要求查的快,从的进,还有多维度的统计,那么这个时候力不从心,所以我们的不能过滤器也应运而生,一个很大的数据,一个网址,一个邮件,我只需要判断你一个坑位,或者是多个坑位组合起来,如果都是一,就说明你存在,如果是零,就说明你不存在。那么。
07:48
这样我们是不是只需要用比特位很小很小的一个位数就能决定一就是有零就是五,那这样我是不是可以用很小的空间来决定你是否存在,OK,所以同学们,这个就是我们的布隆过滤器。
08:06
了解了布隆过滤器是什么,接下来我们就要说一下布隆器的底层原理和它能干些什么。注意,这有个非常重要的考点,要求各位同学一剑封喉,一击必杀,能够准确的回答给面试官,因为他会问问你,你觉得布隆过滤器它最大的特点是什么?哎,它是一个不够完美的过滤器,那么它底层原理和机制是什么?它的特点是什么?好挂着问题跟着走,这一点很重要。来布隆过滤器,它能够高效的插入和查询,占用的空间很少,因为它是比特位的速度。但是它反馈的结果是不确定性的,不够完美,为什么啊?来,同学们,下面我们来说一下,通过前面的讲解我们已经明白了,所谓的布隆过滤器就等于我们的比特map、比特位数组加一系列哈希函数来进行坑位的分派和占用,它的目的是减少内存占用,要求数据量查的快,数据小,能够做充分的映射。我不存具体的记录,没有什么几个亿的数据灌进去我们这个坑位上面的一和零两种状态来表示,这个一和零可以表示除和false yes no,那么它是不是一个合法的邮件地址,它是不是一个合法的网址,它是不是一个签到的用户等等等等,那么一系列的问题我们都转换为从复杂到简单,用一、零来表示,所以它不保存数据记录,没有记录信息,只是在内存中。
09:48
对某一个我们约定好的坑位上所表达的合法网址,合法电电子邮件地址啊,合法的手机号码,合法的微信号码等等来判断一个是否存在yes问no是否合法的一个标记位,仅此而已,所以它占用空间少。但由于他来判定坑位的时候用的是一系列的哈希函数,我们在学Java基础平的输出。
10:16
集合类哈希map只要用哈希函数100%存在哈希冲突,那么这会导致可能某些key他们呢,多条记录占用了同一个坑位,那么我就分不清这个五号坑位。可能有三条记录,那么这个一就表达了三个都是合法用户,或者是三个都是非法用户,那么所以它有点瑕疵,不够完美,这个是它的一个小小的缺点,但是能接受,所以正因为如此,它的优点占用空间少,缺点不够完美,基于此。哈希函数来判定看位,基于此,它的重点,也就是我们要跟面试官说的它的主要特点,那就是如果一个元素在不论过去里面来进行是否存在判断,如果存在元素不一定存在,前面说过了,可能五号坑位哈希冲突了,这几个坑位表达了。
11:15
ABC3个意思,那么现在我知道了到五号坑位有没有数据幺是个一,那到底是A存在,是B存在,是C存在呢?所以说它这如果是存在,这个坑位将将好只有一个记录的话,那么好肯定存在,但是有可能存在多条记录,所以综合而言,它存在的话,元素不一定真就是我们希望的那条记录就存在,也许我判断的是A,我需要的是A,到了五号开,但是五号开C也跟我算出了同样的哈,是扣的,也占用了五号坑,我按照坑位数找到五号坑位,我希望得到A,但是没想到了得到了跟我同样看位的C,所以存在的时候元素不一定存在哈希冲突导致了,但是判断结果为不存在的时候,则一定不存在,哎,所以说它准确的是后面这个,这是它的重要特点,一句话,有是可能有,无是绝对无。讲完了,这个就是我们。
12:15
布隆过滤器的面试回答的重要特点,第三一个问题,布隆过滤器可以添加元素对吧?但是最好不要删元素。由于涉及哈希code的判断依据,你删掉元素会导致误判率增加。前面讲过了,假设五号开ABC。三个记录都在五号开,你觉得A我不想要了,我要把它从五号坑拔掉,哎,但是对不起哦,现在五号开是有ABC3个记录,那么你一杀,那么这个时候你本来想杀A,你也确实杀了A了,但是是不是B和C也连坐了,那么这样的话就会增加我们的误判率,因为他们有哈希冲突,共用坑位这么一个小小的影响,所以兄弟你不吃这碗饭可以,但是你不要掀桌子砸这口锅,明白了吗?你不能说你A不要了,你把BC的财路也给断了,坑位也给占了,那么这样误判率就会增加,所以不能过滤器它的小总结。
13:14
有是可能有,因为哈希冲突所导致,无是肯定无,只要这个坑位是零,肯定没有。所以我们可以保证,如果不用过滤器判断一个元素不在一个集合当中,那么这个元素一定不会存在于这个集合,那么有这个准确的,那么坦白讲,我们做黑白名单,做合法校验,做是否签到,他是不是就是一把好手啊?接下来我们落了布隆过滤器的底层原理,那么了解了它最重要的特点以后,我们下面来看一下布隆过滤器它实际的原理和数据结构。首先啊,来看一下。它呢,是专门用来解决去重问题的高级数据结构,实际上就是一个大型的位数组和几个不同的一系列的无偏哈希函数。
14:12
所谓的无片就是希望你分布均匀,那么尽量的是吧,都别挤在一个坑位,尽量减少这个哈希冲突,那么它呢,有一个初值的为零的比特数组和多个哈希函数构成,那么用来快速判断数据是否存在,但是跟哈log log一样,它呢,有误判率。好了,那么下面我们来看一下啊,添加K和查询K在不同过滤器里面它是怎么做的呢?首先它添加K的时候,会使用一系列多个哈希函数对K进行哈希运算,得到一个整数的索引值,对位数组长度进行什么东东取模运算,再得到一个位置,哎,所以说每个哈希函数都会得到一个不同的位置,尽量给它分布均匀分开,避免撞车,不要同一条记录占。
15:06
不要不同的记录,多条记录占了同一个坑位,那么将这几个坑位都直接就完成了我们的at的操作,这是添加K,那么查询K的时候呢,只要有其中一位是零,就表示这个K不存在,如果都是一,则不一定存在对应的KOK,还是冲突,所以幺是可能有,无是肯定无,这儿同学们。重要补充说一下,咱们在做签到的这种简单业务的时候,109号这个客户一月份的签到情况,那么就是yes问到就行了,他不牵扯到特别复杂的函数,函数计算。但是后续我们就会明白,也许我某个K啊,我希望是这样的,通过哈希函数一,哈希函数二,哈希函数三,哎,然后再取模。
16:03
那么可能他算出来的这个坑位啊,类似于这个K,它是比如说17号坑位是一,五号坑位是一,然后八号坑位是。一相当于这个T,它是由。17号坑位,五号坑位,八号坑位,三个坑位是一,就像开一把锁有三把钥匙,你看我才认为你判断都是一才存在,只要其中有一个是零,那么我认为跟我们所绑定的位置是不一样,所以说反过来。我既可以用一个坑位来表示一个元素是否存在,也可以用一套组合拳多个哈希函数得到多个坑位,比如说五、七、八三个坑位。来表示一个元素是否存在,哎,所以说这你要转的过这个弯,那么下面我们来看哈希冲突导致数据不精准,它的瑕疵和不完美的地方是这么来的,当变量要被加到这个集合里面,通过N个映射函数将这。
17:12
变量映射成位图中的N个点啊,我就这个K映射成了三个位置,这三个位置我呢,我到这儿我要把这三个位置都视为一啊,假设有两个变量都通过三个映射函数OBJECT1 object2,那么请看啊这三个假设OP1 function1,它在,一号坑位有了,它又在,三号坑位也有了,它又在了,12号坑位也有了,Op们记得是二它呢,通过一线的运刷吸取取模,取模了以后一号坑位有。八号坑位有。然后呢,13号坑位有,哎,这个时候就麻烦了。三号坑位有一两个意思,既代表OBJECT1,也代表object啊,那么你告诉我这个你能乱删吗?你一删也许你要删的时候object好,也许效果你达到了,但是你连坐是不是把OBJECT2也给干掉了。
18:15
这个时候就属于情愿错杀1000也不放过一个,你这样一连做,打击面是不是就大?所以不能过滤器建立,添加完成以后尽量不要删除,那么来,同学们,当我们添加完成查询某个变量的时候,我们只需要看看假设OBJECT1反向的有三个函数来定义它的坑位,那么来吧,111,那么。如果三个坑位都是一,那么大概率知道集合中有没有它了,如果这些点有任何一个为零,则查询变量一定不存在,这就是刚才我们所说的要无是肯定无,但如果都是一呢,则被查询的是很可能存在,因为它存在着这个哈希冲突啊,有可能这三个坑位是存了三个记录进去。
19:08
为什么说是可能呢,而不是一定呢?那是因为映射的本身就是一个散列哈希的函数,散列函数有碰撞,那么刚才我们已经看到三号开是不是两个对象都牵扯进来了,所以同学们基于布隆过滤器有这样的快速检测的特性,我们就可以把数据写到数据库的时候,先使用布隆过滤器做个标记,现在看看它在布隆过滤器里面有。假设red挂了或者red没有挂,我们在red前面在挡一套波隆过滤器,那么我们应用查询数据的时候,就可以先通过第一步查询过滤器,不能过滤器来判断是否存在,如果不存在,那么是什么?肯定没有,咱也不用往后跑去访问red或者是MYSQL,那么这样一来,即便发生了缓存串透,那么大量请求也只会查询red和不动过滤器,而不会积压到数据库啊。后面我们说什么叫缓存穿透,意思就是说。
20:08
多次高频的查询,Red也没有MYS克有没有穿透了,那么这样对系统呢,是伤害大的,但是前面打了个波隆过滤器,我先去布隆过滤器里面一查,有是可能有,那么我再去访问red真正真正的来决定有没有,如果red没有,再去查MYQ2次确认有没有,那么这样发生缓存穿透的概率是不是很小?关键是如果没有到波过滤器这一层,滚,你根本不会反问到后面的register,更不可能。再访问到red后面的MYSQL,那这样是不是大大减轻了后面的压力,所以就不会影响数据库的正常运行,那么波动过滤器可以使用red实现,本身就能够承担较大的并发访问的压力,OK,它就给它分担了。同学们,接下来我们来看一下我们的哈希函数的这个冲突来。哈希函数啊,它定义是将任意大小数的元素转换成特定大小输出的这么一个函数,转换后的数据称为哈希值,哈是编码,也叫散列值。那么同学们简单的啊,To这个T或者一个关键数据,一个网址,一个邮箱,一个号码,等待我通过哈希函数,哎,算出来我的值是这么一个Jack Linda和bar瑞,大家请看红圈圈这块。
21:28
值是不一样的值,但是汤姆和bar瑞尔是肯定不一样的名字。但是碰撞出来的哈希值是不是同一个,那么假设他们有同一个哈希值,取模或者取取模了以后又放在了比特map同样的一个坑位里面,那么这样是不是一个坑位表达了两个意思啊?哎,所以如果两个散列值是不相同的,那么这两个散列值的原始输入也不应该是相同的,对吧,那比如说这。琳达是这个,Bar瑞尔是这个,那100%,如果说不哈系统图那太完美了,那就是对吧?唯一性这个特性是三列式具有的确定性的结果,那么具有这种特性的是单项三列函数,但是对不起。
22:11
没有完美散列函数的输入和输出不是唯一的对应关系,如果两个散列值相同,两个数值很可能相同,在数值哈西扣的也一样,再去算那个坑位就有可能干嘛碰撞了,所以这种就叫散裂碰撞哈西。来存储大数据量的时候,空间效率还是很低的,但只有几个一个哈希函数的时候,还是很容易发生哈希碰撞的,所以我们一般会用多个。好,那么接下来我们用Java代码来给大家演示一下。那么作为一个Java程序员,你是需要能够写一个什么哈冲突的案例的啊,那么同学们我们假设啊,这个呢叫AA点哈code来,那么这个叫BB,好,同学们看一眼两个对象AABB,绝对绝对是不同的两个对象,它们两个是不是应该碰撞出不同的哈西编码,相当于两个不同的人,他们的身份证号不应该呀,不应该一样,同学们再来看哈扣的。
23:12
Lawyer这个时候啊,我们来个最经典啊,首先大家都清楚哈西code呢是谁的?是我们三我不这个对象里面的原生方法,说祖宗类的方法对吧?那么同学们请看native好,那么对于我们字符串,那么弟兄们lawyer他呢,复习了一下,那么这个呢,我们在加上基础篇都讲过,好不废话,那么来同学们。我直接呢测试类模拟哈希冲突,AA和BB这两个肯定不会冲突,因为一个叫2080,一个叫2112,杨哥这不废话,可问题是大家请看。第二步。不一样了吧?那么此时同学们我们来运行一下,来看看它的效果是什么。
24:01
什么鬼?2112 2112,请问这个是不是两个不同的字符串对象?绝对大大小写的,不用我解释吧,现在告诉我是不是对象不一样,但是哈希冲突出现了,它的哈希值一样,在取模了以后,可能存到比特map布隆过滤器里面的,是不是就是两个记录共用的同一个坑位,你删2112,你以为你要把bbb删掉了,是删掉了,但是可能连坐把AA也给我干掉了。好,那么如果还是觉得不了解的,那么来吧。这个叫柳柴对吧,那么来吧,没问题吧,姓柳的一个,那么这个叫柴帽,按照我们中国人的姓氏,一个姓刘,一个姓柴,100%是牛马不相干的两个姓,对不对?来吧。
25:01
弟兄们如何?是不是又是哈希中通了啊?各位亲,如何?那么这样的话明白了吧,有可能是不同的记录,同样的一系列的哈希,碰撞了以后,占了同样的坑位,所以这就是布隆过滤器不完美的地方。那么再来干个狠事,那么弟兄们,哈希赛特。秒懂,那接下来啊,弟兄们,我们呢,一不做二不休,In哈西扣,那么这我定义这个变量,我干了一件什么事呢?因为你可能在时说杨哥这个都是这个字符串,嗯,他的哈code被复写过了。OK,好,为了满足大家的这个挑剔的眼光,我们这new object.code跟我讲。
26:03
这个总可以了吧,那么好,这个哈,Code搁到这,弟兄们,这个是我用了new object哈,Code最底层的原生方法,Native的,学过GVM的native归Java程序员管吗?我们解决不了,它是系统分配的第三方函数,好,我每有一个对象。就要出一个哈code,那么正常而言,是不是应该每有一个对象它的哈code是不一样的,对吧?好,那么接下来呢,我们干一件什么事呢?负循环每次来判断,如果我们的set里面container这个哈code了,那说明什么?来吧,运行到第几次。加这个I弟兄们可以吧,出现哈希值冲突,那么这个哈希扣着,那么来弟兄们是多少OK,然后continue,否则的话,每一个哈希你给我丢进去,放到我们的哈希里面,OK,好,那么同学们搞到这,为了好看一点啊,我们做一下小小小的分割,来吧,跑一下这个测试类,同学们搂一下20万次,我溜了20万个对象啊。
27:36
好了,我们弟兄们搂一眼。当我用了20万个object的时候,每个object每个对象都要有个哈code,同学们请看什么鬼,运行到第103993次的时候,我就出现冲突了。多少2134400190,那么也就是说当我们六二十万个对象的时候,12345678,以我JAVA8版本为例,当我们用20万次,基本上会出现八次的哈希冲突。
28:10
所以只要你用哈希函数结合我们的布隆过滤器比特map里面的动动,那么这个时候咱们是不是20万个里面会有八次的误判,哎,这个准确度。也还是可以的,对吧,好,那么同学们,这个就是我们哈希函数为什么这个哈希冲突不精确的直接原因。了解了布隆过滤器它的底层运行原理和数据结构,那比特位数组加一系列哈希函数,比特数组存的小哈希函数有冲突,所以它为什么有是可能有,无是肯定无所谓的有。多个坑位都是一,我在判断你有,但是这个坑位有可能哈希冲突,会同样一个坑位被多个数据记录共享,所以有是可能有,但是只要有任何一个坑位,一个或多个坑位,只要其中有一个是零,那么没有就肯定没有,OK,好,所以得到这样的结论以后,明白了它的底层原理,我们的使用一般是三个步骤。
29:19
第一个。那么来看一下,它本质上呢,就这么个东东,所以一开始我们就申请这么一个比会的数字,初始化都是零,那么接下来是不是要开始把我们合法的数据,或者你认为是黑名单的数据去占坑位,那么只要符合的,要么放行,要么拒绝。所以来。我们呢,ADD的数据的时候,为了尽量的地址不冲突,会使用多个哈希函数对K进行运算,一个容易冲突那么多个,尽量的把这个数据呢分布的均匀一些,减少哈些冲突,当然啊,绝对避免不了,那么我们会算得一个校标值,然后对位数组长度进行取模的运算,就可以得到一个位置啊,有没有发现有点类似于我们red那个集群里面那个16384个槽位,以后咱们再取模是吧,差不多都剩一个思路,最终就是要得到一个坑位洛。
30:20
那么每个哈希函数都会算到一个不同的位置啊。再把。数组的这个位置都是为一搞定,那么这个时候比如说啊,我们添加了这么一个字符串,WMYSXZ,随便乱写的啊,对字符串进行多次哈希K,好,同学们请看啊,这个呢,也许呢,我调用了三次,它告诉你。这一个关键的数据,它存在了一号坑位,三号坑位,五号坑位,135用三个位置。就像这把。这个门有三把钥匙才能开,三个多钥匙一了才证明我存在过,所以我们的不能过滤器爱的操作可能是一个坑位表示一个记录,也可能是一系列多个哈希函数使用以后,多个坑位表示一个记录。OK,好,那么接下来我们来判断在不在。
31:19
那么当我们艾完了以后,需要查询这个K,先把这个K我们也通过多个哈希函数进行计算,查看对应的位置是否都是一,只要有一个位为零,哎,比如说刚才我们说了1353个红色的坑位都要是一,才代表这个字符,图二出现过,那么只要有一个坑位是零的,对不起,那么说明这个不能过滤器里面这个T。这个字符串根本不存在,所以五是放心大胆的绝对五,但如果这几个位置全都是一呢?那么是135这个坑位,那是不是100%也一定就是这个字符串呢?那么我们只能说极有可能存在,因为这些位置一可能是因为其他的K存在,也会导致不同的值,算出来同样的坑位,也就我们前面说过的还是冲突,那么来吧,历历在目,刚刚讲过的对不对,那么假设。
32:15
我们这个谬的这个对象啊。103.93,你又出来一个对象,然后109940,你又出第二个对象,那么这两个对象100%是两个不同的对象,但是他们却拥有了同样的哈西code有可能放到了同样的一个称位,哎,一个意思,所以啊,我们呢,结合就比如说我们添加了这个字符串,刚才看到了啊,我们呢,掉了三次哈西扣的再取模,然后呢是135这几个位置都是一好,那么此时啊,假设我们在查第二个,那么1EXIST这一个K,它将将好,它算出来的坑位也可能是135,那么这个时候就是误判了,OK,所以这个就是不同的两个K算出来了同样的称位,好,那么这样我相信同学们因为存在哈希冲突导致的误判率,为什么一般我们不能过滤器里面不要删,理由?
33:15
布隆过滤区的误判是指多个输入经过哈希之后。相同的比特位对吧?我这样就无法判断究竟是哪个输入产生的,那因此误判的根源在于相同的比特位上面被多次映射且值为一,OK,那么这种情况就造成了不能过滤器删除问题,会有一些投鼠忌器的顾忌,因为它每一个比特外并不是独占有可能是多个元素共享了某一位,所以直接干掉的话连做不太好,会影响其他元素。OK,好,那么接下来我们来小总结来吧。有,很可能有,极大可能有。无是肯定无,100%无,所以我们使用的时候最好不要让实际元素远大于初始化的,这个不能过滤器B3的数量一次给够,避免它扩容,说白了数组扩容是不是很烦啊?那么第二个当实际元素数量超过出出的数量的时候,应该对波容器重建,也不要再删除啊。
34:21
重新分配一个size更大的过滤器,再将所有历史数据批量的艾进去,OK,用重建代替删除,避免误判。好,那么同学们,这个就是我们不能过滤器的底层原理。
我来说两句