首页/新闻资讯/正文详情

位图-布隆过滤1

发布时间:2026/9/26 11:15:06 来源:云帆数科 栏目:资讯中心
位图-布隆过滤1
一无符号32位整数范围 0 ~4294967295 一共约42.9亿个可能数字刚好覆盖题目40亿。BitMap规则1个bit总数除以8字节除以1024kb再除以1024mb得出512兆运用位图只需要512mb内存即可存入压缩多倍二一个字节是八个比特位1 Byte 8 bit位图类似hash但是比hash利用率高原本40个字节现在只需要3个字节就能存这个数组1. 普通HashMap存数组 {1,3,7,4,12,16,19,13,22,18}HashMap 是存键值对key数字value标记存在。- 一个Integer对象本身开销很大对象头4字节int哪怕用基础类型的 HashMapInteger,Boolean- 还要哈希表的数组容量、链表/红黑树指针会有大量空间浪费还有哈希冲突 这里10个数字要几十甚至上百字节。普通int数组每个int4字节10个就是 10 ×4 40字节就是你刚才说的。2. BitMap位图不存数字本身bit的位置下标 数字bit的值只用0/1标记有没有。例子里最大数字是22只需要23个bit向上对齐到字节只要3字节24bit。空间直接压缩十几倍。✅ 但是BitMap不是万能的有硬性限制考试常考点BitMap适合数字范围不大、是整数- 如果数字很大比如数字是 1000000 那你得开辟100万bit的空间直接爆内存这时位图就废了得换回hash。- 如果数字是负数、字符串位图直接不能用。3. 和Hash的核心差异一句话- Hash存数据本身计算hash值找到桶能存很大的数但有额外空间开销、哈希冲突。- BitMap下标就是数据只用1bit标记存在与否极致省内存但依赖数字的范围不能太大三位图底层 byte[] 字节数组底层就是字节数组 byte[]每个 byte 1字节 8bit可以标记8个数字。拿图里例子数字 12公式1. 数组下标 index 数字 / 8 整数除法​2. byte内的bit位置 bitPos 数字 % 8 取模1啥意思 叫做 左移运算符1 n 把数字 1 的二进制整体向左移动 n 位右边空出来的位置补01 的二进制1个字节来看 00000001举例1. 1 0 左移0位 → 00000001 十进制1​2. 1 1 左移1位 → 00000010 十进制2​3. 1 2 左移2位 → 00000100 十进制4​4. 1 4 左移4位 → 00010000 十进制16规律1 n 等价于 2^n- 13 2^3 8​- 15 2^5 32在位图里是干嘛的1 bitIndex 专门用来制造掩码生成一个二进制数只有第 bitIndex 位是1剩下全部是0比如 bitIndex2 12 → 00000100只有第2位是1其他都是0。然后配合- | 按位或把这一位设置成1set添加数字​- 按位与检查这一位是不是1get查询​- ~(1n) 取反之后 把这一位清成0remove删除int arrayIndex val / 8 ;四//扩容if(arrayIndex elem.length-1) {elem Arrays.copyOf(elem,arrayIndex1);}变量含义val 你要存的数字位图的第val位​- arrayIndex 这个位落在byte数组的第几个元素 val / 8 每1个byte存8bit​- elem 底层byte数组 elem.length 当前一共有多少个字节elem.length -1 数组最大合法下标数组下标从0开始五问题为什么普通内存放不下16G原始数组1、先算原始数据占用题目40亿个无符号整数一个int占4字节40亿 × 4 160亿字节 ≈{16GB}现在普通电脑/服务器内存情况- 个人电脑常见内存8G、16G、32G​- 就算机器物理内存是16G操作系统本身就要占一部分内存JVM虚拟机也要占用内存。 你没法把完整16GB的数据全部一次性加载进内存。比如你电脑物理内存一共16G系统开机就吃掉3~5G留给Java程序的堆内存可能就只有8G左右。直接加载16G的int数组直接OOM内存溢出。2、对比Bitmap方案用位图BitMap只需要 512MB很小轻轻松松放进内存。原理1bit标记一个数字是否存在不再存储数字本身。10亿个字节为什么是1g核心换算小技巧10亿个字节大概是0.9G可看做是1G10亿个比特位大概是119兆看做128兆

相关推荐

