快捷導(dǎo)航

java使用bitmap實現(xiàn)可回收自增id的示例

更新時間：2024年10月25日 11:35:09 作者：水中加點糖

本文主要介紹了java使用bitmap實現(xiàn)可回收自增id的示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

需求描述

設(shè)計一個方法，每次調(diào)用返回一個自增id，同時需要滿足以下要求。

可更新id的狀態(tài)為已使用，已使用的id下次調(diào)用時不再返回
可修改某個id的狀態(tài)為未使用，下次調(diào)用時設(shè)為未使用狀態(tài)的id可重新被返回

思路

思路一：如果數(shù)據(jù)量非常小，直接使用一個集合存儲已使用的id，使用循環(huán)和維護這個集合即可，但數(shù)據(jù)量大了，此方法返回數(shù)據(jù)的時間復(fù)雜度和占用的空間都是比較大的。

思路二（推薦）：建立一個(位圖)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

如經(jīng)過一段時間后，索引位置為5的數(shù)據(jù)變成了0未使用
此時請求id返回的值應(yīng)為：5

具體實現(xiàn)

BitSet VS RoaringBitmap

解決思路有了，接下來就是代碼實現(xiàn)。這里以java代碼為例，可以直接使用jdk自帶的java.util.BitSet實現(xiàn)，不過自帶的BitSet在數(shù)據(jù)稀疏的場景下占用空間較大，且提供的原生方法較少。

這里推薦直接使用由2016年由幾位大佬論文而開發(fā)的RoaringBitmap，可移步它的官網(wǎng)詳細(xì)學(xué)習(xí)一把。https://roaringbitmap.org/about/

roaringBitmap

RoaringBitmap有java、go、c\c++、rust、swift等多個版本的實現(xiàn)，同時其時間與空間復(fù)雜度低，提供的方法也非常豐富。
github地址如下：https://github.com/RoaringBitmap

java代碼實現(xiàn)

以下為《使用bitmap實現(xiàn)可回收自增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 0
        rr.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
    }

輸出結(jié)果：