手写一个简易的布隆过滤器
1.什么是布隆过滤器
布隆过滤器(Bloom Filter)是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。
人话理解就是,布隆过滤器是一个容器,我们可以往这个容器里添加元素,并且可以查询某个元素是否在容器中存在,欸有人就经验的可以知道,这个工作Set也可以做,为什么要用布隆过滤器呢,
- 布隆过滤器的优点:
时间复杂度低,增加和查询元素的时间复杂为O(N),(N为哈希函数的个数,通常情况比较小)
保密性强,布隆过滤器不存储元素本身
占用空间小,如果允许存在一定的误判,布隆过滤器是非常节省空间的(相比其他数据结构如Set集合) - 布隆过滤器的缺点:
有点一定的误判率,但是可以通过调整参数来降低
无法获取元素本身
很难删除元素(可以试试自己实现一个可以删除元素的某隆过滤器)
2. 布隆过滤器的使用使用场景
布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”,也就是说布隆过滤器说这个数不存在则一定不存,布隆过滤器说这个数存在可能不存在(误判,后续会讲),**利用这个判断是否存在的特点可以做很多有趣的事情。
- 解决Redis缓存穿透问题(面试重点)
- 邮件过滤,使用布隆过滤器来做邮件黑名单过滤
- 对爬虫网址进行过滤,爬过的不再爬
- 解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
- HBase\RocksDB\LevelDB等数据库内置布隆过滤器,用于判断数据是否存在,可以减少数据库的IO请求
实现原理
布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例,Redis中的布隆过滤器底层是一个大型位数组(二进制数组)+多个无偏hash函数。
我下面的实现是采用了二维数组的方式来实现的,一个hash函数对应每一个数组,这样的误判率会非常小,当然每个人都有自己的实现方式,学习思想即可
代码实现
1.定义接口
public interface AccessInterface<T extends Object> {void add(T t);boolean query(T t);boolean set(T t);
}
2.hash值方法实现
public class HashCode<T extends Object> {/*** @param index* @param length* @param t* @return* 注:适用于hashpool较小的时候,,太大了不行。计算hash值的时候会溢出,当然这个问题换个对象来计算就行了,这里图省事就简单点, Java有内置的大数据对象。*/public int GetHashCode(int index,int length,T t){int hashcode=t.hashCode();Long hashcode1=Math.round(Math.floor((hashcode+index+index*index)%length));return hashcode1.intValue();}}
- 过滤器实现
/*** 过滤器实现*/
public class BlloomEnity<T extends Object> implements AccessInterface<T> {private boolean[][] blloompool;private int length;HashCode<T> Code;public BlloomEnity() {this.length=100;this.blloompool=new boolean[100][100];this.Code=new HashCode<T>();}public BlloomEnity( int length) {this.blloompool = new boolean[length][length];this.length = length;this.Code=new HashCode<T>();}@Overridepublic void add(T o) {for(int i=0;i<this.length;i++){int k=Code.GetHashCode(i+1,this.length,o);this.blloompool[i][k]=true;}}@Overridepublic boolean query(T o) {for(int i=0;i<this.length;i++){int k=Code.GetHashCode(i+1,this.length,o);if(!this.blloompool[i][k]){return false;}}return true;}@Overridepublic boolean set(T o) {if(query(o)){return false;}else{add(o);}return true;}
}
- 测试

