搜索网站制作教程,金山区网站制作,食品购物网站建设,app微信小程序目录
1 原理
2 代码示例
3 位数组
4 布隆过滤器的实际应用场景 1 原理
布隆过滤器#xff08;Bloom Filter#xff09;是一种数据结构#xff0c;用于快速判断一个元素是否存在于一个集合中#xff0c;具有高效的插入和查询操作。它的设计目的是在空间效率和查询效率之…目录
1 原理
2 代码示例
3 位数组
4 布隆过滤器的实际应用场景 1 原理
布隆过滤器Bloom Filter是一种数据结构用于快速判断一个元素是否存在于一个集合中具有高效的插入和查询操作。它的设计目的是在空间效率和查询效率之间寻求一种折衷方案。
布隆过滤器基于位向量bit array和一系列的哈希函数。它适用于需要进行高速判断的场景例如缓存系统、拼写检查、垃圾邮件过滤等。
布隆过滤器的原理如下 初始化创建一个大小为 m 的位向量所有位初始化为 0。 插入当要插入一个元素时对该元素进行 k 次哈希函数计算将对应的 k 个位设为 1。 查询当要查询一个元素是否存在时同样对该元素进行 k 次哈希函数计算检查对应的 k 个位是否都为 1如果有任何一个位不为 1则确定该元素不存在于集合中。如果所有位都为 1则该元素可能存在于集合中但不确定考虑到误判率。
因为布隆过滤器采用了多次哈希函数并将元素映射到多个位所以存在一定的误判率。即使一个元素不存在于集合中由于其哈希值可能会与其他元素的哈希值重叠导致误判为存在。但是布隆过滤器具有占用空间小、查询速度快的特点适用于需要快速判断元素是否可能存在的场景。
需要注意的是布隆过滤器不支持删除操作因为删除操作会影响到其他可能存在的元素。如果需要支持删除操作可能需要考虑其他数据结构。 2 代码示例
import java.util.BitSet;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;public class BloomFilter {private int size; // 位数组的大小private int hashCount; // 哈希函数的个数private BitSet bitArray; // 位数组public BloomFilter(int size, int hashCount) {this.size size;this.hashCount hashCount;this.bitArray new BitSet(size);}public void add(String item) {for (int i 0; i hashCount; i) {int index hashFunction(item, i) % size;bitArray.set(index, true);}}public boolean contains(String item) {for (int i 0; i hashCount; i) {int index hashFunction(item, i) % size;if (!bitArray.get(index)) {return false;}}return true;}private int hashFunction(String item, int seed) {try {MessageDigest md MessageDigest.getInstance(MD5);md.update((item seed).getBytes());byte[] digest md.digest();return Math.abs(java.util.Arrays.hashCode(digest));} catch (NoSuchAlgorithmException e) {throw new RuntimeException(Hash function error: e.getMessage());}}public static void main(String[] args) {BloomFilter bloomFilter new BloomFilter(100, 3);bloomFilter.add(apple);bloomFilter.add(banana);bloomFilter.add(cherry);System.out.println(bloomFilter.contains(apple)); // 输出 trueSystem.out.println(bloomFilter.contains(banana)); // 输出 trueSystem.out.println(bloomFilter.contains(grape)); // 输出 false}
}根据上述代码可知要使用布隆过滤器需要的成员属性有size位数组大小、hashCount哈希函数的个数、bitArray位数组、hashFunction这个是定义哈希函数的方法参数是要加入集合的值以及哈希计算的次数注意hashCount一般会通过for循环去调用它以便k次哈希计算中每次使用的哈希函数是不同的。 3 位数组
这里提下位数组的概念以及与普通数组的区别 存储方式 位数组位数组中的每个元素只占用一个位0 或 1因此在存储上非常紧凑。它使用的是比特位来表示数据。普通数组普通数组中的每个元素可以是任意数据类型比如整数、浮点数、对象等。根据数据类型的不同存储占用的空间可能会更多。 存储内容 位数组通常用于表示某种状态、存在与否、开关等每个位代表一个二进制信息例如布尔值。普通数组存储任意数据类型可以包含数字、字符串、对象等。 内存占用 位数组由于每个元素只占用一个位因此在相同存储空间下可以存储更多的元素适用于需要存储大量布尔信息的情况。普通数组根据元素的数据类型和数量占用的内存空间会更大。 使用场景 位数组适用于需要紧凑地表示某种状态或标记如布隆过滤器、位图索引等。普通数组适用于存储多种数据类型的数组如整数数组、字符串数组、对象数组等。
总之位数组和普通数组的主要区别在于存储方式和存储内容。位数组通常用于紧凑地存储标志、状态等信息而普通数组可以存储多种类型的数据。选择使用哪种类型的数组取决于具体的应用场景和需求。 4 布隆过滤器的实际应用场景
背景我们知道现如今的电商系统特别是像阿里旗下的、京东等肯定是需要面对高并发请求问题的这时避免不了用到中间件技术例如Redis、MQ。而以某宝为例即使在用户不登录的情况下它是需要有一些开放的API供未登录用户去看的如“/product/{id}”,表示界面上对应的商品。当商品特别多且用户同时点击作请求的次数太大时Redis作为缓存是让服务器能够稳定运行的前提。这看起来似乎是解决了高并发问题且能够避免最影响整个系统服务性能的数据库被频繁访问。但对于黑客来说这其中有个漏洞可钻。既然id是指商品的标识符那我不断输入不存在的商品id而Redis又发现缓存中没有这样的id就会转向数据库作请求如此这般便造成了缓存穿透。所以一个新的问题是我要如何识别并处理这些不存在的id避免让它们频繁“骚扰”数据库呢这时布隆过滤器就这样闪亮登场了。
解决
上面提到的缓存穿透总结来讲是指在缓存中找不到所需的数据导致每次请求都需要访问数据库或其他数据源从而造成系统负担过大。这种情况可能是由于恶意请求、非法输入或者业务逻辑问题导致的。
布隆过滤器可以在缓存层面起到一定的预防作用减轻缓存穿透带来的影响。具体来说以下是布隆过滤器如何用于防止缓存穿透的细节 在查询缓存前进行判断 在查询缓存之前先将查询的参数进行布隆过滤器的检查。如果布隆过滤器判断这个参数不在缓存的可能存在集合中那么就不会去查询缓存避免了不必要的数据库或其他数据源访问。 合法参数和非法参数的判断 布隆过滤器可以帮助区分合法参数和非法参数。如果一个参数不在布隆过滤器中说明它肯定是非法的可以直接返回一个错误或默认值而不会继续访问后端数据源。 动态更新布隆过滤器 当缓存中的数据更新时需要相应地更新布隆过滤器中的信息以确保布隆过滤器的准确性。否则布隆过滤器可能会误判某个参数在缓存中不存在。
需要注意的是布隆过滤器虽然可以减轻缓存穿透问题但并不是完全解决方案。它可以用来过滤掉一部分明显无效的请求但不能保证百分之百防止缓存穿透。在实际应用中布隆过滤器通常与其他技术一起使用如合理设置缓存过期时间、使用缓存预热等来综合解决缓存穿透问题。
其它的应用场景包括拼写检查、垃圾邮件过滤等
