Java數(shù)據(jù)結(jié)構(gòu)之位圖的簡單實(shí)現(xiàn)和使用

更新時(shí)間：2023年05月05日 14:40:07 作者：愿榮

位圖,?是一種非常常見的結(jié)構(gòu),?它使用每個(gè)二進(jìn)制位來存放一個(gè)值的狀態(tài),?就類似于?Java?當(dāng)中?HashSet?存儲(chǔ)元素的功能。本文主要來介紹一下位圖的簡單實(shí)現(xiàn)和使用，需要的可以參考一下

1. 什么是位圖

位圖, 是一種非常常見的結(jié)構(gòu), 它使用每個(gè)二進(jìn)制位來存放一個(gè)值的狀態(tài), 就類似于 Java 當(dāng)中 HashSet 存儲(chǔ)元素的功能.

在 Java 當(dāng)中, 可以使用HashSet完成如下操作:

add(T v): 添加一個(gè)元素到 HashSet 中, 重復(fù)則覆蓋.contains(T v): 判斷元素在 HashSet 中是否存在.remove(T v): 從 HashSet 中刪除指定元素.

但如果我們的數(shù)據(jù)范圍是固定的, 使用位圖就比使用HashSet更省空間, 那么下面就來介紹一下位圖如何實(shí)現(xiàn).

在 Java 中, 一個(gè) int 類型的整數(shù)是 4 字節(jié), 就可以表示 32 個(gè) bit位, 所以, 如果數(shù)據(jù)范圍是 [0, 31], 就可以直接使用一個(gè) int 類型的空間來完成上述三個(gè)操作.

例如:

add(5) 這個(gè)操作, 就是在一個(gè) int 類型空間中, 把第 5 個(gè)二進(jìn)制位設(shè)置為 1;

繼續(xù)執(zhí)行 add(7) 這個(gè)操作, 就是在和上面同一個(gè) int 類型空間中, 把第 7 個(gè)二進(jìn)制位設(shè)置為 1;

contains(5) 這個(gè)操作, 就是判斷第5個(gè)二進(jìn)制位是 0 還是 1, 如果是 1, 就說明 4 存在, 如果是 0 , 就說明 4 不存在;

remove(7) 這個(gè)操作, 就是把 7 號(hào)位置置為 0;

如果數(shù)據(jù)范圍是 0 ~ 1023, 則可以用一個(gè) int 類型的數(shù)組來表示, 這個(gè)數(shù)組只需要 32 個(gè)元素即可; 因?yàn)?32 個(gè) int 類型元素, 可以表示 1024 位, 正好可以覆蓋 0 ~ 1023 范圍中的所有數(shù)字; 對(duì)于0 ~ 1023中任意一個(gè)數(shù) num, num 在數(shù)組中存在第num / 32號(hào)下標(biāo)元素中的第num % 32位中.

例如當(dāng) num = 37 時(shí), num 應(yīng)該在數(shù)組 1 號(hào) (即: 37 / 32) 下標(biāo)的元素的第 5 個(gè) bit (即: 37 % 32) 位上.

2. 位圖的簡單實(shí)現(xiàn)

為了增大位圖可以表示的范圍, 我們可以使用 long 類型來替代 int 類型, 一個(gè)long 類型是 64 個(gè) bit位置, 就可以表示64個(gè)數(shù), 下面介紹位圖的簡單實(shí)現(xiàn), 主要實(shí)現(xiàn)上面提到的增, 刪, 查三個(gè)方法.

首先定義好位圖類的大框架, 如下:

public static class BitMap {
    private final long[] bits;

    // 位圖初始化
    public BitMap(int max) {
    }

    // 添加一個(gè)元素
    public void add(int num) {
    }

    // 刪除一個(gè)元素
    public void remove(int num) {
    }

    // 判斷一個(gè)元素是否在位圖中
    public boolean contains(int num) {
    }
}

注: 這里只簡單考慮非負(fù)數(shù)存到位圖中, 對(duì)于負(fù)數(shù)的情況, 其實(shí)也是可以轉(zhuǎn)換成正數(shù)來處理的; 比如: -3~6, 可以轉(zhuǎn)換成0~9, 0 就代表 -3, 以此類推, 一一對(duì)應(yīng).

首先是位圖的初始化, 要根據(jù)數(shù)據(jù)范圍確定位圖應(yīng)該開辟多大的數(shù)組空間.

由于我們這里是 long 類型的, 所以, 對(duì)于 0 ~ x 范圍來說, 就需要準(zhǔn)備 (x + 64) / 64 這么大的 long 類型數(shù)組.

位圖中增加一個(gè)元素, 比如我們要增加 53 這個(gè)元素, 先定位它是數(shù)組中的哪個(gè)元素, 即 53 / 64 = 0, 就是在第 0 號(hào)下標(biāo)位置的元素, 再定位是這個(gè)元素中的第幾個(gè)bit位, 即: 53 % 64 = 11, 即第 11 個(gè) bit 位, 我們可以用 1L << 11 后的值與 | 上 bits[0] 即可 (將相應(yīng)二進(jìn)制位的值修改為1, 不影響其他位).

代碼實(shí)現(xiàn)如下:

public void add(int num) {
    bits[num / 64] |= (1L << (num % 64));
}

由于 num / 64其實(shí)就是 num >> 6, num % 64其實(shí)就是num & 63 (只適用于 2 的 n 次方), 位運(yùn)算是比算術(shù)運(yùn)算效率要高的, 所以我們可以將 add 方法可以改寫成如下形式:

