漫画:15 张图,帮你看懂布隆算法

用户头像
Java小咖秀
关注
发布于: 2020 年 06 月 30 日
漫画:15张图,帮你看懂布隆算法

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



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



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



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



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



image





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





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



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



微信搜索:【Java小咖秀】关注我吧,专注Java以及相关领域,更多精彩等着您~





发布于: 2020 年 06 月 30 日 阅读数: 1228
用户头像

Java小咖秀

关注

公众号:Java小咖秀,专注Java相关领域。 2020.06.18 加入

公众号【Java小咖秀】,回复“面试”白嫖一份博主Java面试题。 个人网站:https://www.javaxks.com。

评论 (3 条评论)

发布
用户头像
布隆是LOL滴英雄呀 你个假粉丝
2020 年 09 月 04 日 15:42
回复
用户头像
位图说得很清晰,学习了,学习了
2020 年 07 月 01 日 09:26
回复
用户头像
插图可爱~
2020 年 06 月 30 日 11:37
回复
没有更多了
漫画:15张图,帮你看懂布隆算法