本文主要是介绍使用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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
