布隆过滤器（Bloom Filter）由布隆于 1970 年提出，它实际上由一个很长的二进制向量和一系列随机映射函数组成。布隆过滤器可以用于查询一个元素是否在一个集合中，它的优点是空间和时间效率都远超一般的算法，缺点是会有一定的误判。
如果某个数被判定存在布隆过滤器，那么这个数不一定存在布隆过滤器，也就是说这个数可能存在也有可能不存在。
如果某个数被判定不存在布隆过滤器，那么这个数肯定不存在布隆过滤器。
布隆过滤器相比位图(Bit Map)来说，更节省空间，是对位图的一种改进。
布隆过滤器有很多实现，比如Java中的BitSet类，Redis提供了BitMap类，Google的Guava工具包也提供了BloomFilter的实现。
m为bit数组的位数，即一个Bit Vector，位数为m。
n为 存储在布隆过滤器中的元素个数。
k为hash函数的个数。
缺点是有一定的误差率，关于如何计算误差率这里不再赘述，请查看参考文献中的2和3 ，下图：
参考文献：
- https://en.wikipedia.org/wiki/Bloom_filter wiki百科中的BloomFilter解释
- http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html 威斯康星大学麦迪逊分校对布隆过滤器计算和分析
3.https://hur.st/bloomfilter/?n=8000&p=&m=30&k=6 布隆过滤器的实时计算器
本文转载自: https://blog.csdn.net/u010566813/article/details/122155197
版权归原作者 Penguinbupt 所有， 如有侵权，请联系我们删除。
版权归原作者 Penguinbupt 所有， 如有侵权，请联系我们删除。