开封网站seo,广州天极科技,wordpress登入可见插件,金华专业网站建设公司一、介绍 Bloom Filter是一个有m bits的bit array#xff0c;每一个bit位都初始化为0。并且定义有k个不同的hash function#xff0c;每个都以uniform random distribution将元素hash到m个不同位置中的一个。n为要添加到bloomfilter里面的元素。p为错误率。所以相关的参数为每一个bit位都初始化为0。并且定义有k个不同的hash function每个都以uniform random distribution将元素hash到m个不同位置中的一个。n为要添加到bloomfilter里面的元素。p为错误率。所以相关的参数为m n k p 二、原理分析
1、插入数据 插入流程 对将要添加的元素执行k种不同的哈希函数每次哈希后得到的结果为bit array的index将每次得到的 bit array 中 index 的位置的bit值设为1 如上图插入了2个元素X和YX的两次hash取模后的值分别为4、9因此4和9位被置成1Y的两次hash取模后的值分别为14和19因此14和19位被置成1。
2、查找数据 查询流程 对将要添加的元素执行k种不同的哈希函数每次哈希后得到的结果为bit array的index将每次得到的 bit array 中 index 的位置对应的bit的值都为1则返回元素可能存在否则返回元素不存在 为什么bit全部为1时元素只是可能存在呢
当然如果情况如上图中只存在XY而且两个元素hash后的值并不重复。那么这种情况就可以确定元素一定存在
但是存在另一种情况。假设我们现在要查询Z元素假设Z元素并不存在。但是正巧经过hash计算出来的位置为9,14。我们很清楚这里的9是属于X元素的14是术语Y元素的。并不存在Z。但是经过hash计算的结果返回值都是1。所以程序认为Z是存在的但实际上Z并不存在此现象称为false positive(不乐观)
3、为什么不能删除数据
BloomFilter中不允许有删除操作因为删除后可能会造成原来存在的元素返回不存在这个是不允许的还是以一个例子说明 上图中刚开始时有元素XY和Z其hash的bit如图中所示当删除X后会把bit 4和9置成0这同时会造成查询Z时报不存在的问题这对于BloomFilter来讲是不能容忍的因为它要么返回绝对不存在要么返回可能存在。
问题BloomFilter中不允许删除的机制会导致其中的无效元素可能会越来越多即实际已经在磁盘删除中的元素但在bloomfilter中还认为可能存在这会造成越来越多的false positive。
三、优缺点分析
1、优点
常用的数据结构如hashmapsetbit array都能用来测试一个元素是否存在于一个集合中相对于这些数据结构BloomFilter有什么方面的优势呢
相比于其它的数据结构布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数O(k)。另外, 散列函数相互之间没有关系方便由硬件并行实现。布隆过滤器不需要存储元素本身在某些对保密要求非常严格的场合有优势。
对于hashmap其本质上是一个指针数组一个指针的开销是sizeof(void *)在64bit的系统上是64个bit如果采用开链法处理冲突的话又需要额外的指针开销而对于BloomFilter来讲返回可能存在的情况中如果允许有1%的错误率的话每个元素大约需要10bit的存储空间整个存储空间的开销大约是hashmap的15%左右数据来自维基百科对于set如果采用hashmap方式实现情况同上如果采用平衡树方式实现一个节点需要一个指针存储数据的位置两个指针指向其子节点因此开销相对于hashmap来讲是更多的对于bit array对于某个元素是否存在先对元素做hash取模定位到具体的bit如果该bit为1则返回元素存在如果该bit为0则返回此元素不存在。可以看出在返回元素存在的时候也是会有误判的如果要获得和BloomFilter相同的误判率则需要比BloomFilter更大的存储空间
布隆过滤器可以表示全集其它任何数据结构都不能
全量存储但是不存储数据本身适合有保密要求的场景空间复杂度为O(m)不会随着元素增加而增加占用空间少插入和查询时间复杂度都是 O(k), 不会随着元素增加而增加远超一般算法。
2、缺点
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加误算率随之增加。但是如果元素数量太少则使用散列表足矣。
另外一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
相对于hashmap和setBloomFilter在返回元素可能存在的情况中有一定的误判率这时候调用者在误判的时候会做一些不必要的工作而对于hashmap和set不会存在误判情况对于bit arrayBloomFilter在插入和查找元素是否存在时需要做多次hash而bit array只需要做一次hash实际上bit array可以看做是BloomFilter的一种特殊情况
在降低误算率方面有不少工作使得出现了很多布隆过滤器的变种。
存在误算率数据越多误算率越高一般情况下无法从过滤器中删除数据二进制数组长度和 hash 函数个数确定过程复杂
四、误算率计算
位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是 在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是 如果我们插入了 n 个元素那么某一位仍然为 “0” 的概率是 该位为 1的概率是 检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中False Positives该概率由以下公式确定 如何使得错误率最小对于给定的m和n当 的时候取值最小。关系如下图所示 五、使用场景
布隆过滤器的巨大用处就是能够迅速判断一个元素是否在一个集合中。因此他主要有如下三个使用场景:
1、去重
网页爬虫对URL的去重避免爬取相同的URL地址
海量数据去重如40亿QQ号去重问题
2、敏感词快速识别
快速识别内容中是否含有敏感信息的场景
如识别垃圾邮件、垃圾短信、不文明发言中的敏感信息
3、防止缓存穿透 缓存穿透当请求数据库中不存在的数据这时候所有的请求都会打到数据库上这种情况就是缓存穿透。如果当请求较多的话这将会严重浪费数据库资源甚至导致数据库假死。 在大多应用中当业务系统中发送一个请求时会先从缓存中查询若缓存中存在则直接返回若返回中不存在则查询数据库。
BloomFilter解决缓存穿透的思路这种技术在缓存之前再加一层屏障里面存储目前数据库中存在的所有key当业务系统有查询请求的时候首先去BloomFilter中查询该key是否存在。若不存在则说明数据库中也不存在该数据因此缓存都不要查了直接返回null。若存在则继续执行后续的流程先前往缓存中查询缓存中没有的话再前往数据库中的查询。
六、JAVA中使用布隆过滤器
1、导包
Guava工具包提供了十分完善的BloomFilter实现。 !-- https://mvnrepository.com/artifact/com.google.guava/guava --dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion27.0.1-jre/version/dependency2、源码分析
这里只分析布隆过滤器构造的过程
BloomFilter.create构造方法的核心参数主要有两个 expectedInsertions(参数n)预期插入数必须为正整数 fpp(参数p)失误率失误率失误数/总次数不指定时默认为0.03 构建后将根据expectedInsertions(参数n)和fpp(参数)p根据最优公式计算出对应的bit位(参数m)和hash算法的个数(参数k) bit集合所需位数(参数m)和哈希函数个数(参数k)的计算方法 /*** 计算出bit集合所需位数* param n 预期数据量* param p 失误率* return m bit集合位数*/static long optimalNumOfBits(long n, double p) {if (p 0) {p Double.MIN_VALUE;}return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));}/*** 计算出hash函数所需个数* param n* param m* return k 哈希函数个数*/static int optimalNumOfHashFunctions(long n, long m) {// (m / n) * log(2), but avoid truncation due to division!return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));}
最后将bit位数据将转为Long数组进行存储这一步叫做map映射 3、测试代码
/*** author GGBOOM* description 布隆过滤器测试* createTime 2022/10/26 17:58*/
public class BloomFilterTest {/*** 测试默认布隆过滤器失误率* size原始数据量 10000* testSize测试数据量 100000* fpp失误率(失误数/测试数据量),未指定时源码默认0.03(百分之3)* bit位数36277*642321728bit约等于0.277M* hash函数数量5*/Testpublic void testBloomFilterDefault() {// 原始数据量int size 10000;BloomFilterCharSequence bloomFilter BloomFilter.create(Funnels.stringFunnel(Charset.forName(utf-8)), size);// 初始化数据for (int m 0; m size; m) {bloomFilter.put( m);}ListInteger list new ArrayList();// 测试数据int testSize 10000;// 以下全为新数据若有判断存在的将视为一次失误添加进listfor (int n size testSize; n size 2 * testSize; n) {if (bloomFilter.mightContain( n)) {list.add(n);}}double errorRate Double.valueOf(list.size()) / testSize;System.out.println(误判率 errorRate);// 误判率0.0312}/*** 测试指定失误率的布隆过滤器* size原始数据量 10000* testSize测试数据量 100000* fpp失误率(失误数/测试数据量),这里指定为0.0001* bit位数94669*646058816bit约等于0.722M* hash函数数量13*/Testpublic void testBloomFilterWithFpp() {// 原始数据量int size 10000;// 失误率double fpp 0.0001;BloomFilterCharSequence bloomFilter BloomFilter.create(Funnels.stringFunnel(Charset.forName(utf-8)), size, fpp);// 初始化数据for (int m 0; m size; m) {bloomFilter.put( m);}ListInteger list new ArrayList();// 测试数据int testSize 10000;// 以下全为新数据若有判断存在的将视为一次失误添加进listfor (int n size testSize; n size 2 * testSize; n) {if (bloomFilter.mightContain( n)) {list.add(n);}}double errorRate Double.valueOf(list.size()) / testSize;System.out.println(误判率 errorRate);// 误判率1.0E-4即0.0001}}七、参考
http://www.doitedu.cn/archives/2662.html
https://zhuanlan.zhihu.com/p/472935179
https://www.jianshu.com/p/a838078413b6
