① 布隆过滤器详解
布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。
通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为 ， ， 。
这个时候，布隆过滤器（Bloom Filter）就应运而生。
了解布隆过滤器原理之前，先回顾下 Hash 函数原理。
哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：
所有散列函数都有如下基本特性：
但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。
BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。
在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：
当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。
查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了
为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。
在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。
如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。
布隆过滤器的典型应用有：
知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器
分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。
当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。
Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。
Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。
在已安装 Redis 的前提下，安装 RedisBloom，有两种方式
直接编译进行安装
使用Docker进行安装
使用
布隆过滤器基本指令：
我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。
上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。
Redis 还提供了自定义参数的布隆过滤器， bf.reserve 过滤器名 error_rate initial_size
但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错
我是一名 Javaer，肯定还要用 Java 来实现的，Java 的 Redis 客户端比较多，有些还没有提供指令扩展机制，笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson
为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。
由于使用较少，暂不深入。
https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf
http://www.justdojava.com/2019/10/22/bloomfilter/
https://www.cnblogs.com/cpselvis/p/6265825.html
https://juejin.im/post/5cc5aa7ce51d456e431adac5
② 垃圾短信邮件判断算法
垃圾短信，垃圾邮件和推销的电话使我们深受其扰，不过也有些手机软件助手，可以帮助我们垃圾这些垃圾短信和电话，这些软件的背后的算法是什么？
像360手机卫士这种APP在手机本地或云端保存一份电话的手机黑名单数据，来电的时候手机判断下就可以决定是否为骚扰电话了，本地存储，黑名单的数据量如果很大的话，可能会占内存比较大，不过这个可以借鉴以前的布隆过滤器这种数据结构来解决，但是布隆过滤器有误判的可能，有可能来电非黑名单却当成黑名单进行处理了，这对于拦截软件来说是比较严重的问题，所以可能是多种方法来结合判断，或者对于布隆过滤判断是属于黑名单的电话，再通过一次联网到网上的云端再判断一次是否为真正为黑名单用户，不过这就需要联网，还存在延迟的可能；对于布隆过滤器判断为正常用户的，则一定是正常用户，那么大部分时间是不需要联网判断或结合其他办法判断的。
像很多病毒检测软件，或IDS或WAF软件一样，垃圾短信和骚扰电话 也可以建立自己的规则库，通过规则库进行垃圾短信的判断，同样像IDS等软件存在误判的情况一样，垃圾短信采用规则判断的话，也存在一定的误判性，一般也要结合其他的判断规则综合判断。
规则有下面几个：
凡是规则判断，都存在着检测死板，不能检测到不在规则里面的情况，而且会被有心者特意设计避开规则的垃圾短信等。
直观地想一下，垃圾短信，垃圾邮件这些一般都包含特定的词语，或者链接等，那么我们反过来统计邮件中特定的词语的数量，达到一定标准，我们就判断为垃圾邮件。
现在对于这种垃圾邮件的判断问题，一般都通过机器学习来解决，在机器学习的算法中，做垃圾邮件判断这个是属于一个二分类问题，可以用很多中算法来解决，常用的有决策树，贝叶斯，SVM，神经网络等，其中贝叶斯算法是属于一个基于统计学的算法，也是本次要介绍的算法。
贝叶斯算法是为了解决“逆序概率”的问题，举个简单的例子，比如我们袋子中有10个红球，8个白球，然后随机从袋子中拿出一个球，问是红球的概率是多少？这是一个非常简单的概率问题，结果就是10/(10+8),这种正向概率问题比较好理解。那么反过来，如果我们只知道袋子中有红球和白球，但是不知道数量和比例，我们拿了几次球，通过拿出这些球的颜色是否可以推断出袋子中两种球的比例那？
贝叶斯算法中有些根据以前经验总结出来的概率，称为先验概率，可以理解成先前的经验的概率，所以叫先验概率，比如清明时节一般会下雨，下雨的概率大概为70%，这就是通过以前的经验总结的；
后验概率， 是事情发生了，推测可能原因，比如小明迟到了，那么起晚了造成迟到的概率假设为30%，这就是后验概率。条件概率，就是在一个事情假设A发生的情况下，另外一个事情B也发生的概率，记作P(B|A),读作在A发生的情况下，B发生的概率，比如起晚的情况下，小明迟到的概率。
总结一句话：先验概率是经验总结，后验概率是由果推因，条件概率是由因推果。
根据条件概率的定义，可以推导出贝叶斯公式，推导过程在网络里面如下：
说明：
1）P(A|B) = A和B同时发生的概率/B发生的概率，直观想下，B发生的概率一定大于A和B同时发生的概率，相除的含义就是在B发生的概率情况下，有多少A也同时发生的概率，也就符合了条件概率的定义。
2）把除法变乘法就得到了合并后的式子，再变化下，就得到了贝叶斯公式。
可能还比较抽象,举个wiki上的例子：
我们用两种算法进行计算，一是自己直观想，二是用朴素贝叶斯。
假设学校一共有U个人，直观想法计算：
P(是女生|穿裤子） = 所有穿裤子的女生数量/所有穿裤子的人数
= U*0.4（女生数量）*0.5（一半穿裤子） / (U*0.4*0.5 +U*0.6*1)
= 0.2*U /0.8*U = 25%
如果用朴素贝叶斯算法：
P(是女生|穿裤子) = P(穿裤子|是女生) *P(是女生)/P(穿裤子)
= 0.5*0.4/[(0.6*1 +0.4*0.5）/1]
= 0.2 /0.8
= 25%
说明： P(穿裤子） = 穿裤子人数/总人数= U*0.6*1 + U*0.4*0.5/U = 80%
这样看起来，朴素贝叶斯公式也不是很难。
具体来看下垃圾邮件的分类问题：我们用D表示一封邮件，D是由很多单词组成。用f+表示是垃圾邮件，用f-表示是正常邮件，根据贝叶斯公式，问题形式化：
其中P(f+)和P(f-)比较容易得到，算下一个邮箱里面有多少个是垃圾邮件，多少个是正常邮件即可，不过最好多找几个，算下平均值，这就是所谓的先验概率。
P(D|f+) 表示是垃圾邮件，单词出现的概率，把D展开成N个单词就是:
P(d1,d2,d3...dn|f+) 即垃圾邮件中，同时出现这些单词的概率，这个没办法求，假设这些单词之间是独立的，没有什么关联关系，那么P(d1,d2,d3...dn|f+) 就可以扩展为P(d1|f+)* P(d2|f+) P(d3|f+).... P(dn|f+) 这个里面的独立假设，就是朴素贝叶斯的朴素来源，因为不是那么精确，所以叫朴素。计算一个单词在垃圾邮件中出现的概率就比较简单了。
翻译一下：
P(垃圾邮件|单词d1，单词d2...单词dn同时出现） =[ P(单词d1,单词d2...同时出现|是垃圾邮件）*P(是垃圾邮件)]/P(单词d1,单词d2...同时出现在一封邮件里面）
根据独立假设：
P(垃圾邮件|单词d1，单词d2...单词dn同时出现） =[ P(单词d1出现|是垃圾邮件）*P(单词d2出现|是垃圾邮件）*P(单词d3出现|是垃圾邮件）...*P(是垃圾邮件)]/P(单词d1,单词d2...同时出现在一封邮件里面）
其实我们在判断是否是垃圾邮件的时候，并一定要计算出来P(单词d1,单词d2...同时出现在一封邮件里面），这个也无法精确计算，我们只需要比较垃圾邮件的概率和非垃圾邮件的概率，取大的那一个就可以了，那么久只要计算：
P(垃圾邮件|单词d1，单词d2...单词dn同时出现） =[ P(单词d1出现|是垃圾邮件）*P(单词d2出现|是垃圾邮件）*P(单词d3出现|是垃圾邮件）...*P(是垃圾邮件)]
P(正常邮件|单词d1，单词d2...单词dn同时出现） =[ P(单词d1出现|是正常邮件）*P(单词d2出现|是正常邮件）*P(单词d3出现|是正常邮件）...*P(是正常邮件)]
1.找到N封邮件，标记好垃圾邮件和非垃圾邮件。
2.对N封邮件进行去掉停词部分，然后采用分词算法做分词。
3.分别计算每个词在垃圾邮件中出现的比例，在正常邮件中出现的比例
4.带入公式算下哪个概率相对大一些，就属于哪个分类。
这里面总结的比较简单，贝叶斯算法，还有很多没有说到，我也理解的不够深刻，先只聊点这种简单的吧，下一篇将找个例子实战下朴素贝叶斯算法。
参考：
1. 数据结构和算法之美：概率统计
2. 数据分析实战：朴素贝叶斯
3. 平凡而又神奇的贝叶斯方法
③ 布隆过滤器
如果使用哈希表，内存空间需要100亿*64字节=640G(10亿字节（byte）是1G)，空间就爆掉了。此时就轮到布隆过滤器登场了。
布隆过滤器应用场景：黑名单 爬虫去重
布隆过滤器优势：节省内存(30G以内)，查询速度快
布隆过滤器劣势：存在一定失误率
但布隆过滤器的失误率是可以容忍的，一是可以通过设计人为的把失误率控制的很低；二是就算失误了不会误报已经在黑名单里的URL。布隆过滤器只会把正常的URL当成黑名单系统里的，但不会误报已经在黑名单里的URL。形象点说就是“宁可错杀三千不会放过一个”
在讲解布隆过滤器原理之前先讲位图。
位图是bit类型的数组。 int类型4字节即32bit，所以长度100的int类型数组可以看出长度3200的bit数组。假如要找1782位比特，那么在int数组里下标是1782/32，在下标里存的int数字里第几个比特位？即1782%32的计算结果，从而把整型数组操作转换成比特类型数组操作。
布隆过滤器即大位图，假设是长度为m的bit数组，那么占用m/8位字节（Byte）,
URL加黑名单过程：开始时m位比特都是0（白）的状态，该URL通过哈希函数f1得到一个哈希值，然后%m,得到0~m-1上某个位置，将该位置描黑（变成1），再用哈希函数f2得到一个哈希值，再描黑，再用哈希函数f3同样处理（f1、f2、f3是独立的哈希函数），假设一共用了k个哈希函数，那么描黑了k个位置（某个位置重复了就重复了，但一旦描黑就没有描白的时候）完成后可以说该URL加入了位图里。对下一个URL同样处理，用k个哈希函数描黑k个位置……一直做100亿个，位图中有相当多位置被描黑了。
如何查某个URL在不在黑名单里？把待查的URL用K个哈希函数算出对应的哈希值，再把该哈希值%m，把K个位置的状态都拿出来，如果全黑，就说这个URL属于黑名单系统，如果有一个是白，就不属于黑名单系统。如果m很小，100亿个URL之后所有位图都是黑的，那么不论查谁都在黑名单里；如果m取的大一些，失误率就会降低。
但布隆过滤器需要准备多少个bit位和单样本的大小无关。一个URL经过K个哈希函数得到K个哈希值，对m取模后去相应的大比特map中描黑，只要保证哈希函数能接收单样本这种类型的参数就可以了，与样本是64字节还是128字节无关。所以影响失误率的重要参数就是样本量N和位图比特数组长度m。
布隆过滤器三公式： 出处
1.确定m:对于输入的数据量n（这里是100亿）和失误率p（这里是万分之一），布隆过滤器的大小m：m = - (n lnp) / (ln2 ln2)
2.确定K：K假如很少，例如只有一个哈希函数，相当于每个数据只采集了一个特征点，只把一个位置描黑，查的时候也只用一个哈希函数，特征点不够，失误率虽然不至于很高但有一定的量，如果K很大，例如用10万个哈希函数去把10万个位置描黑，m的空间会接近耗尽，查什么URL都是黑的，失误率非常高。需要的哈希函数的个数k：k = ln2 * m/n = 0.7 * m/n
3.因为前两步中公式1公式2都会进行向上取整，所以公式3算出的实际的失误率与比预期失误率要低
布隆过滤器在Hadoop中的应用：Hadoop中的分布式文件系统，是由许多小文件组成的，如何查询一个数据在哪个文件里？首先不可能记录每个小文件的索引，这样做占用空间太大了。所以每个小文件里都搞一个布隆过滤器，当Hadoop想知道某个key在哪个文件里，就查每一个布隆过滤器，文件a的布隆过滤器会说明你这个key在我这个文件里，但可能会有误报；文件c的布隆过滤器会说明你这个key在我这个文件里，但可能会有误报……如果失误率很低，哪怕有几万个分布式文件，最终可能算出来只有3个文件里可能含有这个key。那么就只用把这3个小文件遍历一遍，就知道key在哪个小文件里了。通俗点讲，如果一个文件真的含有key，那么它的布隆过滤器会说这个key属于我；但因为有失误率，可能会发生一个文件不含有这个key，它还是会说这个key属于我；可是这也没关系，多查一遍就可以，反正失误率很低，需要遍历的文件很少。
④ 布隆过滤器
[TOC]
通过解决方案：
Java中如将数据存储在内存中，最简单的算法结构是HashMap。通过HashMap判断key是否存在，来判断数据是否存在。通过hash算法查找元素，时间复杂度基本是 O(1) （可能存在hash冲突后转换成链表或红黑树的情况，时间复杂度的影响可以忽略）。
使用HashMap速度很快，存储简单，绝大部分场景可以使用。但是HashMap 占用的空间比较大 ：
为什么出现布隆过滤器：
举例：
如1000万个Integer存储在内存中，占用空间为：4x32x10000000位，即1220兆。如布隆过滤器通过4字节存储（布隆过滤器通过多次hash对数据计算后-->几次hash根据数据量指定，得到多个数据， 占用多个位 ），则占用空间为610M。比原有空间少一半。
个人觉得，此比较在字符等的比较中尤为有效。
一个字符串多个字符，根据编码方式，一个字符两个或三个字节，如10个字符，字符串存储占用20个字节，还有相关字符串相关的类信息的内存占用。
位存储，根据数据量的大小，hash的位数，灵活计算。如4个字节，则是原hashMap占用空间的五分之一。
（1）定义字节向量
先定义一个指定长度的字节数组（字节数组，数组内每个元素的值）。
如长度为8（一个字节大小），默认所有元素值均为0，如下：
（2）计算哈希值
将要写入过滤器的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。
如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。
（3）更新字节向量
将计算出的字节向量的索引， 对应的字节向量中的元素值更高为1 （无论之前为0或者为1，均更改为1）。如下：
（1）计算哈希值
将要判断过滤器中是否存在的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。
如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。
注意：哈希函数的判断方式和计算索引的方式，需和写入数据时完全一致。
（2）判断是否存在
如原字节数组中，对应1，3，7中存在的元素的值都为1。则判定为此元素 可能存在 ，但凡有一个元素的值不为1，则判定此元素 一定不存在 。
布隆过滤器，主要需实现的目标是， 在指定的数据个数范围内，满足误判率在设定的范围内 ，误判率太高的话，无法起到过滤数据的情况，误判率不能为0。
因此需要计算两个数据来满足 存储数据的个数 和 误判率 ：
使用布隆过滤器的决定性因素之一，就是此算法插入数据和查询数据的速度必须非常快。因此在对数据进行哈希运算的时候， 需选择计算快的哈希算法 。
而且， 写入数据以及查询数据的哈希算法，顺序和算法都需完全一致 。
待完善。。。。。
可以通过google的 guava ，在内存中轻松实现布隆过滤器。
无需手动计算满足字节数组的长度和哈希个数，只需要输入 拟输入数据的个数 和 期望误判率 即可。
不输入期望误判率的情况下，误判率为0.03，即100个非范围内的数据进行校验时，约三个数据会判定为存在。
多次执行，结果一致，根据结果判定：
内存的存储存在局限性，可以使用redis中的bitMap来实现字节数组的存储。
使用redis实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。
实现过程，待完善。。。。。。
⑤ 什么是缓存穿透
缓存穿透又称缓存击穿,是指在高并发场景下缓存中(包括本地缓存和Redis缓存)的某一个Key被高并发的访问没有命中,此时回去数据库中访问数据,导致数据库并发的执行大量查询操作,对DB造成巨大的压力。
⑥ Java通过id访问方法,不让id重复访问怎么实现
就是一个id只能访问一次吗？
1，在调用方法前要有控制
2，判定id是否访问过
比较简单的，比如访问过的id存起来，调用前查一下看看是不是已经有了，有了不允许访问
然后说点逼格高的，
1，用数据库保存已经访问的id，但是数据库会慢一点
2，用缓存保存先过滤一下，不过会越来越大。id不长还是能存很多很多很多的，如果缓存失效再向库里查，万无一失
3，布隆过滤器特别适合你这个，每次id访问过来就加到过滤器里面，后面直接先用布隆过滤器过滤下，性能特别高，误判再往后面缓存数据库走就行
⑦ 布隆过滤器和替代算法
布隆过滤器和替代算法：但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
但是包含查找的数据项的数据文件它一定是会返回的，key-value系统中bloom filter返回的数据文件还是需要查看里面的内容才能知道是否存在所需的数据的，这就保证了执行结果的正确性和完整性。
只是多访问一些数据文件而已。在数据量很大key-value系统中，建立统一的B+树索引的代价是非常大的，维护成本也很高，因此综合起来bloom filter的性能是最好的。
缺点：
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。常见的补救办法是建立一个小的白名单，存储那些可能被误判的元素。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。
⑧ 缓存穿透有哪些解决办法
具体有哪些解决办法？
最基本的就是首先做好参数校验，一些不合法的参数请求直接抛出异常信息返回给客户端。比如查询的数据库 id 不能小于 0、传入的邮箱格式不对的时候直接返回错误消息给客户端等等。
1）缓存无效 key : 如果缓存和数据库都查不到某个 key 的数据就写一个到 redis 中去并设置过期时间，具体命令如下：SET key value EX 10086。这种方式可以解决请求的 key 变化不频繁的情况，如何黑客恶意攻击，每次构建的不同的请求key，会导致 redis 中缓存大量无效的 key 。很明显，这种方案并不能从根本上解决此问题。如果非要用这种方式来解决穿透问题的话，尽量将无效的 key 的过期时间设置短一点比如 1 分钟。另外，一般情况下我们是这样设计 key 的： 表名:列名:主键名:主键值。
2）布隆过滤器：布隆过滤器是一个非常神奇的数据结构，通过它我们可以非常方便地判断一个给定数据是否存在与海量数据中。我们需要的就是判断 key 是否合法，有没有感觉布隆过滤器就是我们想要找的那个“人”。具体是这样做的：把所有可能存在的请求的值都存放在布隆过滤器中，当用户请求过来，我会先判断用户发来的请求的值是否存在于布隆过滤器中。不存在的话，直接返回请求参数错误信息给客户端，存在的话才会走下面的流程。总结一下就是下面这张图(这张图片不是我画的，为了省事直接在网上找的)：
⑨ 如果面试官问你布隆过滤器，你该怎么回答
假设遇到这样一个问题：一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出。
可能很多人首先想到的会是使用 HashSet，因为 HashSet基于 HashMap，理论上时间复杂度为：O(1)。达到了快速的目的，但是空间复杂度呢？URL字符串通过Hash得到一个Integer的值，Integer占4个字节，那20亿个URL理论上需要：20亿*4/1024/1024/1024=7.45G的内存，不满足空间复杂度的要求。
这里就引出本文要介绍的“布隆过滤器”。
网络上对布隆过滤器的介绍是这样的：
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
是不是描述的比较抽象？那就直接了解其原理吧！
还是以上面的例子为例：
哈希算法得出的Integer的哈希值最大为：Integer.MAX_VALUE=2147483647，意思就是任何一个URL的哈希都会在0~2147483647之间。
那么可以定义一个2147483647长度的byte数组，用来存储集合所有可能的值。为了存储这个byte数组，系统只需要：2147483647/8/1024/1024=256M。
比如：某个URL（X）的哈希是2，那么落到这个byte数组在第二位上就是1，这个byte数组将是：000….00000010，重复的，将这20亿个数全部哈希并落到byte数组中。
判断逻辑
如果byte数组上的第二位是1，那么这个URL（X）可能存在。为什么是可能？因为有可能其它URL因哈希碰撞哈希出来的也是2，这就是误判。
但是如果这个byte数组上的第二位是0，那么这个URL（X）就一定不存在集合中。
多次哈希
为了减少因哈希碰撞导致的误判概率，可以对这个URL（X）用不同的哈希算法进行N次哈希，得出N个哈希值，落到这个byte数组上，如果这N个位置没有都为1，那么这个URL（X）就一定不存在集合中。
Guava框架提供了布隆过滤器的具体实现：BloomFilter，使得开发不用再自己写一套算法的实现。
BloomFilter提供了几个重载的静态 create方法来创建实例：
最终还是调用：
真正的byte数组维护在类：BitArray中。
最后通过：put和 mightContain方法，添加元素和判断元素是否存在。
1、因使用哈希判断，时间效率很高。空间效率也是其一大优势。
2、有误判的可能，需针对具体场景使用。
3、因为无法分辨哈希碰撞，所以不是很好做删除操作。
1、黑名单
2、URL去重
3、单词拼写检查
4、Key-Value缓存系统的Key校验
5、ID校验，比如订单系统查询某个订单ID是否存在，如果不存在就直接返回。
⑩ 生日悖论是啥我用它省了上百G的内存
生日悖论 : 是指在不少于 23 个人中至少有两人生日相同的概率大于 50%。例如在一个 30 人的小学班级中，存在两人生日相同的概率为 70%。对于 60 人的大班，这种概率要大于 99%。从引起逻辑矛盾的角度来说，生日悖论并不是一种 “悖论”。但这个数学事实十分反直觉，故称之为一个悖论。
生日悖论是有个有趣的概念，但这和我省上百G的内存有什么关系？
首先介绍下背景，工作中我负责了一个广告数据系统，其中一个功能就是对同一次请求的广告曝光去重，因为我们只需要知道这次请求这个广告的一次曝光就行了，那些同一次请求产生的重复曝光记录下来没有意义，而且还耗会增加我们的存储成本。所以这里就需要有个逻辑去判断每条新到的曝光是否只之前已经记录过的，旧的方案是在redis中存储请求唯一标识(uuid)和广告ID(adid)，每次数据过来我们就看redis里有没有uuid+adid这个key，有就过滤掉，没有就不过滤并在redis记录下来已出现。
问题就来了，redis记录的这份数很大(两天数据超过400G)，而且随着我们业务的增长，我们的Redis集群快盛不下了…… 当然花钱加机器是最简单的方式，毕竟能用钱解决的问题都不是问题。而优秀的我，为了替公司省钱，走了优化的路。
首先可以肯定的是数据条数不会少，因为业务量就在那里，所以减少数据量的这条路肯定行不通。那是否可以减少每条数据的长度呢？
我们再来看下redis存储的设计，如下图：
这里我们用的是随机UUID，这个版本中有效二进制位是122个，所以总共有 个有效的UUID。 因为是随机产生的所以肯定有重复的概率，UUID重复的概率有多少？ 要算这个重复概率，光有 这个总数还不行，还得知道你拥有的UUID个数。 我把这个问题具体下，求：在 个UUID中有重复的概率是多少？
这不就是生日悖论的数据放大版吗？ 当然这个概率可以根据上面公式计算，其中x是UUID的总数 ，n是 ，引用网络的数据，概率为 这比你出门被陨石撞的概率还小很多。
另外，从上面的公式也可以看出，在n固定的时候，随着有效二进制位的减少，概率p就会增加。 回到我们广告去重的场景下，每天最大请求数n是基本固定的，而且我们也可以忍受一个较小的概率p（小于万分之一），然后就可以反推出这个x有多大。
其实只要 ，p就会小于万分之一。我可以从历史数中统计出n的大小，然后计算出x，再留一定的buff，然后根据n的大小重新设计了redis的key。(因为涉及公司数据，这里不公布中间计算过程)
最终有效位我选取了40个有效二进制位(10个16进制位)，但我并没有直接截取UUID的前10位，因为UUID的前几位和时间有关，随机性并不强。我选择将整个UUID重新md5散列，然后截取md5的前10位，然后拼接adId形成最终的key，如下图：
明显看出，key的长度缩小了一半，总体上能节省至少50%的存储空间。备注：但其实我们redis的具体存储实现和上文描述略有差异，为了不喧宾夺主上文特意对实际实现做了简化描述，所以最终实际没有省一半以上的内存，只省了35%左右。
实际优化就到这了，但其实还是不够极致，其实adId中也包含大量的冗余信息也可以截取，其实我们可以承受更高的重复率，其实我们可以把redis数据存储时间设的更短一些……
上面几种方法都可以进一步优化，但存储空间不会有量级级别的减少，而下面一种方式，可以将存储空间减小99%以上。
关于布隆过滤器的原理，可以参考我之前写的一篇文章 布隆过滤器(BloomFilter)原理 实现和性能测试 。 布隆过滤器完全就是为了去重场景设计的，保守估计我们广告去重的场景切到布隆过滤器，至少节省90%的内存。
那为什么我没有用布隆过滤器，其实还是因为实现复杂。redis在4.0后支持模块，其中有人就开发设计了布隆过滤器的模块 RedisBloom ，但无奈我们用的redis 还是3.x版本 ！我也考虑过应用端基于redis去实现布隆过滤器，但我们应用端是个集群，需要解决一些分布式数据一致性的问题，作罢。
其实我们redis的具体存储实现和上文描述略有差异，为了不喧宾夺主上文特意对实际实现做了简化描述，所以最终实际没有省一半以上的内存，只省了35%左右。
最终400G+优化后能减少100多G的内存，其实也就是一台服务器，即便放到未来也就是少扩容几台服务器。对公司而言就是每个月节省几千的成本，我司这种大厂其实是不会在乎这点钱的。不过即便这几千的成本最终不会转化成我的工资或者奖金，但像这种优化该做还是得做。如果每个人都本着 用最低的成本做同样事 的原则去做好每一件事，就我司这体量，一个月上千万的成本还是能省下来的。