使用bitmap实现可回收自增id
需求描述
设计一个方法,每次调用返回一个自增id,同时需要满足以下要求。
- 可更新id的状态为已使用,已使用的id下次调用时不再返回
- 可修改某个id的状态为未使用,下次调用时设为未使用状态的id可重新被返回
思路
思路一:如果数据量非常小,直接使用一个集合存储已使用的id,使用循环和维护这个集合即可,但数据量大了,此方法返回数据的时间复杂度和占用的空间都是比较大的。
思路二(推荐):建立一个(位图)bitmap,初始时bitmap的每一位都为0,0代表未使用,1代表已使用。每次请求获取id时从此bitmap的第0位开始返回一个未使用的index即可。
以一个bitmap长度为65536的bitmap为例,示意图如下:
初始时每一个bit位值都为0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | …… | 1024 | …… | 65535 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | …… | 0 | …… | 0 |
此时请求id返回的值为:0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | …… | 1024 | …… | 65535 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | …… | 1 | …… | 0 |
如经过一段时间后,索引位置为5的数据变成了0未使用
此时请求id返回的值应为:5
具体实现
BitSet VS RoaringBitmap
解决思路有了,接下来就是代码实现。这里以java代码为例,可以直接使用jdk自带的java.util.BitSet实现,不过自带的BitSet在数据稀疏的场景下占用空间较大,且提供的原生方法较少。
这里推荐直接使用由2016年由几位大佬论文而开发的RoaringBitmap,可移步它的官网详细学习一把。https://roaringbitmap.org/about/