// 向位圖中添加值, 將對(duì)應(yīng)的二進(jìn)制位改成1即可
public void add(int num) {
    // 1. num / 64 找到該數(shù)應(yīng)該存在數(shù)組的哪個(gè)元素上
    // 2. num % 64 找到該數(shù)應(yīng)該存到元素的第幾個(gè)二進(jìn)制位置上(從0位置開始)
    // 3. ( 1L << (num % 64) ) | bits[num / 64] 就是將相應(yīng)二進(jìn)制位的值修改為1, 不影響其他位
    // 要注意1后面必須加上L, 1默認(rèn)是一個(gè)int類型的數(shù), 是沒有64位的, 移位運(yùn)算就可能會(huì)出錯(cuò)
    //  num / 64       1L << (num % 64)
    bits[num >> 6] |= (1L << (num & 63));
}

位圖中刪除一個(gè)元素, 其實(shí)就是把對(duì)應(yīng)位置的二進(jìn)制位修改為 0, 其他位置保持不變, 通過

~(1L << (num & 63));

可以預(yù)先得到一個(gè)除目標(biāo)位置是 0, 其他位置都是 1 的數(shù).

然后通過這個(gè)數(shù)去去 & 數(shù)組目標(biāo)位置的元素, 即可把對(duì)應(yīng)位置的 1 改為 0, 其他位置不變.

// 在集合中刪除記錄, 將對(duì)應(yīng)二進(jìn)制位改成0即可
public void remove(int num) {
    // 1. num / 64 找到該數(shù)應(yīng)該存在數(shù)組的哪個(gè)元素上
    // 2. num % 64 找到該數(shù)應(yīng)該存到元素的第幾個(gè)二進(jìn)制位置上(從0位置開始)
    // 3. ~( 1L << (num % 64) ) 就是在把0001000變成1110111這樣的
    // 4. 把 3 得到的結(jié)果再 & 到 bits[num >> 6] 就行了
    bits[num >> 6] &= ~(1L << (num & 63));
}

位圖中是否包含某個(gè)元素, 其實(shí)就是判斷對(duì)應(yīng)位置是 0 還是 1, 如果是 1, 就說明存在, 如果是 0, 則不存在.

public boolean contains(int num) {
    return (bits[num >> 6] & (1L << (num & 63))) != 0;
}

位圖的完整代碼見:

// 位圖的簡單實(shí)現(xiàn)
public class BitMap {
    private long[] bits;
    // 傳入集合要保存的最大數(shù)值
    public BitMap(int max) {
                           // max / 64 + 1
        this.bits = new long[(max >> 6) + 1];
    }
    // 向位圖中添加值, 將對(duì)應(yīng)的二進(jìn)制位改成1即可
    public void add(int num) {
        // 1. num / 64 找到該數(shù)應(yīng)該存在數(shù)組的哪個(gè)元素上
        // 2. num % 64 找到該數(shù)應(yīng)該存到元素的第幾個(gè)二進(jìn)制位置上(從0位置開始)
        // 3. ( 1L << (num % 64) ) | bits[num / 64] 就是將相應(yīng)二進(jìn)制位的值修改為1, 不影響其他位
        // 要注意1后面必須加上L, 1默認(rèn)是一個(gè)int類型的數(shù), 是沒有64位的, 移位運(yùn)算就可能會(huì)出錯(cuò)
        //  num / 64       1L << (num % 64)
        bits[num >> 6] |= (1L << (num & 63));
    }
    // 在集合中刪除記錄, 將對(duì)應(yīng)二進(jìn)制位改成0即可
    public void remove(int num) {
        // 1. num / 64 找到該數(shù)應(yīng)該存在數(shù)組的哪個(gè)元素上
        // 2. num % 64 找到該數(shù)應(yīng)該存到元素的第幾個(gè)二進(jìn)制位置上(從0位置開始)
        // 3. ~( 1L << (num % 64) ) 就是在把0001000變成1110111這樣的
        // 4. 把 3 得到的結(jié)果再 & 到 bits[num >> 6] 就行了
        bits[num >> 6] &= ~(1L << (num & 63));
    }
    // 查看位圖中是否記錄了某個(gè)值
    public boolean contains(int num) {
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }
}

3. 測試位圖代碼

通過實(shí)現(xiàn)的位圖和 Java 自帶的 HashSet 進(jìn)行對(duì)比著進(jìn)行測試, 測試代碼如下:

import java.util.HashSet;
public class BitMap {
    private long[] bits;
    public BitMap(int max) {
        bits = new long[(max + 64) >> 6];
    }
    public void add(int num) {
        bits[num >> 6] |= (1L << (num & 63));
    }
    public void remove(int num) {
        bits[num >> 6] &= ~(1L << (num & 63));
    }
    public static void main(String[] args) {
        System.out.println("測試開始!");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTime = 10000000;
        for (int i = 0; i < testTime; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.333) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {
                bitMap.remove(num);
                set.remove(num);
            } else {
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("出錯(cuò)了!");
                    break;
                }
            }
        }
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("出錯(cuò)了!");
            }
        }
        System.out.println("測試結(jié)束!");
    }
}

執(zhí)行代碼, 可以看到看到結(jié)果中是沒有打印錯(cuò)錯(cuò)誤信息的, 所以上面位圖的邏輯實(shí)現(xiàn)是正確的.