redis应用场景---实现布隆过滤器.md

1. 什么是布隆过滤器

在解释布隆过滤器之前，先来看一个具体的例子，如果没有布隆过滤器，这种问题解决起来还是有点费力的。

像百度，谷歌这样的爬虫，每天要爬取数以亿记的网页，如果让你来做这个事情，你会面临一个非常棘手的问题，如何判断一个url是否已经被抓取过了。

假设有10亿的url等待抓取，这里面极可能存在重复的url，你如何存储那些已经被爬取过的url呢？

用mysql? 一张表存储10亿条记录，疯子才会这么做，分表？很麻烦，很费力的操作。

将url缓存到redis中，是一个可行的办法，不过这需要非常大的内存。

怎么办呢？用布隆过滤器。

说起来，布隆过滤器的思路非常简单，我们一点一点的来了解它。

假设有一个长度为n的比特数组，暂且命名为bit_array,数组里的每一位都是0。对于一个url，我使用hash算法计算出url的散列值，这个散列值当然是一个整数，暂且命名为index，让index = index % n ，确保index的值小于n。接下来最重要的一个步骤，查看bit_array[index]的是否等于1，如果等于1，就表示这个url已经被抓取过了，如果等于0，则表示还没有被抓取，让爬虫去抓这个url，同时设置bit_array[index] = 1。

上面说的方法乍看起来挺合理挺好用的，但经不起深究，当url非常多了以后，必然会发生碰撞，即两个不同的url经过hash处理后得到相同的散列值，这就麻烦了，两个url，有一个被误判，明明没有被抓取过，但比特数组里已经记录了它。

如何解决碰撞呢，布隆过滤器的方法很暴力，用多个hash，这样就会产生多个散列值，这些散列值所对应的索引位置均设置为1，虽然依然会发生碰撞，但是这些位置都发生碰撞的概率就降低了。

关于布隆过滤器，有三个影响效果的变量

比特数组的长度
错误率，两个不同的值经过多个hash散列后，还是碰撞在一起的概率
hash的次数

经过一些看不同的高数知识，知道其中的两个变量，就可以计算出第三个，如果你感兴趣，推荐你看这篇文章布隆过滤器(Bloom Filter)详解

布隆过滤器可以视为一个特殊的集合，它不能存储具体的值，它只能表示某个值是否在集合中，而且，它有一定的错误率，布隆过滤器说某个值不存在，那么就一定不存在，说某个值存在，则有一定的概率是错的，这一点务必要牢记，对于一个要爬取数十亿的爬虫，一点点错误遗漏还是可以忍受的，如果你的应用可以忍受一点点错误率，布隆过滤器可以为你带来一个实实在在的好处，节省内存，非常可观的节省。

2. 结合redis来实现布隆过滤器

redis并没有布隆过滤器这种数据结构，常见文章里提到的bitmap也不是redis的数据结构，redis提供了setbit，getbit等命令，但底层只是在操作string这种数据结构，string是可以自动扩容的，因此事先不必为所谓的bitmap分配内存。

布隆过滤器需要对一个值进行多次的hash，有一个叫mmh3的库提供了广泛测试且速度很快的非加密哈希函数，只是安装起来有点麻烦，以下的安装过程是在windows环境下记录的

pip install mmh3

你很可能会遇到错误“Microsoft Visual C++ 14.0 is required” ，解决方法很简单，下载Microsoft Visual C++ Build Tools.exe 并进行安装，下载地址：

链接：https://pan.baidu.com/s/1E4LxPNUImcDO9lHdGtO_Bw 
提取码：gstd 
复制这段内容后打开百度网盘手机App，操作更方便哦