RoaringBitmap有java、go、c\c++、rust、swift等多个版本的实现,同时其时间与空间复杂度低,提供的方法也非常丰富。
github地址如下:https://github.com/RoaringBitmap
java代码实现
以下为《使用bitmap实现可回收自增id》的示例代码
引入依赖
<dependency><groupId>org.roaringbitmap</groupId><artifactId>RoaringBitmap</artifactId><version>1.0.0</version></dependency>
示例代码:
public static void main(String[] args) {RoaringBitmap rr = new RoaringBitmap();long l = rr.nextAbsentValue(0);System.out.println(l);//print 0rr.add(0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 1024, 1025);l = rr.nextAbsentValue(0);System.out.println(l);//print 5// index 5 set true(1)rr.add(5);l = rr.nextAbsentValue(0);System.out.println(l);//print 11}
输出结果:
0
5
11
以上代码使用new RoaringBitmap()定义了一个可以自动扩容的bitmap,add方法的入参代表将某个bit位设为1,nextAbsentValue方法返回从某个index位开始出现的第一个bit位为0的索引值
分布式自增可回收id实现方案
RoaringBitmap还有一大特点:支持序列化与反序列化。

凭借这一特点,如需要在分布式场景下使用RoaringBitmap,则仅需稍微修改代码即可快速实现。
如将RoaringBitmap序列化为二进制存储在数据库中。
比如在mongodb中使用Binary data数据类型、mysql中使用blob数据类型、oracle中使用BLOB这些二进制类型存储RoaringBitmap即可。
实现时每次先将RoaringBitmap读取到程序中,再进行逻辑操作,修改后再写回数据库中。
总结一下
RoaringBitmap YYDS
相关文章:
使用bitmap实现可回收自增id
需求描述 设计一个方法,每次调用返回一个自增id,同时需要满足以下要求。 可更新id的状态为已使用,已使用的id下次调用时不再返回可修改某个id的状态为未使用,下次调用时设为未使用状态的id可重新被返回 思路 思路一࿱…...
0基础学习VR全景平台篇第118篇:利用动作录制器功能避免重复操作 - PS教程
上课!全体起立~ 大家好,欢迎观看蛙色官方系列全景摄影课程! 嗨,大家好。欢迎收看蛙色VR系列教程之PS利用动作记录器节约补地时间。 大家拍摄在补地的时候,利用插件选择输入输出选项的时候,每次重复操作…...
大数据Doris(十九):数据导入(Load)
文章目录 数据导入(Load) 一、Broker load 二、Stream load 三、Insert 四、Multi load...
BP神经网络的数据分类——语音特征信号分类
大家好,我是带我去滑雪! BP神经网络,也称为反向传播神经网络,是一种常用于分类和回归任务的人工神经网络(ANN)类型。它是一种前馈神经网络,通常包括输入层、一个或多个隐藏层和输出层。BP神经网…...
基于SSM+Vue的随心淘网管理系统
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:Vue 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目:是 目录…...
大语言模型的关键技术(二)
一、Transformer 语言模型存在明显的扩展效应: 更大的模型/数据规模和更多的训练计算通常会导致模型能力的提升。 1、扩展效应的原因: 模型规模:增加模型的规模,即增加模型的参数数量和层数,通常会提高模型的表示能力…...
世界互联网大会领先科技奖发布 百度知识增强大语言模型关键技术获奖
11月8日,2023年世界互联网大会乌镇峰会正式开幕,今年是乌镇峰会举办的第十年,本次峰会的主题为“建设包容、普惠、有韧性的数字世界——携手构建网络空间命运共同体”。 目录 百度知识增强大语言模型关键技术荣获“世界互联网大会领先科技奖”…...
2023.11.09 homework (2)
【七年级上数学】 教别人也是教自己,总结下: 13)找规律的题目,累加题目,要整体看,不然不容易算出来,求最大值,那么就是【最大值集群和】减去【最小集群和】就是最大值 9-12&#x…...
ARMday01(计算机理论、ARM理论)
计算机理论 计算机组成 输入设备、输出设备、运算器、控制器、存储器 1.输入设备:将编写好的软件代码以及相关的数据输送到计算机中,转换成计算机能够识别、处理和存储的数据形式 键盘、鼠标、手柄、扫描仪、 2.输出设备:将计算机处理好的数…...
C#中通过LINQtoXML加载、创建、保存、遍历XML和修改XML树
目录 一、加载、创建、保存、遍历XML 1.加载XML (1)从已有文件加载XML (2)从字符串加载XML 2.创建并保存XML 3.遍历XML 4.示例源码 5.运行 二、修改XML的树 1.添加节点 2.删除 3.更新 4.示例源码 5.运行效果 三、…...
进程管理(二)
进程并发制约关系及临界区 (3)比如A的n为MAX,此时B执行buf[Max]出错。 临界区是访问临界资源的代码。 par并发执行 进程同步机制准则 让权等待:主动让位 进程互斥访问临界资源的软件解决方案 算法1——设置访问编号 no_op是空指令,做空操作,空转指令。no_op依然会占…...
数字图像处理 基于numpy库的傅里叶变换
一、傅里叶变换 图像可以用两个域表示:空间域和频域。空间域是图像最常见的表示形式,其中像素值表示图像中每个点的亮度或颜色。另一方面,频域将图像表示为不同频率和幅度的正弦波的集合。 傅里叶变换(一种图像处理中使用的数学技术)可以通过分析图像的频率分量并揭示隐藏…...
scrapy案例教程
文章目录 1 scrapy简介2 创建项目3 自定义初始化请求url4 定义item5 定义管道 1 scrapy简介 scrapy常用命令 |命令 | 格式 |说明| |–|–|–| |startproject |scrapy startproject <项目名> |创建一个新项目| |genspider| scrapy genspider <爬虫文件名> <域名…...
1-3 docker 安装 prometheus
一、环境 1、环境准备 安装Docker 镜像加速 安装 docker 检查版本 安装Docker-compose 二、Docker-compose 安装 Prometheus 1、【方式一】手动创建 docker-compose 和 配置文件 创建prometheus监控的文件夹 创建alertmanager的配置文件 - config.yml 新建grafana的…...
Mac使用brew搭建kafka集群
1. 第一步:单机搭建 单机搭建: 安装完后,默认自动安装对应版本zookeeper brew install kafka2.第二步:修改配置文件: 配置3个Kafka 第一个(使用默认配置) vi /opt/homebrew/etc/kafka/server.propertie…...
图形界面应用案例——关灯游戏(以及扩展)(python)
7.8 图形界面应用案例——关灯游戏 题目: [案例]游戏初步——关灯游戏。 关灯游戏是很有意思的益智游戏,玩家通过单击关掉(或打开)一盏灯。如果关(掉(或打开)一个电灯,其周围(上下左右)的电灯也会触及开关,成功地关掉所有电灯即可过关。 图7-43 关灯游戏运行效…...
Android平台上执行C/C++可执行程序,linux系统编程开发,NDK开发前奏。
Android平台上执行C/C可执行程序,linux系统编程开发,NDK开发前奏准备。 1.下载NDK,搭建NDK开发环境 下载地址 https://developer.android.com/ndk/downloads 下载过程中点击下面箭头的地方,点击鼠标右键,复制好下载…...
elasticsearch 基本使用,ES8.10
官方文档:https://www.elastic.co/guide/en/elasticsearch/reference/current/elasticsearch-intro.html ES版本:8.10 By default, Elasticsearch indexes all data in every field and each indexed field has a dedicated, optimized data structure…...
pytorch中常用的损失函数
1 损失函数的作用 损失函数是模型训练的基础,并且在大多数机器学习项目中,如果没有损失函数,就无法驱动模型做出正确的预测。 通俗地说,损失函数是一种数学函数或表达式,用于衡量模型在某些数据集上的表现。损失函数在…...
申克SCHENCK动平衡机显示器维修CAB700系统控制面板
适用电枢转子的卧式平衡机,高测量率,自动测量循环,自动定标完整的切槽计数可选项,CAB700动平衡测量系统两种皮带驱动方式(上置式或下置式)适用于站立或坐姿操作的人性化工作台设计。 动平衡机申克控制器面板维修型号:V…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)
旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据!该数据集源自2025年4月发表于《地理学报》的论文成果…...
【技巧】dify前端源代码修改第一弹-增加tab页
回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码,在知识库增加一个tab页"HELLO WORLD",完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...
