快捷導(dǎo)航

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

更新時(shí)間：2024年10月25日 11:35:09 作者：水中加點(diǎn)糖

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

需求描述

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

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

思路

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

思路二（推薦）：建立一個(gè)(位圖)bitmap，初始時(shí)bitmap的每一位都為0，0代表未使用，1代表已使用。每次請(qǐng)求獲取id時(shí)從此bitmap的第0位開始返回一個(gè)未使用的index即可。

以一個(gè)bitmap長度為65536的bitmap為例，示意圖如下：

初始時(shí)每一個(gè)bit位值都為0

0	1	2	3	4	5	6	7	8	……	1024	……	65535
0	0	0	0	0	0	0	0	0	……	0	……	0

此時(shí)請(qǐng)求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)過一段時(shí)間后，索引位置為5的數(shù)據(jù)變成了0未使用
此時(shí)請(qǐng)求id返回的值應(yīng)為：5

具體實(shí)現(xiàn)

BitSet VS RoaringBitmap

解決思路有了，接下來就是代碼實(shí)現(xiàn)。這里以java代碼為例，可以直接使用jdk自帶的java.util.BitSet實(shí)現(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等多個(gè)版本的實(shí)現(xiàn)，同時(shí)其時(shí)間與空間復(fù)雜度低，提供的方法也非常豐富。
github地址如下：https://github.com/RoaringBitmap

java代碼實(shí)現(xiàn)

以下為《使用bitmap實(shí)現(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é)果：

0
5
11

以上代碼使用new RoaringBitmap()定義了一個(gè)可以自動(dòng)擴(kuò)容的bitmap，add方法的入?yún)⒋韺⒛硞€(gè)bit位設(shè)為1，nextAbsentValue方法返回從某個(gè)index位開始出現(xiàn)的第一個(gè)bit位為0的索引值