一道算法题引发布隆过滤器原理的思考
发布于 3 年前 作者 zy445566 3030 次浏览 来自 分享

起因

周会组内有一位同事L分享了一道算法题,题目是这样的:

A 文件有 50 亿条 URL,B 文件也有 50 亿条 URL,每条 URL 大小为 64B,在一台只有 4G 内存的机器上,怎么找出 A、B 中相同的 URL?

我当时脱口而出,这用布隆过滤器不就好了。

同事L看起来并没有太理会我的答案转而听取分治类的答案。我心想看看你有啥比我更好的答案,嘿嘿嘿!(安静做只腹黑猫🐱)

后来同事L,公布答案是这样的:

50 亿条 URL 文件的大小:50 * 10^8 * 64 Byte ≈ 32 * 10^10 Byte ≈ 320G

首先遍历 A 文件(注意逐行读取)

对每个 URL 取 hash(url)%1000 的值,该值就是 URL 要存储到小文件的编号,最终所有 URL 分别存储在 1000 个小文件中,文件名记成以下形式: a0、a1、…、a999

再遍历 B 文件,用同样的方法将 B 文件的 URL 分别存储在 b0、b1、…、b999 这 1000 个小文件中。

我们知道 Hash 的一个特点:相同的 key,hash 之后的 value 一定是相同的。所以,对于 A、B 文件中相同的 URL,Hash 之后,一定会存储到相同下标的文件中。

如果 Hash 函数设计合理,将数据均匀分散,每个文件大致 300M。

这时我坐不住了,我说这个方案那还不如使用布隆过滤器啊!

这时同事L发问,那啥是布隆过滤器?给我解释解释呗?

其他同事眼睛瞪的像铜铃(没错就是黑猫警长),似乎很想知道啥是布隆过滤器。。。

啥是布隆过滤器?

关于布隆过滤器的最小例子

大家知道计算机世界是由0和1组成的,那么储存0或1的数据的最小单元是位(bit)。那么布隆过滤器要初始化其实就是初始化N个bit的内存块。那么假设我们要初始化一个长度为11的布隆过滤器,那么它在内存中的表示就如下所示:

地址0 地址1 地址2 地址3 地址4 地址5 地址6 地址7 地址8 地址9 地址10
0 0 0 0 0 0 0 0 0 0 0

那么这里就是一个11bit的布隆过滤器了,当我们要找出10以下数组中的相同的值,那么是不是可以直接对11取模。比如我们要找出下列数组中相同的值。

[0, 1, 2, 2, 9]

那么首先是0%11=0,那么我们直接把地址0的0标记成1.

接下来是1%11=1,那么我们直接把地址1的0标记成1.

接下来是2%11=2,那么我们直接把地址2的0标记成1.

接下来是2%11=2,那么我们这时候发现地址2已经是1了,我们就直接把2存储起来,因为找到相同的数据了.

接下来是9%11=9,那么我们直接把地址9的0标记成1.

根据上面的逻辑,我们很轻松就找到相同的那个数2.

那么万一数据大怎么办?

布隆过滤器就是为大数据而生的,我给你算笔账:

1 byte = 8 bit 
1 MB = 1024*1024*8 bit
1GB = 1024*1024*1024*8 bit

也就是说1MB的内存就能有8百万的bit,1GB就有80亿的bit。

那么回到我们的问题,我们只需要2GB内存就能创造160亿长度的布隆过滤器。

那么我们找2个50亿文件中相同的url就非常好解决了,找一个100亿左右的素数作为布隆过滤器的长度,计算每个url的hash值之后再对布隆过滤器的长度取模,如果发现布隆过滤器标记成1的数据,就可以几乎认定相同即可,这样只要遍历一遍且花费2GB不到的内存空间即可。当然碰撞概率是存在的,所以还需要考虑容忍度问题。

说罢,同事响起了雷鸣般的掌声(好吧,这个掌声是我脑补的,当时除了我一个人很激烈的说话,整体还是略显平淡,不过最终还是取得了同事L的认同)。

最后

由于同事看了一些网上关于布隆过滤器的文章感觉不是很好理解,所以正好遇到了这样有意思的分享后,所以本人决定重新理一理布隆过滤器的原理给大家,希望这篇科普文能够更好的帮助理解布隆过滤器,谢谢大家。

6 回复

其实就是把hash值当成“位”地址存一个bool数据,通常我们都是用的字节地址,这种情况下字节地址不够用 由于hash是有碰撞概率的,要降低这种概率可以用不同的hash算法做多次比对,但这也不能完全避免 如果这是面试题,那么面试官100%会苛刻地追问就要100%可靠,这时候你同事L就高兴了😂

布隆过滤器 这种不是只能判断一定不存在的情况的么。
就像楼上说的,不一定准确的呀。😂 还是得看场景。这面试题整的害怕呀

@zengming00 @zhangxh1023 科普文,果断是不能深究了,其目的仅仅是了解布隆过滤器而已,要100%也是有100%的方法

如果不限制硬盘大小,原来那个办法是通用的,50亿变成500亿也没问题,无非是多拆分几个hash桶,但是你那个方法是有上限的,要求构造的位数组长度不能超过4G内存的限制,业务上很多时候需要的是通解,防止以后的扩容同样办法也能无缝升级上去 :),而面试可能更需要下面这种特解吧

@hyj1991 嗯,为面试👏

回到顶部