如果想要判断一个元素是不是在一个集合中存在，一般的想法是将所有元素保存起来，然后再拿着这个元素在集合中一个一个进行比对。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。 针对这种需要在大量数据中去判断某一个值是事否存在的情况，1970年由布隆提出了布隆过滤器的概念。布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 字节 的空间。布隆过滤器除了一个位数组，还有 n个哈希函数。
它具体的实现思想是并不将具体的数据存储在数组中，而是通过hash函数对要存储的数据进行三次hash运算，并将hash运算的结果做为位数组的下标，将对应的数组元素修改为1。
例如：我们要将”oracle”、”database”、”filter”存储到布隆过滤器中可以这样做。如下图所示
从上图中可以看到，我们有三个hash函数（h1()、h2()、h3()）和一个位数组，oracle经过三个hash函数，得到第1、4、5位为1，database同理得到2、5、10位1，这样如果我们需要判断oracle是否在此位数组中，则通过hash函数判断位数组的1、4、5位是否均为1，如果均为1，则判断oracle在此位数组中，database同理。这就是布隆过滤器判断元素是否在集合中的原理。
但同学们也会发现，如果我们现在要判断”mysql”是否存在，例如它通过三次hash运算得到的值分别是4,5,10。现在即使你的位数中没有存储“mysql”,布隆过滤器也会判断它存在。这是因为”oracle”、”database”、”filter”算出的hash值已经导致上面的三个位置的值被改为了1，这样就会导致误判。但是可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中。
产生上面误判的主要原因是hash碰撞导致的。但如果我们将位数组设置的足够大，并且让hash运算执行的次数多一些，这样就会降低误判率。
布隆过率器还有另一个问题就是不能删除。这是因为在位数组上的同一个点有可能有多个输入值的映射，如果删除了会影响布隆过滤器里其他元素的判断结果。
所以我们可以总结出布隆过滤器的优缺点如下：
优点：所占空间小（并不存储真正的数据），空间效率高查询时间短缺点:元素添加到数组中后，不能被删除有一定的误判率二、布隆过滤器使用场景解决缓存穿透问题，缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中就到数据库中去查，并且出于容错考虑，如果从数据库中查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库中去查询，失去了缓存的意义。在流量大时，可能数据库就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则再到数据库中查。如果不在布隆器中，则直接返回在业务场景中可以用来判断用户是否阅读过某些文章或视频，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。黑名单：比如在邮件系统中可以使用布隆器设置黑名单，判断邮件地址是否在黑名单中。也可以设IP黑名单防止网格爬虫等。垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱。三、实践3.1通过 Java 编程手动实现布隆过滤器package com.heima.rbac.controller; import java.util.BitSet; public class MyBloomFilter { / * 位数组的大小 */ private static final int DEFAULT_SIZE = 2 << 24; / * 通过这个数组可以创建 6 个不同的哈希函数 */ private static final int[] SEEDS = new int[]{5, 17, 48, 73, 93, 132}; / * 位数组。数组中的元素只能是 0 或者 1 */ private BitSet bits = new BitSet(DEFAULT_SIZE); / * 存放包含 hash 函数的类的数组 */ private SimpleHash[] func = new SimpleHash[SEEDS.length]; / * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样 */ public MyBloomFilter() { // 初始化多个不同的 Hash 函数 for (int i = 0; i < SEEDS.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]); } } / * 添加元素到位数组 */ public void add(Object value) { for (SimpleHash f : func) { bits.set(f.hash(value), true); } } / * 判断指定元素是否存在于位数组 */ public boolean contains(Object value) { boolean ret = true; for (SimpleHash f : func) { ret = ret && bits.get(f.hash(value)); } return ret; } / * 静态内部类。用于 hash 操作！ */ public static class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } / * 计算 hash 值 */ public int hash(Object value) { int h; return (value == null) ? 0 : Math.abs(seed * (cap – 1) & ((h = value.hashCode()) ^ (h >>> 16))); } } }3.2Redis 中的布隆过滤器redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。
> docker run -d -p 6379:6379 –name bloomfilter redislabs/rebloom > docker exec -it bloomfilter redis-cliredis 布隆过滤器主要就两个命令：
bf.add 添加元素到布隆过滤器中：bf.add urls http://www.itcast.com。bf.exists 判断某个元素是否在过滤器中：bf.exists urls http://www.itcast.com。上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：
error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。redis 中有一个命令可以来设置这两个值：
bf.reserve urls 0.01 100三个参数的含义：
第一个值是过滤器的名字。第二个值为 error_rate 的值。第三个值为 initial_size 的值。使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists
免责声明：文章内容来自互联网，本站仅作为分享，不对其真实性负责，如有侵权等情况，请与本站联系删除。
转载请注明出处：Java教程：防缓存穿透利器-布隆滤器(BloomFilter) https://www.dachanpin.com/a/cyfx/11702.html