完事儿,一切对象都可存,
相关文章:
手写一个简易的布隆过滤器
1.什么是布隆过滤器 布隆过滤器(Bloom Filter)是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,…...
阿里云快速部署开发环境 (Apache + Mysql8.0)
本文章的内容截取于云服务器管理控制台提供的安装步骤,再整合前人思路而成,文章末端会提供原文连接 ApacheMysql 8.0部署MySQL数据库(Linux)步骤一:安装MySQL步骤二:配置MySQL步骤三:远程访问My…...
侧边栏的打开与收起
侧边栏的打开与收起 <template><div class"box"><div class"sideBar" :class"showBox ? : controller-box-hide"><div class"showBnt" click"showBox!showBox"><i class"el-icon-arrow-r…...
贝叶斯学习
贝叶斯 贝叶斯学习的背景贝叶斯定理举例 概览选择假设— MAPMAP举例 选择假设 — 极大似然 MLML 举例: 抛硬币问题 极大似然 & 最小二乘Nave Bayesian Classifier (朴素贝叶斯分类器)举例1:词义消歧 (Word Sense Disambiguation)举例 2: 垃圾邮件过滤 从垃圾邮件…...
Java并发系列之六:CountDownLatch
CountDownLatch作为开发中最常用的组件,今天我们来聊聊它的作用以及内部构造。 首先尝试用一句话对CountDownLatch进行概括: CountDownLatch基于AQS,它实现了闩锁,在开发中可以将其用作任务计数器。 若想要较为系统地去理解这些特性ÿ…...
24数据结构-图的基本概念与存储结构
目录 第六章 图6.1 图的基本概念知识回顾 6.2 图的储存结构(邻接矩阵法)1. 数组表示法(1) 有向图,无向图的邻接矩阵 2. 定义邻接矩阵的结构3. 定义图的结构4. 构造图G5. 特点 第六章 图 6.1 图的基本概念 图是一种非线性结构 图的特点&am…...
自然语言处理学习笔记(三)————HanLP安装与使用
目录 1.HanLP安装 2.HanLP使用 (1)预下载 (2)测试 (3)命令行 (4)测试样例 3.pyhanlp可视化 4. HanLP词性表 1.HanLP安装 HanLP的 Python接口由 pyhanlp包提供,其安装…...
CS 144 Lab Five -- the network interface
CS 144 Lab Five -- the network interface TCP报文的数据传输方式地址解析协议 ARPARP攻击科普 Network Interface 具体实现测试tcp_ip_ethernet.ccTCPOverIPv4OverEthernetAdapterTCPOverIPv4OverEthernetSpongeSocket通信过程 对应课程视频: 【计算机网络】 斯坦福大学CS144…...
Mecha
一、Mecha Mecha 是一个开源的多云 Kubernetes 管理平台,旨在简化和统一在多个云提供商上运行 Kubernetes 集群的管理和操作。它是由阿里巴巴集团开发和维护的项目。 Mecha 的主要目标是提供一个统一的界面和工具,使用户能够更轻松地在不同的云提供商上…...
Apache RocketMQ之集成RocketMQ_MQTT 安装部署协议
Apache RocketMQ 安装说明 安装步骤 参考快速开始 https://rocketmq.apache.org/zh/docs/quickStart/01quickstart 安装可视化rocketmq_dashboard下载地址 https://rocketmq.apache.org/zh/docs/4.x/deployment/03Dashboard/ 安装rocketmq_mqtt https://rocketmq.apache.o…...
Oracle多行数据合并为一行数据,并将列数据转为字段名
Oracle多行数据合并为一行数据 实现查询效果原数据 方式一:MAX()数据效果SQL 方式二:LISTAGG()数据效果 方式三:WM_CONCAT()数据效果 实现查询效果 原数据 FZPROJECTVALUE1电脑$16001手机$121导管$12电脑$22手机$22 方式一:MAX…...
MySQL5.7 与 MariaDB10.1 审计插件兼容性验证
这是一篇关于发现 MariaDB 审计插件导致 MySQL 发生 crash 后,展开适配验证并进行故障处理的文章。 作者:官永强 爱可生DBA 团队成员,擅长 MySQL 运维方面的技能。热爱学习新知识,亦是个爱打游戏的宅男。 本文来源:原创…...
PyTorch Lightning教程五:Debug调试
如果遇到了这样一个问题,当一次训练模型花了好几天,结果突然在验证或测试的时候崩掉了,这个时候其实是很奔溃的,主要还是由于没有提前知道哪些时候会出现什么问题,本节会引入Lightning的Debug方案 1.fast_dev_run参数 …...
末流211无科研保研经验分享
文章目录 个人背景夏令营哈工大威海西工大光电北航软院北邮计算机中科大科学岛 预推免东南软件北航计算机 写在最后心路历程寄语 个人背景 院校:末流211专业背景:计算机科学与技术排名:夏令营7 / 126,预推免3 / 126英语ÿ…...
日期选择器多选换行
<el-form-item label"日期选择"><div class"multi-date-picker"><div class"date-item"><span class"dateIcon"><el-icon><Calendar /></el-icon></span><span class"dateIt…...
NodeJS原型链污染ctfshow_nodejs
文章目录 NodeJS原型链污染&ctfshow_nodejs前言0x01.原型与原型链0x02.prototype和__proto__分别是什么?0x03.原型链继承不同对象的原型链* 0x04.原型链污染原理0x05.merge()导致原型链污染0x06.ejs模板引擎RCEejs模板引擎另一处rce 0x07.jade模板引擎RCE【ctfs…...
18. SpringBoot 如何在 POM 中引入本地 JAR 包
❤️ 个人主页:水滴技术 🌸 订阅专栏:成功解决 BUG 合集 🚀 支持水滴:点赞👍 收藏⭐ 留言💬 Spring Boot 是一种基于 Spring 框架的轻量级应用程序开发框架,它提供了快速开发应用程…...
vue2-$nextTick有什么作用?
1、$nextTick是什么? 官方定义:在下次DOM更新循环结束之后执行延迟回调。在修改数据之后立即使用这个方法,获取更新后的DOM。 解释:Vue在更新DOM时是异步执行的,当数据发生变化时,Vue将开启一个异步更新的队…...
python自动收集粘贴板
win10的粘贴板可以用“winV”查看: 每次复制都相当于入栈一个字符串,粘贴相当于获取栈顶。 但是系统自带的这个粘贴板貌似不能一键导出,所以我写了个python代码完成这个功能: import pyperclip import timetmp while True:txt…...
Vue3_语法糖—— <script setup>以及unplugin-auto-import自动引入插件
<script setup>import { ref , onMounted} from vue;let obj ref({a: 1,b: 2,}); let changeObj ()>{console.log(obj)obj.value.c 3 //ref写法}onMounted(()>{console.log(obj)})</script> 里面的代码会被编译成组件 setup() 函数的内容。 相当于 <…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
