布隆过滤器详解及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小程序,为远程协助助力,…...
YimMenu安全增强指南:四阶法实现GTA V体验升级
YimMenu安全增强指南:四阶法实现GTA V体验升级 【免费下载链接】YimMenu YimMenu, a GTA V menu protecting against a wide ranges of the public crashes and improving the overall experience. 项目地址: https://gitcode.com/GitHub_Trending/yi/YimMenu …...
PlayCover 2.0重构Mac游戏体验:社交与云服务双引擎驱动革新
PlayCover 2.0重构Mac游戏体验:社交与云服务双引擎驱动革新 【免费下载链接】PlayCover Community fork of PlayCover 项目地址: https://gitcode.com/gh_mirrors/pl/PlayCover 在Mac平台运行iOS游戏长期面临两大痛点:缺乏社交连接与跨设备数据同…...
从浮点到定点:手把手教你用MATLAB自定义函数实现加减乘除(避坑溢出与精度损失)
从浮点到定点:手把手教你用MATLAB自定义函数实现加减乘除(避坑溢出与精度损失) 当算法需要从实验室环境迁移到嵌入式设备时,浮点运算的硬件开销常常成为瓶颈。这时定点数运算就像一把手术刀——精准控制每个比特的用途,…...
深求·墨鉴实战教程:DeepSeek-OCR-2 API接入企业OA系统实现自动归档
深求墨鉴实战教程:DeepSeek-OCR-2 API接入企业OA系统实现自动归档 1. 引言:企业文档管理的痛点与解决方案 在日常办公中,企业每天都会产生大量的纸质文档和电子文件,包括合同、报表、会议纪要、审批单等。传统的人工归档方式不仅…...
课堂教学质量综合评分系统
目录 一、项目环境与目录结构 1. 环境要求 2. 推荐目录结构 二、核心类设计:ClassroomScorer 三、关键代码深度解析 1. 基础路径配置 2. 初始化方法:极致灵活的配置 3. 上下文管理器:统一封装 CSV 读取 4. 数据加载:4 类 …...
OpenRGB:如何用一个免费开源软件统一管理所有RGB灯光设备?
OpenRGB:如何用一个免费开源软件统一管理所有RGB灯光设备? 【免费下载链接】OpenRGB Open source RGB lighting control that doesnt depend on manufacturer software. Supports Windows, Linux, MacOS. Mirror of https://gitlab.com/CalcProgrammer1/…...
实践指南:如何使用Cisco DefenseClaw保护你的AI Agent安全
一、背景:AI Agent安全面临的新挑战 最近,开源AI代理框架OpenClaw遭遇了大规模供应链攻击,超过800个恶意技能被植入ClawHub技能市场。这个事件被命名为"ClawHavoc",它暴露了AI Agent生态的安全漏洞。 作为开发者&#x…...
NaViL-9B一文详解:双GPU显存占用分析、服务重启与端口验证
NaViL-9B一文详解:双GPU显存占用分析、服务重启与端口验证 1. 平台概述 NaViL-9B是由专业研究机构开发的原生多模态大语言模型,具备文本问答和图片理解双重能力。该模型在设计上充分考虑了工程落地需求,特别针对双GPU环境进行了优化适配。 …...
Pixel Fashion Atelier保姆级教程:从INSERT COIN按钮到像素粒子物理引擎解析
Pixel Fashion Atelier保姆级教程:从INSERT COIN按钮到像素粒子物理引擎解析 1. 像素时装锻造坊简介 像素时装锻造坊是一款融合了复古游戏美学与现代AI技术的图像生成工具。它基于Stable Diffusion和Anything-v5模型构建,专为时尚设计和像素艺术创作而…...
Windows HEIC缩略图终极指南:3分钟让iPhone照片在Windows完美预览
Windows HEIC缩略图终极指南:3分钟让iPhone照片在Windows完美预览 【免费下载链接】windows-heic-thumbnails Enable Windows Explorer to display thumbnails for HEIC files 项目地址: https://gitcode.com/gh_mirrors/wi/windows-heic-thumbnails 你是不是…...
