布隆过滤器详解及java实现
什么是布隆过滤器?
布隆过滤器(Bloom Filter)是一种数据结构,用于判断一个元素是否属于一个集合。它的特点是高效地判断一个元素是否可能存在于集合中,但是存在一定的误判率。
布隆过滤器的基本原理是使用一个位数组(Bit Array)和多个哈希函数。初始时,所有位都被置为0。当添加一个元素时,会使用多个哈希函数计算出多个哈希值,并将对应的位数组位置置为1。当判断一个元素是否存在于集合时,同样使用多个哈希函数计算哈希值,并检查对应的位数组位置是否都为1,若有任意一位不为1,则可以确定该元素一定不在集合中;若所有位都为1,则可能存在于集合中,存在一定的误判率。总结来说就是: 布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在。
应用场景
-
缓存系统: 布隆过滤器可以用于缓存系统中,用于快速判断一个数据是否存在于缓存中。在查询之前,可以先使用布隆过滤器进行判断,如果判断不存在,则不需要查询缓存系统,从而减少了查询时间。
-
大型数据库系统: 在数据库系统中,布隆过滤器可以用于快速判断一个元素是否存在于数据库中。对于一些经常被访问的热点数据,可以先使用布隆过滤器进行判断,如果判断不存在,则可以避免进行实际的数据库查询操作。
-
URL去重: 在网络爬虫中,布隆过滤器可以用于URL的去重。当爬取一个新的URL时,可以先使用布隆过滤器判断该URL是否已经存在于已爬取的URL集合中,从而避免重复爬取相同的URL。
代码实现
下面用java来实现一个简单的布隆过滤器
public class BloomFilter {private static final int DEFAULT_SIZE = 2 << 24; // 布隆过滤器的比特长度private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61}; // 哈希种子,用于产生多个哈希函数private BitSet bits = new BitSet(DEFAULT_SIZE);private SimpleHash[] func = new SimpleHash[seeds.length]; // 存储多个哈希函数public BloomFilter() {for (int i = 0; i < seeds.length; i++) {func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);}}public void add(String value) {if (value != null) {for (SimpleHash f : func) {bits.set(f.hash(value), true);}}}public boolean contains(String value) {if (value == null) {return false;}boolean result = true;for (SimpleHash f : func) {result = result && bits.get(f.hash(value));}return result;}public static class SimpleHash {private int cap;private int seed;public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}public int hash(String value) {int result = 0;int len = value.length();for (int i = 0; i < len; i++) {result = seed * result + value.charAt(i);}return (cap - 1) & result;}}public static void main(String[] args) {BloomFilter filter = new BloomFilter();filter.add("test");filter.add("hello");System.out.println(filter.contains("test")); // trueSystem.out.println(filter.contains("hello")); // trueSystem.out.println(filter.contains("world")); // false}
}
、
相关文章:
布隆过滤器详解及java实现
什么是布隆过滤器? 布隆过滤器(Bloom Filter)是一种数据结构,用于判断一个元素是否属于一个集合。它的特点是高效地判断一个元素是否可能存在于集合中,但是存在一定的误判率。 布隆过滤器的基本原理是使用一个位数组…...
CloudCompare 点云工具
CloudCompare 点云工具 1. CloudCompare简介1.1 CloudCompare下载 2. CloudCompare安装 1. CloudCompare简介 CloudCompare 是一款开源的三维点云处理软件,它提供了一系列功能来处理、查看和分析三维点云数据。这个软件可以用于许多不同的应用领域,包括…...
Linux 著名的sudo、su是什么?怎么用?
一、su 什么是su? su命令(简称是:substitute 或者 switch user )用于切换到另一个用户,没有指定用户名,则默认情况下将以root用户登录。 为了向后兼容,su默认不改变当前目录,只设…...
C语言分支语句
一、什么是语句 C语句可分为以下五类: 表达式语句 函数调用语句 控制语句 复合语句 空语句 本周后面介绍的是控制语句。 控制语句用于控制程序的执行流程,以实现程序的各种结构方式,它们由特定的语句定义符组成,C语 言有…...
android 资源文件混淆
AGP7.0以上引用AndResGuard有坑 记录下 在项目的build.gradle中添加如下 buildscript {ext.kotlin_version "1.4.31"repositories {google()jcenter()maven {url "https://s01.oss.sonatype.org/content/repositories/snapshots/"}}dependencies {class…...
注册接口和前置SQL及数据生成及封装
注册接口 演示注册接口的三步操作:【注册流程逻辑】 第一步:发送注册短信验证码接口请求 请求方法: put 请求地址:http://shop.lemonban.com:8107/user/sendRegisterSms 请求参数:{“mobile”:“13422337766”} 请求头…...
鸿蒙实战开发-通过输入法框架实现自绘编辑框
介绍 本示例通过输入法框架实现自会编辑框,可以绑定输入法应用,从输入法应用输入内容,显示和隐藏输入法。 效果预览 使用说明 1.点击编辑框可以绑定并拉起输入法,可以从输入法键盘输入内容到编辑框。 2.可以点击attach/dettac…...
深度学习中的注意力模块的添加
在深度学习中,骨干网络通常指的是网络的主要结构或主干部分,它负责从原始输入中提取高级特征。骨干网络通常由卷积神经网络(CNN)或者类似的架构组成,用于对图像、文本或其他类型的数据进行特征提取和表示学习。 注意力…...
Docker 部署开源远程桌面工具 RustDesk
RustDesk是一款远程控制,远程协助的开源软件。完美替代TeamViewer ,ToDesk,向日葵等平台。关键支持自建服务器,更安全私密远程控制电脑!官网地址:https://rustdesk.com/ 环境准备 1、阿里云服务器一 台&a…...
intellij idea 使用git ,快速合并冲突
可以选择左边的远程分支上的代码,也可以选择右边的代码,而中间是合并的结果。 一个快速合并冲突的小技巧: 如果冲突比较多,想要快速合并冲突。也可以直接点击上图中 Apply non-conflicting changes 旁边的 All 。 这样 Idea 就会…...
AcWing26. 二进制中1的个数。三种解法Java
输入一个 3232 位整数,输出该数二进制表示中 11 的个数。 注意: 负数在计算机中用其绝对值的补码来表示。 数据范围 −100≤ 输入整数 ≤100 样例1 输入:9 输出:2 解释:9的二进制表示是1001,一共有2个…...
【ADB】常见命令汇总(持续更新)
▒ 目录 ▒ 🛫 导读开发环境 1️⃣ 设备连接和识别2️⃣ 应用程序管理3️⃣ 文件传输和管理4️⃣ 设备信息和日志5️⃣ 设备操作和控制6️⃣ 截图相关🛬 文章小结📖 参考资料 🛫 导读 Android调试桥(ADB)是…...
【递归与递推】数的计算|数的划分|耐摔指数
1.数的计算 - 蓝桥云课 (lanqiao.cn) 思路: 1.dfs的变量>每一次递归什么在变? (1)当前数的大小一直在变:sum (2)最高位的数:k 2.递归出口:最高位数字为1 3.注意&#…...
企业案例:金蝶云星空集成钉钉,帆软BI
正文:在数字化转型的大潮中,众多企业开始探索并实践高效的数据流转与集成,以提升内部管理效率和决策质量。本文将以某企业为例,详细介绍如何通过将钉钉审批流程的数据实时同步至金蝶云星空,并进一步在帆软报表平台上实…...
简单设计模式讲解
设计模式是在软件开发中经常使用的最佳实践,用于解决在软件设计中经常遇到的问题。它们提供了可重用的设计,使得代码更加灵活、可维护和可扩展。下面我将为你讲解几种常见的设计模式,并提供相应的C#代码示例。 1. 单例模式(Single…...
基于springboot的社区医疗服务系统
文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式 🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 &…...
影院座位选择简易实现(uniapp)
界面展示 主要使用到uniap中的movable-area,和movable-view组件实现。 代码逻辑分析 1、使用movable-area和movea-view组件,用于座位展示 <div class"ui-seat__box"><movable-area class"ui-movableArea"><movab…...
调用飞书获取用户Id接口成功,但是没有返回相应数据
原因: 该自建应用没有开放相应的数据权限。 解决办法: 在此处配置即可。...
STM32 GPIO输入检测——按键
前言 在嵌入式系统开发中,对GPIO输入进行检测是一项常见且关键的任务。STM32微控制器作为一款功能强大的处理器,具有丰富的GPIO功能,可以轻松实现对外部信号的检测和处理。在本文中,我们将深入探讨如何在STM32微控制器上进行GPIO…...
Rustdesk二次编译,新集成AI功能开源Gpt小程序为远程协助助力,全网首发
环境: Rustdesk1.1.9 sciter版 问题描述: Rustdesk二次编译,新集成AI功能开源Gpt小程序为远程协助助力,全网首发 解决方案: Rustdesk二次编译,新集成开源AI功能Gpt小程序,为远程协助助力,…...
面试(03)————多线程和线程池
一、多线程 1、什么是线程?线程和进程的区别? 2、创建线程有几种方式 ? 3、Runnable 和 Callable 的区别? 4、如何启动一个新线程、调用 start 和 run 方法的区别? 5、线程有哪几种状态以及各种状态之间的转换? 6、线程…...
纯CSS实现未读消息显示99+
在大佬那看到这个小技巧,我觉得这个功能点还挺常用,所以给大家分享下具体的实现。当未读消息数小于100的时候显示准确数值,大于99的时候显示99。 1. 实现效果 2. 组件封装 <template><span class"col"><sup :styl…...
【C++】C++ primer plus 第十二章--类和动态内存分配
动态内存和类 关于静态数据成员 类之作声明,不分配内存,因此静态成员变量在类中不能进行初始化,需要在类外进行。特殊情况: 存在可以在类中声明静态成员并初始化的情况,成员类型为const整型或者const枚举类型。 特殊…...
分类预测 | Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据分类预测
分类预测 | Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据分类预测 目录 分类预测 | Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据…...
使用PHP进行极验验证码动态参数提取与逆向分析
在网络安全领域,逆向工程和验证码破解是常见的技术挑战之一。极验验证码作为一种常见的人机验证工具,其动态参数的提取和逆向分析对于验证码的破解至关重要。本文将介绍如何使用PHP语言进行极验验证码动态参数的提取与逆向分析。 1. 准备工作 在开始之前…...
43.1k star, 免费开源的 markdown 编辑器 MarkText
43.1k star, 免费开源的 markdown 编辑器 MarkText 分类 开源分享 项目名: MarkText -- 简单而优雅的开源 Markdown 编辑器 Github 开源地址: https://github.com/marktext/marktext 官网地址: MarkText 支持平台: Linux, macOS 以及 Win…...
ArcGIS Pro怎么进行挖填方计算
在工程实施之前,我们需要充分利用地形,结合实际因素,通过挖填方计算项目的标高,以达到合理控制成本的目的,这里为大家介绍一下ArcGIS Pro中挖填方计算的方法,希望能对你有所帮助。 数据来源 教程所使用的…...
POLY - Survival Melee Weapons
一个轻便、有趣且灵活的低多边形资源包,非常适合原型设计或添加到低多边形世界中。超过50种近战武器、刀、斧、棍棒、棍棒等。 此套餐非常适合第三人称或自上而下的观看。 除此之外,资产还包括开发生存游戏可能需要的任何细节。 整个包是以多边形风格创建的,可以与其他多边…...
【ARMv7-M】| 01——阅读笔记 | 简介|应用程序级编程和内存模型
系列文章目录 【ARMv7-M】| 01——阅读笔记 | 简介|应用程序级编程和内存模型 失败了也挺可爱,成功了就超帅。 文章目录 前言1、简介2、应用程序级编程模型2.1 编程模式和访问等级2.2 数据类型和运算操作2.3 寄存器和执行状态1.2.4 异常和中断1.2.5 浮点单元寄存器…...
用Python做一个4399游戏脚本原来这么简单 !(内含完整思路)
说明 简述:本文将以4399小游戏《宠物连连看经典版2》作为测试案例,通过识别小图标,模拟鼠标点击,快速完成配对。对于有兴趣学习游戏脚本的同学有一定的帮助。 运行环境:Win10/Python3.5。 主要模块:win3…...
珠宝网站建设要以商为本/济南做网站比较好的公司
像HTML/CSS中的style一样,android也可以使用自定义的style样式 一般是在value 文件夹下面建一个styles.xml文件 样式是用于描述一个View或是一个窗口的显示属性的集合,样式可以指定如高度,填充,字体颜色,字体大小,背景…...
中山精品网站建设方案/2024最火的十大新闻
要点: 案例注意点vuex的引入是在store.index.js中 然后就是对于没有逻辑的方法,就可以直接再组件方法调用commit去直接连接mutations:this.$state.commit(大写方法名,数据) 对那些需要逻辑判断定时器,需要发送ajax请求的都需要在组件方法调用dispatch…...
团购酒店的网站建设/营销工具
卷首语 致远SPM系统进度计划管理是项目管理的核心业务,是站在企业层面对现行组织中所有的项目进行筛选、评估、计划、执行与控制的项目管理方式。 致远SPM系统支持对不同层级的项目进行直接监控和干预,对多个项目进行分析比较,更好地分配资源…...
大连开发区论坛网/seo优化技术培训中心
今天这篇文章来分析一下什么是前后端分离的相关知识,很多小伙伴不清楚到底什么是前端,什么是后端,什么是前后端分离。在说前后端分离之前,我们先要弄清楚这几个概念,大家可能经常听到前端,后端或者是大前端…...
网站建设优化服务如何/seo排名赚app是真的吗
如果您使用的是JDK 7,请使用新的Files.createTempDirectory类创建临时目录。Rulepublic TemporaryFolder folder new TemporaryFolder();在JDK 7之前,应该这样做:public static File createTempDirectory()throws IOException{final File te…...
做购物比价的网站/网址ip地址查询工具
原文链接:https://cloud.google.com/kubernetes-engine/kubernetes-comic/后台回复“加群”,带你进入高手如云交流群▼喜欢,就给我一个“在看”10T 技术资源大放送!包括但不限于:云计算、虚拟化、微服务、大数据、网络…...