当前位置: 首页 > news >正文

手写一个简易的布隆过滤器

1.什么是布隆过滤器

布隆过滤器(Bloom Filter)是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。
人话理解就是,布隆过滤器是一个容器,我们可以往这个容器里添加元素,并且可以查询某个元素是否在容器中存在,欸有人就经验的可以知道,这个工作Set也可以做,为什么要用布隆过滤器呢,

  • 布隆过滤器的优点:
    时间复杂度低,增加和查询元素的时间复杂为O(N),(N为哈希函数的个数,通常情况比较小)
    保密性强,布隆过滤器不存储元素本身
    占用空间小,如果允许存在一定的误判,布隆过滤器是非常节省空间的(相比其他数据结构如Set集合)
  • 布隆过滤器的缺点:
    有点一定的误判率,但是可以通过调整参数来降低
    无法获取元素本身
    很难删除元素(可以试试自己实现一个可以删除元素的某隆过滤器)

2. 布隆过滤器的使用使用场景

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”,也就是说布隆过滤器说这个数不存在则一定不存,布隆过滤器说这个数存在可能不存在(误判,后续会讲),**利用这个判断是否存在的特点可以做很多有趣的事情。

  1. 解决Redis缓存穿透问题(面试重点)
  2. 邮件过滤,使用布隆过滤器来做邮件黑名单过滤
  3. 对爬虫网址进行过滤,爬过的不再爬
  4. 解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
  5. 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();}}
  1. 过滤器实现
/*** 过滤器实现*/
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. 测试
    测试通过
    完事儿,一切对象都可存,

相关文章:

手写一个简易的布隆过滤器

1.什么是布隆过滤器 布隆过滤器&#xff08;Bloom Filter&#xff09;是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多&#xff0c;…...

阿里云快速部署开发环境 (Apache + Mysql8.0)

本文章的内容截取于云服务器管理控制台提供的安装步骤&#xff0c;再整合前人思路而成&#xff0c;文章末端会提供原文连接 ApacheMysql 8.0部署MySQL数据库&#xff08;Linux&#xff09;步骤一&#xff1a;安装MySQL步骤二&#xff1a;配置MySQL步骤三&#xff1a;远程访问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&#xff1a;词义消歧 (Word Sense Disambiguation)举例 2: 垃圾邮件过滤 从垃圾邮件…...

Java并发系列之六:CountDownLatch

CountDownLatch作为开发中最常用的组件&#xff0c;今天我们来聊聊它的作用以及内部构造。 首先尝试用一句话对CountDownLatch进行概括: CountDownLatch基于AQS&#xff0c;它实现了闩锁&#xff0c;在开发中可以将其用作任务计数器。 若想要较为系统地去理解这些特性&#xff…...

24数据结构-图的基本概念与存储结构

目录 第六章 图6.1 图的基本概念知识回顾 6.2 图的储存结构&#xff08;邻接矩阵法&#xff09;1. 数组表示法(1) 有向图&#xff0c;无向图的邻接矩阵 2. 定义邻接矩阵的结构3. 定义图的结构4. 构造图G5. 特点 第六章 图 6.1 图的基本概念 图是一种非线性结构 图的特点&am…...

自然语言处理学习笔记(三)————HanLP安装与使用

目录 1.HanLP安装 2.HanLP使用 &#xff08;1&#xff09;预下载 &#xff08;2&#xff09;测试 &#xff08;3&#xff09;命令行 &#xff08;4&#xff09;测试样例 3.pyhanlp可视化 4. HanLP词性表 1.HanLP安装 HanLP的 Python接口由 pyhanlp包提供&#xff0c;其安装…...

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 管理平台&#xff0c;旨在简化和统一在多个云提供商上运行 Kubernetes 集群的管理和操作。它是由阿里巴巴集团开发和维护的项目。 Mecha 的主要目标是提供一个统一的界面和工具&#xff0c;使用户能够更轻松地在不同的云提供商上…...

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多行数据合并为一行数据 实现查询效果原数据 方式一&#xff1a;MAX()数据效果SQL 方式二&#xff1a;LISTAGG()数据效果 方式三&#xff1a;WM_CONCAT()数据效果 实现查询效果 原数据 FZPROJECTVALUE1电脑$16001手机$121导管$12电脑$22手机$22 方式一&#xff1a;MAX…...

MySQL5.7 与 MariaDB10.1 审计插件兼容性验证

这是一篇关于发现 MariaDB 审计插件导致 MySQL 发生 crash 后&#xff0c;展开适配验证并进行故障处理的文章。 作者&#xff1a;官永强 爱可生DBA 团队成员&#xff0c;擅长 MySQL 运维方面的技能。热爱学习新知识&#xff0c;亦是个爱打游戏的宅男。 本文来源&#xff1a;原创…...

PyTorch Lightning教程五:Debug调试

如果遇到了这样一个问题&#xff0c;当一次训练模型花了好几天&#xff0c;结果突然在验证或测试的时候崩掉了&#xff0c;这个时候其实是很奔溃的&#xff0c;主要还是由于没有提前知道哪些时候会出现什么问题&#xff0c;本节会引入Lightning的Debug方案 1.fast_dev_run参数 …...

末流211无科研保研经验分享

文章目录 个人背景夏令营哈工大威海西工大光电北航软院北邮计算机中科大科学岛 预推免东南软件北航计算机 写在最后心路历程寄语 个人背景 院校&#xff1a;末流211专业背景&#xff1a;计算机科学与技术排名&#xff1a;夏令营7 / 126&#xff0c;预推免3 / 126英语&#xff…...

日期选择器多选换行

<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__分别是什么&#xff1f;0x03.原型链继承不同对象的原型链* 0x04.原型链污染原理0x05.merge()导致原型链污染0x06.ejs模板引擎RCEejs模板引擎另一处rce 0x07.jade模板引擎RCE【ctfs…...

18. SpringBoot 如何在 POM 中引入本地 JAR 包

❤️ 个人主页&#xff1a;水滴技术 &#x1f338; 订阅专栏&#xff1a;成功解决 BUG 合集 &#x1f680; 支持水滴&#xff1a;点赞&#x1f44d; 收藏⭐ 留言&#x1f4ac; Spring Boot 是一种基于 Spring 框架的轻量级应用程序开发框架&#xff0c;它提供了快速开发应用程…...

vue2-$nextTick有什么作用?

1、$nextTick是什么&#xff1f; 官方定义&#xff1a;在下次DOM更新循环结束之后执行延迟回调。在修改数据之后立即使用这个方法&#xff0c;获取更新后的DOM。 解释&#xff1a;Vue在更新DOM时是异步执行的&#xff0c;当数据发生变化时&#xff0c;Vue将开启一个异步更新的队…...

python自动收集粘贴板

win10的粘贴板可以用“winV”查看&#xff1a; 每次复制都相当于入栈一个字符串&#xff0c;粘贴相当于获取栈顶。 但是系统自带的这个粘贴板貌似不能一键导出&#xff0c;所以我写了个python代码完成这个功能&#xff1a; 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() 函数的内容。 相当于 <…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...