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

Java中利用BitMap位图实现海量级数据去重

🏷️个人主页:牵着猫散步的鼠鼠 

🏷️系列专栏:Java全栈-专栏

🏷️个人学习笔记,若有缺误,欢迎评论区指正

目录

前言

什么是BitMap?有什么用?

基本概念

位图的优势

位图的劣势

BitMap和Int的区别

使用场景

BitMap在Java中的使用


1.前言

有许多方法可以用来去重,比如使用列表、集合等等,但这些方法通常只适用于一般情况。然而,当涉及到大量数据去重时,常见的 Java Set、List,甚至是 Java 8 的新特性 Stream 流等方式就显得不太合适了。在处理大量数据的需求场景下,我们不得不提及 BitMap。

2.什么是BitMap?有什么用?

2.1.基本概念

位图(BitMap),基本思想就是用一个bit来标记元素,bit是计算机中最小的单位,也就是我们常说的计算机中的0和1,这种就是用一个位来表示的。

所谓位图,其实就是一个bit数组,即每一个位置都是一个bit,其中的取值可以是0或者1

像上面的这个位图,可以用来表示1,4,6:

如果不用位图的话,我们想要记录1,4,,6 这三个整型的话,就需要用三个unsigned int,已知每个unsigned int占4个字节,那么就是3_4 = 12个字节,一个字节有8 bit,那么就是 12_8 = 96 个bit。

所以,位图最大的好处就是节省空间。

位图有很多种用途,特别适合用在去重、排序等场景中,著名的布隆过滤器就是基于位图实现的。

2.2.位图的优势

  1. 空间效率优势:极大的节省了存储空间,对于大量稀疏数据,特别是当元素数量远大于实际存在的项时,相比较于使用传统的列表、集合等数据结构,位图的空间占用极小。
  2. 查询速度:由于内存访问时按字节或字进行的。因此对单个元素的存在性检查时间复杂度为O(1),即常量时间,非常快速。
  3. 批量操作高效:对于批量插入、删除和查询操作,尤其是统计范围内元素的数量,位图表现出优秀的性能。

2.3.位图的劣势

但是位图也有着一定的限制,那就是他只能表示0和1,无法存储其他的数字。所以他只适合这种能表示true or false的场景。

3.BitMap和Int的区别

以Java中的int为例,来对比观察BitMap的优势,再Java中,int类型通常需要32位,而BitMap使用1位就可以来标识此元素是否存在,所以可以认为BitMap占用的空间大小只有int类型的1/32,所以有大量数据判重时,使用BitMap也可以实现。

了解了什么是BitMap,那么我们就可以使用BitMap来解决大量数据去重的问题

4.使用场景

假设我们有40亿个无符号整数数据,并且都是10位的话,如果直接使用内存来存储,大约需要14.9GB 的空间。

每个无符号整数通常占用4个字节(32位),因此40亿个无符号整数所需要的总字节数位4*4000000000字节。 总字节数转换为GB:4*4000000000 / 1024 / 1024 /1024 = 14.9 GB

考虑到其中有一些重复的数据,即使这样1G的空间基本上也是不够的。所以想要实现这个功能可以借助BitMap。

如果使用位图的话,40亿万所需要的内存大概也就是 476M

40亿无符号整数数据的总字节数是4000000000 字节,在位图中1个10位的无符号整数可以使用1 bit表示,然后1 字节 = 8 位(bit)。 4000000000 bit * 1/8 求出字节数,再 / 1024得到占用的KB数,最后/ 1024得到占用的MB数 4000000000 * 1 /8 /1024/1024 = 476M

这样相比于之前的14.9G来说,大大的节省了很多空间。

比如要把数据"714771310"放到BitMap中,就需要找到第714771310这个位置,然后把他设置成1就可以了。

这样,把40亿个数字都放到BitMap之后,所有位置上是1的表示存在,不为1的表示不存在,相同的数据只需要设置一次1就可以了,那么,最终就把所有是1的数字遍历出来就行了。

5.BitMap在Java中的使用

BitMap在Java中的具体实现时java.util中的BitSet,BitSet是一个可变大小的位向量,能够动态增长以容纳更多的数据,以下是BitSet基本使用示例:

