假设位数组的大小是m，我们一共有k个hash函数，那么每一个hash函数，进行hash的时候，只能hash到m位中的一个位置，所以没有被hash到的概率是：
$$1-\frac{1}{m}$$
k个hash函数都hash之后，该位还是没有被hash到1的概率是：
$$(1-\frac{1}{m})^k$$
如果我们插入了n个元素，也就是hash了n*k次，该位还是没有被hash成1的概率是：
$$(1-\frac{1}{m})^{kn}$$
那该位为1的概率就是：
$$1-(1-\frac{1}{m})^{kn}$$
如果需要检测某一个元素是不是在集合中，也就是该元素对应的k个hash元素hash出来的值，都需要设置为1。也就是该元素不存在，但是该元素对应的所有位都被hash成为1的概率是：
$${(1-(1-\frac{1}{m}){kn})}{k}\approx {(1-e{-kn/m})}k $$
可以大致看出，随着位数组大小m和hash函数个数的增加，其实概率会下降，随着插入的元素n的增加，概率会有所上升。
最后也可以通过自己期待的误判率P和期待添加的个数n，来大致计算出布隆过滤器的位数组的长度：
$$m=-(\frac{nInP}{(In2)^2})$$
上面就是误判率的大致计算方式，同时也提示我们，可以根据自己业务的数据量以及误判率，来调整我们的数组的大小。
布隆过滤器的作用除了我们前面说的过滤爬虫恶意请求，还可以对一些URL进行去重，过滤海量数据里面的重复数据，过滤数据库里面不存在的id等等。
但是，即使有布隆过滤器，我们也不可能完全避免，或者彻底解决缓存穿透这个问题。只是相当于做了优化，将准确率提高。
很多的key-value数据库也会使用布隆过滤器来加快查询效率，因为全部挨个判断一遍，这个效率太低了。
【刷题笔记】
Github仓库地址：https://github.com/Damaer/codeSolution
笔记地址：https://damaer.github.io/codeSolution/
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
2020年我写了什么？