前言海量数据解决和缓存渗透这两个场景让我认识了Bloom filter。我查阅了少量资料进行了解，但是很多可用的资料都不符合我的需求，所以我决定自己总结一篇关于Bloom filter的文章。 希望通过这篇文章，让更多的人了解Bloom filter，并会实际使用它！下面我们将分几个方面来详细介绍Bloom filter:什么是Bloom filter？布隆过滤器原理的细节 布隆过滤器使用场景 用Java编程手动实现布隆过滤器 利用谷歌开源番石榴中的布鲁姆过滤器。 Redis中的布隆过滤器 1.什么是布鲁姆滤镜？首先，我们需要了解Bloom filter的概念。 布鲁姆滤镜是一个叫布鲁姆的哥哥在1970年提出的。 我们可以把它看作是由二进制向量(或位数组)和一系列随机映射函数(哈希函数)组成的数据结构。 与常用的链表、Map、Set等数据结构相比，占用空间更少，效率更高，但缺点是返回的结果是概率性的，不是很准确。 理论上，添加到集合中的元素越多，虚警的可能性就越大。 而且Bloom filter中存储的数据不容易删除。 QQ: 2046136117自由存取数据位数组中每个元素只占1位，每个元素只能是0或1。 这种具有100w个元素的位阵列的应用仅占用100000 bit/8 = 125000 byte = 125000/1024 kb≈122 kb。 概要:一个叫Bloom的人提出了一种数据结构来检索元素是否可以在给定的大集合中。这种数据结构是高效的，具有良好的性能，但其缺点是正错误识别率和删除困难。 而且从理论上讲，集合中加入的元素越多，虚警的可能性就越大。 二。Bloom filter原理细节当一个元素被添加到Bloom filter中时，会进行如下操作:使用Bloom filter中的hash函数计算元素值，得到hash值(有几个hash函数得到几个hash值) 根据得到的哈希值，在比特数组中设置对应的下标值为1。 当我们需要判断一个元素是否可以存在于Bloom filter中时，我们会做以下操作:确定该元素再次执行相同的哈希计算；确定最后一个位数组中的每个元素是否都可以是1。如果所有值都为1，则意味着该值在布隆过滤器中。如果有一个不是1的值，这意味着该元素不在布隆过滤器中。 举个简单的例子:QQ: 2046136117免费获取信息。如图，当字符串存储要添加到Bloom filter中时，字符串会先通过多个hash函数生成不同的hash值，然后将对应的位数组的下级表中的元素设置为1(位数组初始化时，所有位置都为0)。 当第二次存储相同的字符串时，由于之前的对应位置已被设置为1，因此很容易知道该值已经存在(重复数据删除非常方便) 不同的字符串可能在相同的位置被散列，在这种情况下，我们可以适当地增加位数组的大小或调整我们的散列函数。 综上所述，我们可以得出一个结论:Bloom filter说一个元素存在，它会有小概率被误判。 Bloom filter说一个元素不在，那么这个元素肯定不在。 3.Bloom filter使用场景来判断一个给定的数据是否可以存在:比如一个数是否可以在包含大量数的数集中(数集非常大，超过5亿！)、防止缓存穿透(判断请求的数据是否能有效避免直接绕过缓存请求数据库)等。、邮箱的垃圾邮件过滤、黑名单功能等。 重新加权:例如，当抓取给定的URL时，重新加权已经抓取的URL。 四。通过Java编程手动实现布隆过滤器。上面我们已经提到了Bloom filter的原理，了解了Bloom filter的原理之后，就可以自己手动实现一个了。 如果要手动实现一个，需要:一个大小合适的位数组来存储数据，几个不同的哈希函数来给位数组添加元素(Bloom filter)，一个判断给定元素是否可以存在于位数组中的方法(Bloom filter)。 下面是我觉得写得还算不错的一段代码(参考了网上现有的代码进行了改进，适用于所有类型的对象):import Java . util . bitset；类myBloomfilter {/* * *位数组大小*/Private static final int default _ Size = 2 数组中的元素只能是0或1 */private bitset bits = new bitset(default _ size)；/* * *保存包含哈希函数的类的数组*/privatesimplehash[]func = newsimplehash[seeds . length]；/* * *初始化多个包含哈希函数的类的数组，每个类中的哈希函数是不同的*/ public MyBloomFilter() {//初始化多个不同的哈希函数for(int I = 0；我& lt种子.长度；i++){ func[I]= new simple hash(DEFAULT _ SIZE，SEEDS[I])；}}/* * *添加元素就地数组*/public void Add(object value){ for(simple hash f:func){ bits . set(f . hash(value)，true)；}}/* * *确定指定的元素是否可以存在于位数组*/public boolean contains(对象值){ boolean ret = truefor(simple hash f:func){ ret = ret & amp；& ampbits . get(f . hash(value))；ret返回；}/* * *静态内部类 用于哈希运算！*/公共静态类SimpleHash { private int cap私有int种子；public SimpleHash(int cap，int seed){ this . cap = cap；this.seed = seed}/* * *计算哈希值*/public int hash(object value){ int h；return (value == null)？0:math . ABS(seed *(cap-1)& amp；((h = value . hashcode())^(h & gt；& gt& gt16)));} } } Test:String value 1 = " https://Java guide . cn/"；String value2 = " SnailclimbMyBloomFilter filter = new MyBloomFilter()；system . out . println(filter . contains(value 1))；system . out . println(filter . contains(value 2))；filter . add(value 1)；filter . add(value 2)；system . out . println(filter . contains(value 1))；system . out . println(filter . contains(value 2))；输出:假假真真测试:整数值1 = 13423；整数值2 = 22131；MyBloomFilter filter = new MyBloomFilter()；system . out . println(filter . contains(value 1))；system . out . println(filter . contains(value 2))；filter . add(value 1)；filter . add(value 2)；system . out . println(filter . contains(value 1))；system . out . println(filter . contains(value 2))；输出:假假真真五、谷歌开源番石榴中使用布鲁姆滤镜的主要目的是让自己了解布鲁姆滤镜的原理。Bloom filter在Guava中的实现是比较权威的，实际项目中我们不需要手动实现一个Bloom filter。 首先，我们需要将Guava的依赖性引入到项目中: Guava提供的Bloom filter的实现是相当不错的(想详细了解可以看看它的源代码实现)，但是它有一个重大缺陷就是只能单机使用(另外不容易扩展容量)，现在互联网一般都是分布式的。 为了解决这个问题，我们需要在Redis中使用Bloom filter。 不及物动词Redis 1中的Bloom filter。细节Redis v4.0以后，有了模块功能，Redis Modules允许Redis使用外部模块来扩展功能。 布隆过滤器就是其中的一个模块。 另外官网推荐了一个redi bloom作为redi bloom过滤器的模块，地址为redi bloom/redi bloom。 其他:Redis-Lua-scaling-bloom-filter(由Lua脚本实现):erikdubbelboer/Redis-Lua-scaling-bloom-filter PyreBloom(Python中的快速redisbloom过滤器):seomoz/ PyreBloom......RedisBloom提供多种语言的客户端支持，包括Python、Java、JavaScript和PHP。 2.使用Docker安装如下:~ Docker Run-p 6379:6379-Name Redis-Redis Bloom Redis Labs/re Bloom:latest ~ Docker Exec-ire dis-Redis Bloom bash root @ 21396 d02c 252:/data # Redis-CLI 127 . 0 . 0..3.常用命令列表注意:key:Bloom filter的名称，item:添加的元素。 BF。ADD:向Bloom过滤器添加元素，如果过滤器尚不存在，则创建过滤器。 格式:BF。添加{key} {item} BF。MADD:在“布鲁姆过滤器”中添加一个或多个元素，创建一个尚不存在的过滤器。 该命令的操作方式与BF相同。ADD，只是它允许多个输入并返回多个值。 格式:BF。MADD {key} {item} [item...] BF。EXISTS:确定元素是否可以存在于Bloom filter中。 格式:BF。存在{key} {item} BF。确定一个或多个元素是否可以具有Bloom filter: BF中的格式。我存在{key} {item} [item...] 另外，BF。RESERVE命令需要单独的细节:这个命令的格式如下:BF。预留{ key } { error _ rate } { capacity }[expansion expansion] 下面简单描述一下每个参数的具体含义:key:bloom filter名称error_rate:虚警期望概率 这应该是介于0和1之间的十进制值。 例如，对于0.1%的预期虚警率(千分之一)，error_rate应设置为0.001。 数字越接近零，每个项目的内存消耗越大，每次操作的CPU利用率越高。 容量:过滤器的容量。 当实际存储的元素数量超过该值时，性能将开始下降。 的实际退化将取决于超过极限的程度。 随着过滤元件的数量呈指数增长，性能将呈线性下降。 可选参数:expansion:如果创建了一个新的子过滤器，其大小将是当前过滤器的大小乘以扩展。 默认的扩展名值是2。 这意味着每个后续子过滤器将是前一个的两倍大。 4.实际使用127.0.0.1: 6379 >: BF。添加my filter Java(integer)1 127 . 0 . 0 . 1:6379 & gt；BF。ADD my filter Java guide(integer)1 127 . 0 . 0 . 1:6379 & gt；BF。EXISTS my filter Java(integer)1 127 . 0 . 0 . 1:6379 & gt；BF。EXISTS my filter Java guide(integer)1 127 . 0 . 0 . 1:6379 & gt；BF。Exists MyFilter GitHub (integer) 0参考:Java高级核心知识综合分析