漫画:高效的布隆算法

x星球经过和y星球的激战后,x星球已经无法居住,重建需要很长的时间,因此迁移到why星球上。

ps: 假设每个人ip代表不同的用户。

ps:一个B代表一个字节,一个字节8位,即8个二进制数,1GB=1024MB=1024*1024KB=1024*1024*1024B。

ps:ip如何转成int类型。每段均为最大值的ip为255.255.255.255,8位正好可以表示一个255大小的数字,因此每8位表示一个数字,ip一共是4段,正好32位。

ps: 255 * 255 * 255 * 255 = 4228250625,4228250625/(1024*1024*8)=504。

ps:f1,f2,f3代表3个不同的hash函数。箭头指向的地方代表通过hash函数计算出的hash值同时也是在位图中的位置。

ps:另外一般情况下不能从布隆过滤器中删除元素,由于有一些字符串计算的hash值可能会相同,此时我们会想到,把每个位置存上对应的次数,删除元素的时候同时减1,前面我们说过会有误判的情况,所以要安全的删掉元素不是这么简单。

end:本文主要讲解布隆过滤器的算法思想,具体的实现我们可以去看guava中的BloomFIlter。

文章转载自公众号 JAVA小咖秀 , 作者 小小小咖

原文发布于微信公众号 - 全菜工程师小辉(mseddl)

原文发表时间:2019-09-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券