布隆过滤器(Bloom Filter)及CBF 使用及原理浅析

布隆过滤器 原理:

步骤1:在内存中开辟一块连续的空间;将所有bit位置为0; 假如 设置 3个hash函数 将 数据 分别存储在3个bit位上;

步骤2:在有数据(如 'baidu')需要存储时, 将 数据 经过 3个hash函数的计算 得到 3个 bit位置; 然后将对应3个bit位置 数据置位1;

下次判断 数据(如'baidu') 是否存在时,将数据 通过 步骤2 计算后 获取对应bit位置 数据是否 都为1(注意 因为3个hash函数相同,所以相同数据 无论计算多少次 对应bit位置都一样,保证准确性) 即可判断数据是否重复;

作用:

黑名单,缓存穿透 等等 需要判断在大量数据基础上某条数据是否存在时使用;

特点:

1.有一定的判断错误概率;因为 2个 数据 通过 hash计算后可能会 落到相同的bit位上;

2.不支持删除操作;在实际项目中,如 黑名单 可能存在 今天将用户拉入黑名单,明天拉出黑名单的操作;这时 使用布隆过滤器 无法完成此种业务;因为 每个bit为可能关联多个数据(牵一发而动全身); 这时可以考虑使用 Count Boolm Filter 解决此问题;

问题: 判断数据是否存在或者重复?

方案一: 在内存中 存入所有数据,然后 将被比较数据 和 所有数据进行一一比对;   缺点:数据存储耗费内存多; 比较 效率最差为o(n);

方案二: 在内存中 将所有数据 通过 处理后 直接存储 数据是否存在的状态; 然后 将被比较数据 通过处理后 查看状态 是否为 存在或者不存在即可;  这种方式就是 布隆过滤器; 优点在于 在 海量数据时,因为存储的是 数据是否存在的状态;而不是 海量数据;  优点:存储利用率较高; 比较 效率基本为o(1);   缺点: 存在一定概率 比较失败(误判数据存在);

布隆过滤器计算器

布隆过滤器 根据数据条数,错误率 判断内存使用情况和hash函数个数 的 计算器如下: https://krisives.github.io/bloom-calculator/

总结:

由于布隆过滤器 实现特点;所以 要想误判率越低,则需要 越多的内存及 越多的 hash函数; 但是过多的hash函数会造成 时间及资源上 的损耗; 所以 需要根据实际需求 设置合理的 误判率;

可以通过 上面的 布隆过滤器计算器  快捷计算出需要的 内存空间等数据;

延伸:

解决 布隆过滤器无法 删除数据的问题 可以通过 Count Boolm Filter(CBF) 这种计数布隆过滤器实现;

其实CBF 思路 就是 在将 每个bit位 置为1 的次数 进行计数;  从而达到 删除数据时 则对应bit位 计数减一; 增加数据时 对应bit为 计数加一;

CBF是一种解决无法删除问题的 思路(注意 CBF和SBF,DCF的关系); 具体实现方式分为如下2种:

SBF(Spectral Bloom Filter): 引用原文如下:  将所有counter排成一个位串，counter之间完全不留空隙，然后通过建立索引结构来访问counter，并达到了只使用O(N) + O(m)位的存储目标，O(m)的构建时间。虽然SBF解决了动态counter的存储问题，但其引入了复杂的索引结构，这让每个counter的访问变得复杂而耗时

DCF(Dynamic Count Filter): 其实就是 将 bit位 存的 count值 分别放在 2个列表中; 一个列表 每个数据的 最大值固定(也就是bit位的个数固定); 另一个列表 每个数据 最大值不固定(bit为个数不固定); 2个列表 对应数据 相加 就是 count的值; 存数据时 优先存在固定长度的列表中,存不下再放在 不固定列表中;

这样 最大程度上 可以动态的 调整内存空间;从而更加有效率的利用内存空间;

具体区别及特点如下链接:https://blog.csdn.net/vipshop_fin_dev/article/details/102647115

注意: 由于 CBF 是基于 布隆过滤器 的 基础上进行的变种;所以 布隆过滤器的缺点 这些变种算法同样存在

相关链接:

python及redis 实现 布隆过滤器方法及解决缓存穿透问题: https://www.cnblogs.com/yscl/p/12003359.html#3346833348

散列技术: https://www.jianshu.com/p/7f9d74b34e76