快捷導(dǎo)航

Java中BitMap(位圖)hutool版、IntMap、LongMap示例詳解

更新時間：2024年12月27日 10:26:34 作者：qq_41369135

這篇文章主要給大家介紹了關(guān)于Java中BitMap(位圖)hutool版、IntMap、LongMap的相關(guān)資料,通過位運算高效存儲和檢索整數(shù),相比于傳統(tǒng)數(shù)組,它們在內(nèi)存占用和性能上都有顯著優(yōu)勢,需要的朋友可以參考下

一、引入依賴

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.5.1</version>
</dependency>

二、源碼

BitMap （interface ）

package cn.hutool.bloomfilter.bitMap;

public interface BitMap {
    int MACHINE32 = 32;
    int MACHINE64 = 64;

    void add(long var1);

    boolean contains(long var1);

    void remove(long var1);
}

IntMap （class）

package cn.hutool.bloomfilter.bitMap;

import java.io.Serializable;

public class IntMap implements BitMap, Serializable {
    private static final long serialVersionUID = 1L;
    private final int[] ints;

    public IntMap() {
        this.ints = new int[93750000];
    }

    public IntMap(int size) {
        this.ints = new int[size];
    }

    public void add(long i) {
        int r = (int)(i / 32L);
        int c = (int)(i % 32L);
        this.ints[r] |= 1 << c;
    }

    public boolean contains(long i) {
        int r = (int)(i / 32L);
        int c = (int)(i % 32L);
        return (this.ints[r] >>> c & 1) == 1;
    }

    public void remove(long i) {
        int r = (int)(i / 32L);
        int c = (int)(i % 32L);
        int[] var10000 = this.ints;
        var10000[r] &= ~(1 << c);
    }
}

LongMap（class）

package cn.hutool.bloomfilter.bitMap;

import java.io.Serializable;

public class LongMap implements BitMap, Serializable {
    private static final long serialVersionUID = 1L;
    private final long[] longs;

    public LongMap() {
        this.longs = new long[93750000];
    }

    public LongMap(int size) {
        this.longs = new long[size];
    }

    public void add(long i) {
        int r = (int)(i / 64L);
        long c = i % 64L;
        this.longs[r] |= 1L << (int)c;
    }

    public boolean contains(long i) {
        int r = (int)(i / 64L);
        long c = i % 64L;
        return (this.longs[r] >>> (int)c & 1L) == 1L;
    }

    public void remove(long i) {
        int r = (int)(i / 64L);
        long c = i % 64L;
        long[] var10000 = this.longs;
        var10000[r] &= ~(1L << (int)c);
    }
}

三、以下純屬自學(xué)（自己測試，有問題請幫忙指出）

四、BigMap原理

原來如果我們要存儲1，2，3，4四個整數(shù)，就需要new一個長度為4的數(shù)組存儲，如new int[3]，占內(nèi)存就是4x4=16byte。而現(xiàn)在入宮hutool的 IntMap，只需要 new IntMap[1]就夠了，占內(nèi)存1x4=4byte。

而且new IntMap[1]可以存儲0-31這32個整數(shù)。用傳統(tǒng)方法得new int[31]，占內(nèi)存就是32x4=128byte。他們兩個的內(nèi)存占比就是32:1（原始:IntMap）

1.IntMap是怎么存儲的？add(long i)方法

1.1 我們先new IntMap[1]。int=4byte=32bit。所以得到如下32位二進制。

00000000 00000000 00000000 00000000

我們都知道二進制只有0和1，在這里可以這么理解，如下面這樣，代表存入這個0、7、31三個整數(shù)。簡而言之，當(dāng)我們只new 了1字節(jié)（32bit）大小的空間，只要我們存入0-31內(nèi)的某個數(shù)字，二進制對應(yīng)位就會被置為1

10000000 00000000 00000000 10000001

如：

1.2 查看add方法解析

可以發(fā)現(xiàn)他做了以下操作。比如我們要存儲 7 這個數(shù)字

r 代表7存放在index為0 tmp[0] 里

c 代表 7 該存放在tmp[0] 中32bit位哪個位置

著重講 this.ints[r] |= 1 << c (有三步操作)，源碼是 1左移7位后，第8個bit位從0變?yōu)?，如下：

初始 1 的二進制：

00000000 00000000 00000000 00000001

1. 1 左移7位后：

00000000 00000000 00000000 10000000

2. 最后與 ints[0] 進行或運算后得到，如下：

00000000 00000000 00000000 10000000

00000000 00000000 00000000 00000000 ints[0]

結(jié)果：

00000000 00000000 00000000 10000000

3. 第三步，給 ints[0] 賦值（把或運算的值付給ints[0]）

注意：為什么要進行或運算，是因為要保留前面add得值。如此時我們已經(jīng)add了 7 ，此時ints[0]為：

ints[0] = 00000000 00000000 00000000 10000000

我們再往里面 add一個 9 。程序又執(zhí)行到或運算那一步

00000000 00000000 00000010 00000000 新的 add 9 的值

00000000 00000000 00000000 10000000 ints[0] 原來add 7 的值

或運算后，7跟9的值都保存起了。如下：

ints[0] = 00000000 00000000 00000010 10000000

個人理解：

接上面第一步左移7位說，為什么要從1左移 c 位，我的理解：它的設(shè)計思想默認第一個bit位都放余數(shù)為0的數(shù)，如tmp[0]中的整數(shù)0，tmp[1]中的整數(shù) 32。其余數(shù) 位置都要+1bit位。從代碼編寫來說就變成 1<<c

2.contains(long i)方法與remove(long i)方法自己可以根據(jù)以上去驗證理解

五、同理，LongMap也是類似的思想

到此這篇關(guān)于Java中BitMap(位圖)hutool版、IntMap、LongMap的文章就介紹到這了,更多相關(guān)Java BitMap、IntMap、LongMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: