布隆过滤器四种实现(Java,Guava,hutool,Redisson)

news/2024/2/25 19:19:05/文章来源:https://blog.csdn.net/o0way0o/article/details/135589867

1.背景

为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据库中进行查询,所以能将数据库查询返回值为空的查询过滤掉。
缓存穿透: 缓存穿透是查询一个根本不存在的数据,由于缓存是不命中时需要从数据库查询,这将导致这个不存在的数据每次请求都要到数据库去查询,进而给数据库带来压力。

2.布隆过滤器介绍

1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列的随机映射函数(哈希函数)两部分组成的数据结构。
用途: 用于检索一个元素是否在一个集合中。
优点:
时间复杂度低,增加及查询元素的时间复杂度都是O(k),k为Hash函数的个数;
占用存储空间小,布隆过滤器相对于其他数据结构(如Set、Map)非常节省空间。
缺点:
存在误判,只能证明一个元素一定不存在或者可能存在,返回结果是概率性的,但是可以通过调整参数来降低误判比例;
删除困难,一个元素映射到bit数组上的k个位置为1,删除的时候不能简单的直接置为0,可能会影响到其他元素的判断。

3.原理

当一个元素加入布隆过滤器中的时候,会进行如下操作:

使用布隆过滤器中的哈希函数对元素进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。
根据得到的哈希值,在位数组中把对应下标的值置为1。
当我们需要判断一个元素是否位于布隆过滤器的时候,会进行如下操作:

对给定元素再次进行相同的哈希计算;
得到值之后判断位数组中的每个元素是否都为1,如果值都为1,那么说明这个值在布隆过滤器中,如果存在一个值不为1,说明该元素不在布隆过滤器中。
举个例子:
在这里插入图片描述
如图所示,当字符串存储要加入到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,然后将对应的位数组的下标设置为1(当位数组初始化时,所有位置均为 0)。当第二次存储相同字符串时,因为先前的对应位置已设置为 1,所以很容易知道此值已经存在(去重非常方便)。
如果我们需要判断某个字符串是否在布隆过滤器中时,只需要对给定字符串再次进行相同的哈希计算,得到值之后判断位数组中的某个元素是否都为1,如果值都为1,那么说明这个值在布隆过滤器中,如果存在一个值不为1,说明该元素不在布隆过滤器中。
不同的字符串可能哈希出来的位置相同,这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。

综上:布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不存在,那么这个元素一定不在。

4.使用场景

4.1判断给定数据是否存在:
比如判断一个数字是否在于包含大量数字的数字集中(数字集很大,5亿以上)、防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)、邮箱的垃圾邮件过滤、黑名单功能等。
4.2去重:
爬给定网址的时候对已经爬取过的URL去重。

5.代码实现

5.1Java实现
package com.fandf.test.redis;import java.util.BitSet;/*** java布隆过滤器*/
public class MyBloomFilter {/*** 位数组大小*/private static final int DEFAULT_SIZE = 2 << 24;/*** 通过这个数组创建多个Hash函数*/private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};/*** 初始化位数组,数组中的元素只能是 0 或者 1*/private final BitSet bits = new BitSet(DEFAULT_SIZE);/*** Hash函数数组*/private final MyHash[] myHashes = new MyHash[SEEDS.length];/*** 初始化多个包含 Hash 函数的类数组,每个类中的 Hash 函数都不一样*/public MyBloomFilter() {// 初始化多个不同的 Hash 函数for (int i = 0; i < SEEDS.length; i++) {myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);}}/*** 添加元素到位数组*/public void add(Object value) {for (MyHash myHash : myHashes) {bits.set(myHash.hash(value), true);}}/*** 判断指定元素是否存在于位数组*/public boolean contains(Object value) {boolean result = true;for (MyHash myHash : myHashes) {result = result && bits.get(myHash.hash(value));}return result;}/*** 自定义 Hash 函数*/private class MyHash {private int cap;private int seed;MyHash(int cap, int seed) {this.cap = cap;this.seed = seed;}/*** 计算 Hash 值*/int hash(Object obj) {return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16)));}}public static void main(String[] args) {String str = "好好学技术";MyBloomFilter myBloomFilter = new MyBloomFilter();System.out.println("str是否存在:" + myBloomFilter.contains(str));myBloomFilter.add(str);System.out.println("str是否存在:" + myBloomFilter.contains(str));}
}
5.2Guava实现

