起因

周会组内有一位同事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的布隆过滤器，那么它在内存中的表示就如下所示：

那么这里就是一个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的认同)。

最后

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