import java.util.BitSet;public class BitmapExample {public static void main(String[] args) {// 创建一个BitSet实例BitSet bitmap = new BitSet();// 设置第5个位置为1,表示第5个元素存在bitmap.set(5);// 检查第5个位置是否已设置boolean exists = bitmap.get(5);System.out.println("Element at position 5 exists: " + exists);  // 输出: Element at position 5 exists: true// 设置从索引10到20的所有位置为1bitmap.set(10, 21);  // 参数是包含起始点和不包含终点的区间// 计算bitset中所有值为1的位的数量,相当于计算设置了的元素个数int count = bitmap.cardinality();System.out.println("Number of set bits: " + count);// 清除第5个位置bitmap.clear(5);// 判断位图是否为空boolean isEmpty = bitmap.isEmpty();System.out.println("Is the bitset empty after clearing some bits? " + isEmpty);}
}

6.总结 

本文简单的讲解了如何使用BitMap进行大量数据的去重,BitMap的空间占用极小,对单个元素的存在性检查时间复杂度为O(1),非常快速,除了BitMap外,我们也可以采取布隆过滤器来完成去重,但是布隆过滤器存在误判问题,可以根据实际场景来分析使用哪种方案

相关文章:

Java中利用BitMap位图实现海量级数据去重

🏷️个人主页:牵着猫散步的鼠鼠 🏷️系列专栏:Java全栈-专栏 🏷️个人学习笔记,若有缺误,欢迎评论区指正 目录 前言 什么是BitMap?有什么用? 基本概念 位图的优势 …...

Linux知识点记录

Linux知识点记录 1. 后台运行应用程序方法一:&方法二:nohup & 2. 一个shell脚本中执行多个应用程序3. 2>&14. shell脚本清除日志5. 通过grep查找匹配字符串 1. 后台运行应用程序 参考文章:https://blog.csdn.net/Pan_peter/…...

js的check函数

在JavaScript中,并没有一个内置的名为check的函数。然而,你可以根据需求自定义一个check函数,用于执行各种验证和检查任务。这个check函数的具体作用完全取决于你如何定义和实现它。 以下是一个简单的示例,展示了如何定义一个che…...

赛尼格磁电科技邀您到场参观2024第13届生物发酵展

参展企业介绍 北京赛尼格磁电科技有限公司是一家中加合资的专业永磁组件生产商,2001年成立于中国北京。公司专业从事磁性材料的应用及各类磁系统的设计、开发及制造,公司产品广泛应用于汽车行业、建筑行业、电子行业、航海领域、医学领域、教育领域等。 …...

gpt国内怎么用?最新版本来了

claude 3 opus面世后,这几天已经有许多应用,而其精确以及从不偷懒(截止到2024年3月11日还没有偷懒)的个性,也使得我们可以用它来首次完成各种需要多轮对话的尝试。 今天我们想要进行的一项尝试就是—— 如何从一个不知…...

Vim脚本语言入门:打造你的编辑器

简介 Vim脚本语言是Vim编辑器内置的一种脚本语言,它赋予用户高度的定制和自动化编辑任务的能力。通过编写Vim脚本,用户可以根据自己的需求来扩展和改进Vim编辑器的功能,从而提高编辑效率和舒适度。 在Vim中,脚本语言被广泛用于创…...

myweb项目资料集

项目要求 前后端分离后端采用 flask 框架前端采用 vue3 框架 后端部分 Flask 3 框架: https://dormousehole.readthedocs.io/en/latest/quickstart.html Session: https://blog.csdn.net/zhangvalue/article/details/93892241 MySQL 操作&#xf…...

Kubernetes(k8s):部署、使用 metrics-server

Kubernetes(k8s):部署、使用 metrics-server 一、metrics-server简介二、部署metrics-server2.1、 下载 Metrics Server 部署文件2.2、修改metrics-server.yaml 文件2.3、 部署 Metrics Server2.4、 检查 Metrics Server 三、使用 Metrics Se…...

为什么建议你学习Spring底层原理?

1.根因 Java诞生以来,一直是业界的主流语言和平台,而Spring则是Java开发的平台。与其说是用Java编程,不如说是在Spring框架上编程。即便最近几年比较火的Spring Boot、Spring Cloud,其底层内核仍然是Spring。因此,作为…...

post请求搜索功能爬虫

<!--爬虫仅支持1.8版本的jdk--> <!-- 爬虫需要的依赖--> <dependency> <groupId>org.apache.httpcomponents</groupId> <artifactId>httpclient</artifactId> <version>4.5.2</version> </dependency>…...

#pragma once的作用

使用visual studio新建头文件时&#xff0c;第一行会出现如下默认代码&#xff0c; #pragma once 它是一种编译器指令&#xff0c;通常用于确保头文件只被包含一次&#xff0c;以避免产生重复定义的问题。当编译器处理一个源文件时&#xff0c;遇到#pragma once指令时&#xf…...

【Android】图解View的工作流程原理

文章目录 入口DecorView如何加载到Window中MeasureSpec MeasureView的测量ViewGroup的测量 LayoutView的layout() Draw1、绘制背景3、绘制View内容4、绘制子View6、绘制装饰 入口 DecorView如何加载到Window中 MeasureSpec 该类是View的内部类&#xff0c;封装View的规格尺寸…...

记工时流程

记工时流程 加入团体 加入观古鉴古服务队 登录成功后&#xff0c;点击我的-我的成员 添加成员 进入小程序 扫描后登录&#xff0c;我的-我的团体&#xff0c;可以看到观古鉴古服务队&#xff0c; 进入后点项目 选择观古鉴古文化志愿者招募 -> 我要报名 -> 选择文化志…...

Ubuntu20.04使用Neo4j导入CSV数据可视化知识图谱

1.安装JDK&#xff08; Ubuntu20.04 JDK11&#xff09; sudo apt-get install openjdk-11-jdk -y java -version which java ls -l /usr/bin/java ls -l /etc/alternatives/java ls -l /usr/lib/jvm/java-11-openjdk-amd64/bin/java确认安装路径为/usr/lib/jvm/java-11-openjd…...

vue-cli打包 nodejs内存溢出 vue2.x Last few GCs

遇到这种情况百度各种博客&#xff0c;什么改package.json里的配置&#xff0c;什么安装increase-memory-limit &#xff0c;都尝试了并没什么用处&#xff0c;最后解决方案为执行下方名单&#xff0c;再次打包就成功了&#xff1a; export NODE_OPTIONS--max_old_space_size4…...

SpringBoot整合Flowable/Activiti

SpringBoot版本: 2.0.1.RELEASE Flowable版本: 6.3.1 Activiti版本: 6.0.0 一.添加pom依赖 因为之前我整合的时候有报错关于sqlsession的错误,后面查询文章才发现flowable要排除掉mybatis,又没说具体排除哪一个,所以我这干脆全部排除了 <!-- Flowable dependencies -->…...

基础总结篇:Activity生命周期

private int param 1; //Activity创建时被调用 Override public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); Log.i(TAG, “onCreate called.”); setContentView(R.layout.lifecycle); Button btn (Button) findViewById(R.id.…...

【鸿蒙 HarmonyOS】@ohos.promptAction (弹窗)

一、背景 创建并显示文本提示框、对话框和操作菜单。 文档地址&#x1f449;&#xff1a;文档中心 说明 本模块首批接口从API version 9开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。 该模块不支持在UIAbility的文件声明处使用&#xff0c;即…...

ElasticSearch的常用数据类型

常见的数据类型 Text类型&#xff08;文本数据类型&#xff09; 用于全文检索的字段&#xff0c;例如电子邮件的正文或产品的描述。这些字段是analyzed&#xff0c;也就是说&#xff0c;它们通过分析器传递&#xff0c;以便 在被索引之前将字符串转换为单个术语的列表。通过分…...

C/C++预处理过程

目录 前言&#xff1a; 1. 预定义符号 2. #define定义常量 3. #define定义宏 4. 带有副作用的宏参数 5. 宏替换的规则 6. 宏和函数的对比 7. #和## 8. 命名约定 9. #undef 10. 命令行定义 11. 条件编译 12. 头文件的包含 13. 其他预处理指令 总结&#x…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...