依赖:

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>31.1-jre</version>
</dependency>

代码:

package com.fandf.test.redis;import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;/*** Guava*/
public class GuavaBloomFilter {public static void main(String[] args) {BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);bloomFilter.put("好好学技术");System.out.println(bloomFilter.mightContain("不好好学技术"));System.out.println(bloomFilter.mightContain("好好学技术"));}
}
5.3hutool实现

依赖:

<dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.3</version>
</dependency>

代码:

package com.fandf.test.redis;import cn.hutool.bloomfilter.BitMapBloomFilter;
import cn.hutool.bloomfilter.BloomFilterUtil;/*** hutool*/
public class HutoolBloomFilter {public static void main(String[] args) {BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000);bloomFilter.add("好好学技术");System.out.println(bloomFilter.contains("不好好学技术"));System.out.println(bloomFilter.contains("好好学技术"));}
}
5.4Redisson实现

依赖:

<dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.20.0</version>
</dependency>

代码:

package com.fandf.test.redis;import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;/*** Redisson 实现布隆过滤器*/
public class RedissonBloomFilter {public static void main(String[] args) {Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379");//构造RedissonRedissonClient redisson = Redisson.create(config);RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name");//初始化布隆过滤器:预计元素为100000000L,误差率为1%bloomFilter.tryInit(100000000L,0.01);bloomFilter.add("好好学技术");System.out.println(bloomFilter.contains("不好好学技术"));System.out.println(bloomFilter.contains("好好学技术"));}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925272.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Alibaba-> EasyExcel 整理3

1 导入依赖 <!-- easyExcel --><dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version >3.2.1</version><exclusions><exclusion><artifactId>poi-ooxml-schemas</art…

SQL-分页查询and语句执行顺序

&#x1f389;欢迎您来到我的MySQL基础复习专栏 ☆* o(≧▽≦)o *☆哈喽~我是小小恶斯法克&#x1f379; ✨博客主页&#xff1a;小小恶斯法克的博客 &#x1f388;该系列文章专栏&#xff1a;重拾MySQL &#x1f379;文章作者技术和水平很有限&#xff0c;如果文中出现错误&am…

LLVM系列(1): 在微软Visual Studio下编译LLVM

参考链接&#xff1a; Getting Started with the LLVM System using Microsoft Visual Studio — LLVM 18.0.0git documentation 1.安装visualstudio&#xff0c;版本需要大于vs2019 本机环境已安装visual studio2022&#xff0c;省略 2安装Makefile&#xff0c;版本需要大…

【K8s学习】

k8s的简单执行流程&#xff1a; Kubernetes Master&#xff08;API Server、Scheduler等组件&#xff09;负责调度Pod到合适的Node上。 当Pod被调度到某个Node时&#xff0c;该Node上的kubelet代理会收到指令并开始执行Pod的生命周期管理任务&#xff0c;包括创建、监控和终止P…

【Python数据可视化】matplotlib之绘制常用图形:折线图、柱状图(条形图)、饼图和直方图

文章传送门 Python 数据可视化matplotlib之绘制常用图形&#xff1a;折线图、柱状图&#xff08;条形图&#xff09;、饼图和直方图matplotlib之设置坐标&#xff1a;添加坐标轴名字、设置坐标范围、设置主次刻度、坐标轴文字旋转并标出坐标值matplotlib之增加图形内容&#x…

阿里 P7 三面凉凉,kafka Borker 日志持久化没答上来

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小黄&#xff0c;阿里巴巴淘天Java开发工程师&#xff0c;CSDN博客专家&#x1f4d5;系列专栏&#xff1a;Spring源码、Netty源码、Kafka源码、JUC源码、dubbo源码系列&#x1f525;如果感觉博主的文章还不错…

JVM基础(7)——ParNew垃圾回收器

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 学习必须往深处挖&…

市场复盘总结 20240116

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 昨日主题投资 连板进级率 18% 二进三&#xff1a; 进级率低 60% 最常用的二种方法&#xff1a; 方法一&am…

【iOS】数据持久化(四)之FMDB基本使用

正如我们前面所看到的&#xff0c;原生SQLite API在使用时还是比较麻烦的&#xff0c;于是&#xff0c;开源社区就出现了一系列将SQLite API进行封装的库&#xff0c;其中FMDB的被大多数人所使用 FMDB和SQLite相比较&#xff0c;SQLite比较原始&#xff0c;操作比较复杂&#…

GPT/GPT4在人工智能,深度学习,编程等领域应用

详情点击链接&#xff1a;GPT/GPT4在人工智能&#xff0c;深度学习&#xff0c;编程等领域应用 一OpenAI 1.最新大模型GPT-4 Turbo 2.最新发布的高级数据分析&#xff0c;AI画图&#xff0c;图像识别&#xff0c;文档API 3.GPT Store 4.从0到1创建自己的GPT应用 5. 模型Ge…

价值7500的在线授权网站源码支持IP+域名+双向授权全开源

PHP授权验证更新系统完整版&#xff0c;一键更新系统&#xff0c;一键卡密生成自助授权功能&#xff0c;域名ip双重验证功能等等 修复盗版检测&#xff0c;确保实时查看盗版 修复在线加密系统&#xff0c;一键加密 授权系统几乎所有的程序都能整合使用,包括您的app和计算机程序…

数据结构实战:变位词侦测

文章目录 一、实战概述二、实战步骤&#xff08;一&#xff09;逐个比较法1、编写源程序2、代码解释说明&#xff08;1&#xff09;函数逻辑解释&#xff08;2&#xff09;主程序部分 3、运行程序&#xff0c;查看结果4、计算时间复杂度 &#xff08;二&#xff09;排序比较法1…

docker 安装 zookeeper ( 亲测有效 )

目录 1 安装2 验证 1 安装 上传 zookeeoer.tar 包 到服务器 上传之后tar 包&#xff0c;将他变成镜像 输入docker images,发现目前是没有镜像的&#xff0c;现在将tar 包变成镜像 docker load -i zookeeper.tar因为我们要使用 Docker-compose 去管理容器&#xff0c;所以要使…

网络共享服务

存储类型&#xff1a;直连式&#xff08;DAS&#xff09;:距离最近&#xff0c;存储设备且直接连接到服务器上 存储区域网络&#xff08;SAN&#xff09;&#xff1a;适用于大型应用或数据库系统&#xff0c;可以使用文件的空间&#xff0c; 以及管理空间…

深入理解 Flink(五)Flink Standalone 集群启动源码剖析

前言 Flink 集群的逻辑概念&#xff1a; JobManager(StandaloneSessionClusterEntrypoint) TaskManager(TaskManagerRunner) Flink 集群的物理概念&#xff1a; ResourceManager(管理集群所有资源&#xff0c;管理集群所有从节点) TaskExecutor(管理从节点资源&#xff0c;接…

使用WAF防御网络上的隐蔽威胁之SSRF攻击

服务器端请求伪造&#xff08;SSRF&#xff09;攻击是一种常见的网络安全威胁&#xff0c;它允许攻击者诱使服务器执行恶意请求。与跨站请求伪造&#xff08;CSRF&#xff09;相比&#xff0c;SSRF攻击针对的是服务器而不是用户。了解SSRF攻击的工作原理、如何防御它&#xff0…

贪心算法(思路)

最近在cf上做了很多贪心的题&#xff0c;写篇博客来总结一下 Problem - C - Codeforces 看第一道题 不难看出&#xff0c;我们需要在数组中找到一段奇偶相间的序列&#xff0c;要使他们的和最大&#xff0c; 在图中我们假设[1,2]和[3,4]是奇偶相间的序列&#xff0c;我们在在…

【Docker】数据卷挂载以及宿主机目录挂载的使用

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《Docker实战》。&#x1f3af;&#x1f3af; &…

docker部署私人云盘nextcloud

首先查看效果 1.拉取镜像 docker pull nextcloud 2.创建目录 mkdir -p /data/nextcloud/{config,data,apps} 3.创建实例 docker run -itd --name yznextcloud -v /data/nextcloud/config:/var/www/html/config -v /data/nextcloud/data:/var/www/html/data -v /data/nextc…

关于html导出word总结一

总结 测试结果不理想&#xff0c;html-to-docx 和 html-docx-js 最终导出的结果 都 差强人意&#xff0c;效果可以见末尾的附图 环境 "electron": "24.3.0" 依赖库 html-docx-js html-docx-js - npm html-to-docx html-to-docx - npm file-saver…