一、引入依賴

<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é)（自己測(cè)試，有問(wèn)題請(qǐng)幫忙指出）

四、BigMap原理

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

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

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

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

00000000 00000000 00000000 00000000

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

10000000 00000000 00000000 10000001

如：

1.2 查看add方法解析

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

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

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

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

初始 1 的二進(jìn)制：

00000000 00000000 00000000 00000001

1.  1 左移7位后：

00000000 00000000 00000000 10000000

2.  最后與 ints[0] 進(jìn)行或運(yùn)算后得到，如下：

00000000 00000000 00000000 10000000

00000000 00000000 00000000 00000000  ints[0]

結(jié)果 ：

00000000 00000000 00000000 10000000

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

注意：為什么要進(jìn)行或運(yùn)算  ，是因?yàn)橐Ａ羟懊鎍dd得值。如此時(shí)我們已經(jīng)add了 7 ，此時(shí)ints[0]為：

ints[0] = 00000000 00000000 00000000 10000000

我們?cè)偻锩?add一個(gè) 9 。程序又執(zhí)行到或運(yùn)算 那一步

00000000 00000000 00000010 00000000   新的 add  9  的值

00000000 00000000 00000000 10000000  ints[0]  原來(lái)add 7 的值

或運(yùn)算后，7跟9的值都保存起了。如下：

ints[0] = 00000000 00000000 00000010 10000000

個(gè)人理解：

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

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

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

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

最新評(píng)論