图⽂解析布隆过滤器⼤⼩的算法公式
⽬录
1. 简介
2. 应⽤场景
2.1 缓存穿透
2.2 判断某个数据是否在海量数据中存在
3. HashMap的问题
4. 理解布隆过滤器
5. 根据布隆过滤器查询元素
6. 可以删除么
7. 如何选择哈希函数个数和布隆过滤器长度
更多应⽤场景
1. 简介
客户端：这个key存在吗？
服务器：不存在/不知道
本质上，布隆过滤器是⼀种数据结构，是⼀种⽐较巧妙的概率型数据结构。它的特点是⾼效地插⼊和查询。但我们要检查⼀个key是否在某个结构中存在时，通过使⽤布隆过滤器，我们可以快速了解到「这个key⼀定不存在或者可能存在」。相⽐于传统的List、Set、Map这些数据结构，它更加⾼效、占⽤的空间也越少，但是它返回的结果是概率性的，是不确切的。
布隆过滤器仅⽤于测试集合中的成员资格。使⽤布隆过滤器的经典⽰例是减少对不存在的密钥的昂贵磁盘（或⽹络）查。正如我们看到的那样，布隆过滤器可以在O（k）恒定时间内搜索密钥，其中k是哈希函数的数量，测试密钥的不存在将⾮常快。
2. 应⽤场景
2.1 缓存穿透
为了提⾼访问效率，我们会将⼀些数据放在Redis缓存中。当进⾏数据查询时，可以先从缓存中获取数据，⽆需读取数据库。这样可以有效地提升性能。
在数据查询时，⾸先要判断缓存中是否有数据，如果有数据，就直接从缓存中获取数据。
但如果没有数据，就需要从数据库中获取数据，然后放⼊缓存。如果⼤量访问都⽆法命中缓存，会造成数据库要扛较⼤压⼒，从⽽导致数据库崩溃。⽽使⽤布隆过滤器，当访问不存在的缓存时，可以迅速返回避免缓存或者DB crash。
2.2 判断某个数据是否在海量数据中存在
HBase中存储着⾮常海量数据，要判断某个ROWKEYS、或者某个列是否存在，使⽤布隆过滤器，可以快速获取某个数据是否存在。但有⼀定的误判率。但如果某个key不存在，⼀定是准确的。
3. HashMap的问题
要判断某个元素是否存在其实⽤HashMap效率是⾮常⾼的。HashMap通过把值映射为HashMap的Key，这种⽅式可以实现
O(1)常数级时间复杂度。
但是，如果存储的数据量⾮常⼤的时候（例如：上亿的数据），HashMap将会耗费⾮常⼤的内存⼤⼩。⽽且也根本⽆法⼀次性将海量的数据读进内存。
4. 理解布隆过滤器
⼯作原理图：
布隆过滤器是⼀个bit数组或者称为⼀个bit⼆进制向量
这个数组中的元素存的要么是0、要么是1
k个hash函数都是彼此独⽴的，并将每个hash函数计算后的结果对数组的长度m取模，并将对⼀个的bit设置为1（蓝⾊单元格）
我们将每个key都按照这种⽅式设置单元格，就是「布隆过滤器」
5. 根据布隆过滤器查询元素
假设输⼊⼀个key，我们使⽤之前的k个hash函数求哈希，得到k个值
判断这k个值是否都为蓝⾊，如果有⼀个不是蓝⾊，那么这个key⼀定不存在
如果都有蓝⾊，那么key是可能存在（布隆过滤器会存在误判）
因为如果输⼊对象很多，⽽集合⽐较⼩的情况，会导致集合中⼤多位置都会被描蓝，那么检查某个key时候为蓝⾊时，刚好某个位置正好被设置为蓝⾊了，此时，会错误认为该key在集合中
⽰例：
6. 可以删除么
传统的布隆过滤器并不⽀持删除操作。但是名为 Counting Bloom filter 的变种可以⽤来测试元素计数个数是否绝对⼩于某个阈值，它⽀持元素删除。详细理解可以参考⽂章Counting Bloom Filter 的原理和实现，写的很详细。
7. 如何选择哈希函数个数和布隆过滤器长度
很显然，过⼩的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的⽬的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越⼩。
另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变⾼。
从上图可以看出，增加哈希函数k的数量将⼤⼤降低错误率p。
好像是WTF？不⽤担⼼，实际上我们实际上需要确定我们的m和k。因此，如果我们⾃⼰设置容错值p和元素数n，则可以使⽤以下公式来计算这些参数：
我们可以根据过滤器的⼤⼩m，哈希函数的数量k和插⼊的元素的数量n来计算误报率p，公式如下：由上⾯，⼜怎么选择适合业务的 k 和 m 值呢？
hbase为什么查询快公式：
k 为哈希函数个数，m 为布隆过滤器长度，n 为插⼊的元素个数，p 为误报率。
⾄于如何推导这个公式，我在知乎发布的⽂章有涉及，感兴趣可以看看，不感兴趣的话记住上⾯这个公式就⾏了。
我还要在这⾥提到另⼀个重要的观点。由于使⽤Bloom筛选器的唯⼀⽬的是搜索速度更快，所以我们不能使⽤慢速哈希函数，对吗？加密散列函数（例如Sha-1，MD5）对于bloom过滤器不是⼀个好选择，因为它们有点慢。因此，从更快的哈希函数实现中更好的选择是murmur，fnv系列哈希，Jenkins哈希和HashMix。
更多应⽤场景
在给定的⽰例中您已经看到，我们可以使⽤它来警告⽤户输⼊弱密码。
您可以使⽤布隆过滤器，以防⽌⽤户从访问恶意⽹站。
您可以先使⽤Bloom Bloom筛选器进⾏廉价的查检查，⽽不⽤查询SQL数据库来检查是否存在具有特定电⼦邮件的⽤户。如果电⼦邮件不存在，那就太好了！如果确实存在，则可能必须对数据库进⾏额外的查询。您也可以执⾏同样的操作来搜索“⽤户名已被占⽤”。
您可以根据⽹站访问者的IP地址保留⼀个Bloom过滤器，以检查您⽹站的⽤户是“回头⽤户”还是“新⽤户”。“回头⽤户”的⼀些误报不会伤害您，对吗？
您也可以通过使⽤Bloom过滤器跟踪词典单词来进⾏拼写检查。
以上就是布隆过滤器算法图⽂详解的详细内容，更多关于布隆过滤器算法的资料请关注其它相关⽂章！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。