Java 布隆过滤器

你在么？在！一定在么？不在！一定不在么？

你想要100%的准去性，还是99%的准确性附带较高的速度和较小的资源消耗。

任何算法，任何经营收到的背后，都是时间效益 资源消耗 准确性的平衡（1天的时间 10元的投入 生产10个单位的产品，还是 0.6天的时间 6元的投入 生产9个单位的产品）

存在即合理，只是在不同场景下的不同选择。

布隆过滤器

百度百科​布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向
量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的
优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难

维基百科A Bloom filter is a space-efficient probabilistic data structure, conceivedby Burton Howard Bloom in 1970, that is used to test whether an element is 
a member of a set. False positive matches are possible, but false negatives 
are not, thus a Bloom filter has a 100% recall rate. In other words, a queryreturns either “possibly in set” or “definitely not in set”.空间效率高的概率型数据结构，用来检查一个元素是否在一个集合中。
对于一个元素检测是否存在的调用，BloomFilter会告诉调用者两个结果之一：
可能存在或者一定不存在。

用途

        存值，与set map类似（set map 存储大量数据时浪费空间）。

        校验值是否存在（不存在一定不存在，存在可能不一定存在【有一定误差】）。

原理

存值：

k = m/n * ln2 【m是数组长度，n是插入的元素个数，k是hash函数的个数】

假设想要将“张三”放入数组中，经计算k=3的情况，大体存储如下图。

 

校验：

1.同样的k值计算，获取hash函数个数，计算落点位置。

2.逐个落点校验，每个落点位置都标记为1则元素可能存在，只要有一个落点标记为0则不存在。

看到这大家是不是一下子明白的啥叫没有就是没有哈。