GVF:面向受政策约束的大模型医疗申诉生成的智能体治理与对抗验证框架
GVF:面向受政策约束的大模型医疗申诉生成的智能体治理与对抗验证框架

GVF:面向受政策约束的大模型医疗申诉生成的智能体治理与对抗验证框架 arXiv编号:arXiv:2609.27844v1 摘要 理赔拒付管理是美国医疗体系成本最高的运营瓶颈之一,每年带来约2600亿美元管理开销与报销延迟。大语言模型与检索增强生成(R(\mathcal A)G)虽然可以生成流畅的临床文… · 2026/9/26 11:15:06

OpenClaw多Agent部署从入门到精通:openclaw.json配置骨架与飞书接入实战
OpenClaw多Agent部署从入门到精通:openclaw.json配置骨架与飞书接入实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 11:15:06

算法(62):Bellford algorithm的证明,negative weights-18.5
算法(62):Bellford algorithm的证明,negative weights-18.5

Q:对于每个v,都由相应的处理。对于每个v,都计算过邻边。这个绿色循环,每次都计算了整个图像。但是,这还不够,因为要包含负权重,所以可能出现被计算过的distTo变小的情况,因此还有一个… · 2026/9/26 11:15:00

WorkBuddy实战:从大模型到AI Agent,四十分钟完成网站发布
WorkBuddy实战:从大模型到AI Agent,四十分钟完成网站发布

这两年我明显感觉到一个变化:大家不再问“AI 能不能写代码”,而是问“AI 能不能把一件完整的事做完”。如果你现在还觉得 AI Agent 只是“更聪明的聊天机器人”,那 2026 年的效率红利基本和你没什么关系。最近我把一套“从需求到发布”的流程… · 2026/9/26 13:40:22

Perplexity Computer 接入 MiniMax H3 与 Seedance 2.5:本地部署视频生成工作流实战
Perplexity Computer 接入 MiniMax H3 与 Seedance 2.5:本地部署视频生成工作流实战

1. 从标题拆解:Perplexity Computer 接入 MiniMax H3 与 Seedance 2.5 到底在做什么Perplexity Computer 接入 MiniMax H3 与 Seedance 2.5,这个标题乍一看像是三条产品线的简单叠加,但真正动手跑过一轮的人会明白,它描述的其实是… · 2026/9/26 13:40:22

Perplexity Computer接入MiniMax H3与Seedance 2.5:智能体编排视频生成工作流
Perplexity Computer接入MiniMax H3与Seedance 2.5:智能体编排视频生成工作流

1. 从标题拆解这次接入的真实意图 1.1 为什么“Perplexity Computer MiniMax H3 Seedance 2.5”值得单独聊 先把这三个词拆开看。Perplexity Computer 是 Perplexity 推出的一个面向“执行型任务”的智能体环境,它和普通对话式问答最大的区别在于:它不… · 2026/9/26 13:40:22

P1379“热浪”题解:堆优化Dijkstra最短路从入门到熟练
P1379“热浪”题解:堆优化Dijkstra最短路从入门到熟练

1. 这道“热浪”到底在考什么如果你刷过《信息学奥赛一本通》,看到“热浪”这个标题,大脑里应该立刻蹦出三个字:最短路。没错,P1379 这道题在题单里几乎是每个学图论的人都会碰到的入门模板题,英文原名 heatwv&#xf… · 2026/9/26 13:40:22

Codos虚拟首席AI官:员工访谈驱动自动化落地全解析
Codos虚拟首席AI官:员工访谈驱动自动化落地全解析

1. 从"访谈"到"自动化":Codos到底在解决什么问题 第一次看到"Codos"这个名字和"虚拟首席AI官"这个定位,我的直觉是:又一个把AI包装成高管头衔的营销概念。但仔细拆解"员工访谈驱动自动化"… · 2026/9/26 13:40:22

LeetCode 513:二叉树遍历核心考点,BFS与DFS精讲
LeetCode 513:二叉树遍历核心考点,BFS与DFS精讲

1. 从一道题看二叉树遍历的核心考点1.1 LeetCode 513到底在考什么LeetCode 513这题,题目全称叫"找树左下角的值",对应的英文是Find Bottom Left Tree Value。很多第一次刷到这道题的人,第一眼看到"左下角"三个字&#xf… · 2026/9/26 13:40:16

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码