1. 引入
布隆过滤器主要作用就是用来解决 "黑名单系统" 或者 "爬虫去重问题" 之类的问题。
我们以黑名单系统举例，比方说，现在有1000万个URL组成的大文件，这些URL都是黑名单，每个URL最大64字节，公司不希望用户在使用我们开发的浏览器服务的时候能够访问它们。
因此，我们需要构建一个黑名单系统，该系统使用一种数据结构能够将大文件中所有URL组织起来，并且能够快速查询。当用户输入一个URL要去访问时，我们能够通过查询该数据结构快速判断该URL是否在黑名单中。 该数据结构没有删除某个黑名单的需求，只有将某个URL加入黑名单和查询某个URL是否在黑名单中这两个重点需求。
经典解决方案就是构建一个HashSet，将1000万个URL全部存入HashSet，总共占用内存空间6亿4000万字节，约5GB，内存的空间开销将会非常大。
如果使用布隆过滤器实现该系统，将会极大减少内存的开销，但是将会出现一定概率的失误。
布隆过滤器专门用来替代内存中存储大量数据的集合，且该集合只有增和查的需求，没有删除的需求。布隆过滤器只占用很小的内存空间，但是会有一定概率出现失误，且失误无法避免。
失误有两种：
- 在黑名单中的URL被判断成白名单。
- 不在黑名单中的URL被判断成黑名单。
布隆过滤器不会出现第一种失误，只可能会有第二种类型的失误。但是布隆过滤器可以通过人为的设计，让第二种类型失误的触发率很低，低到万分之一。
布隆过滤器在工程中是完全能被接收的，即使是极度敏感的黑名单，要求不能误判任何一个黑名单，布隆过滤器也能做到 "即使错杀一百，也不放过一个"，更何况错杀的概率很低。
2. 位图
想要了解布隆过滤器，需要知道什么叫做位图，因为位图不是本文主要要讲的，所以这里就只是简单的讲讲。
位图，又叫 Bit Array 或者 Bit Map。它是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。通过位图我们能够大大的节省空间。
我们都熟悉 Java 中的数组，有int类型的数组int[]，如果初始容量为10，那么int[]会有0~9个单元空间，每一个空间占4个字节。那就相当于申请了一个 320 个bit 位的数组。
我们知道Java中，内存是按照字节计算的，而位图的占用空间是按照bit来计算的，那么我们在Java中如何实现一个位图呢？
使用基础类型数组来拼凑，意思就是可以使用基础类型来保存bit的整体信息，然后通过位运算来操作每一个bit。
容量为10的int类型数组可以表示容量为320的bit类型数组。
int[] arr = new int[10]
arr[0]，arr[1]，arr[2] ... 都是独立的数字，如果把每一个数字每一位拆开来看，arr[0] 能表示 0~31 bit，arr[1] 能表示 32 ~ 63 bit ... 以此类推。
现在需要获取第178 bit的信息，如果是1返回整数1，如果是0返回整数0，那么该如何获取？
// 定位第178 bit在int[]中的哪一个单元空间int numIndex = 178 / 32; // 定位该单元空间中的哪一个bitint bitIndex = 178 % 32; // 获取该bit上的状态int status = (arr[numIndex] >> bitIndex) & 1;
如果我们要修改第178 bit的信息，如何修改？
// 将第178bit改成1 并保存arr[numIndex] = (1 << bitIndex) | arr[numIndex]; // 将第178bit改成0 并保存arr[numIndex] = (~(1 << bitIndex)) & arr[numIndex];
3. 设计思想
布隆过滤器就是一个大位图，容量为m的bit[]，实际占用空间为m/8字节。
往布隆过滤器中添加第一个黑名单URL1，那么URL1会先被哈希函数1计算所得结果out1，再将out1%m，就可以算出一个0~(m-1)的数字，这样就可以对应到bit[]中的某一个单元空间，将该位bit置1；然后URL1再被哈希函数2计算所得结果out2，再将out2%m，又可以对应的bit[]中的某一个单元空间，将该位bit置1 ... 以此类推，假设有K个哈希函数，URL1就会去依次调用K个哈希函数，得到K个out，模完m后对应到bit[]中K个单元空间，将K位bit置1（有可能单元空间有重叠，重叠的bit保持1，也有可能K个单元空间都独立不相同）。当K个哈希函数都调用完，URL1就算存入布隆过滤器中了。
URL2、URL3 ... URL1000万以此类推，每一个URL都需要调用K个哈希函数，得到K个out，模完m后对应到bit[]中K个单元空间，将K位bit置1。
现在有一个URL，需要在布隆过滤器中查找该URL是否是黑名单，那么该URL需要调用K个哈希函数，得到K个out，摸完m后对应到bit[]中K个单元空间，如果所有位bit都是1，那么说明该URL是黑名单；只要有1位bit不是1，那么说明该URL是白名单。
这里有两个参数是不确定的：
- K个哈希函数到底设置多少个？
- 位图容量m到底开多大？（小了可能失误，大了浪费）
为什么在这个问题中布隆过滤器中不会出现 "黑名单误判成白名单" 这种失误呢？
机制决定的，如果该URL是黑名单，那么在查的时候，可以保证该URL对应的bit位必然全都是1。
为什么在这个问题中布隆过滤器中会出现 "白名单误判成黑名单" 这种失误呢？
如果容量m定的很小，URL数量又很多，那么每一位bit必然会出现大量重叠，最终每一位bit都是1，就必然会出现误判。
什么决定失误率？
最重要的因素就是位图的容量m，如果m很大，那么失误率就能压的很小；如果m很小，失误率就会上升，最高可能高达100%。
哈希函数的个数K是什么地位？
K实际上是根据位图容量m和样本量共同决定的。k 太少失误率高，k大了也同样会让失误率增大（因为根据每个元素都要多算出来很多个位置要置为1，那位图都快全是1了，失误率能不高吗）。
m和K的确定流程是什么？
先根据样本量n和失误率P先确定位图容量m，然后再根据样本量n、失误率P和位图容量m计算出一个最合适的哈希函数个数K。
在样本量n确定的情况下，随着位图容量m的增长，失误率P逐渐下降，但是下降速度会越来越缓慢。根据预期的失误率，可以选择一个较为合适的位图容量m = v。
在样本量n和位图容量m都确定的情况下，随着哈希函数个数K的增长，失误率P逐渐下降，但是当K很大时，m也会被逐渐填满，失误率P最终会逐渐上升，最终逼近到1。因此我们能够找到失误率P下降和回升的临界点，该点对应的k值就是最合适的哈希函数个数。
4. 具体实现
判断一个系统是否需要使用布隆过滤器来设计的标准：
- 确定模型，类似于黑名单业务这样的系统，并且系统中没有删除业务。
- 该系统允许有一定的失误，并且有一个明确的预期失误率。
如果聊到系统中要存很多啥，数据量很大，且是类似与黑名单或者爬虫去重这样的，就问问是否允许失误率，如果允许，那就是用布隆过滤器
单样本的大小和设计布隆过滤器没有一点关系，不会决定布隆过滤设计的任何细节，例如上述例子中 "每个URL最大占64字节"。只要我设置的哈希函数可以接收64字节的URL作为参数，并能够对其进行计算就可以了。
设计布隆过滤器只需要以下三个公式：
公式一和公式二计算出来的是理论位图容量m和理论哈希函数个数K，在实际生产中会做出相应调整。
比如理论位图计算出来容量m=26G，实际上可能会给m‘分配32G，这样实际失误率P’就会比理论失误率P进一步降低。
如果要计算实际失误率P’，需要使用先使用公式一和公式二计算出m和K，再使用公式三：
如果算出来k为好多个，那哪来那么多哈希函数给我们呢？
- 用已知的哈希函数自己造。如：有 f1、f2 两个哈希函数，可以 1 * f1 + f2 、 2 * f1 + f2……
