使用bitmap实现可回收自增id

需求描述

设计一个方法，每次调用返回一个自增id，同时需要满足以下要求。

1. 可更新id的状态为已使用，已使用的id下次调用时不再返回
2. 可修改某个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