點陣圖的使用與實現

作者：Grey

原文地址：

部落格園：點陣圖的使用與實現

CSDN：點陣圖的使用與實現

說明

本文內容使用的程式語言是 Java。其他語言有類似的資料結構。

點陣圖的使用

在 Java 中，使用HashSet可以實現如下操作：

add(T v)

加入一個元素到HashSet中，重複則覆蓋。

contains(T v)

判斷一個元素是否加入過HashSet。

remove(T v)

從HashSet中刪除一個元素。

如果資料範圍固定，使用點陣圖比使用HashSet省空間。

在 Java 中，一個 int 型別的整數可以表示 32 個 bit，所以，如果資料範圍0 ~ 31，可以直接用一個 int 型別的數來完成上述三個操作。

比如：

add(4)這個操作，就是在如下 int 型別數（二進位制表示）中，第 4 號位置設定為 1。如下圖

繼續執行add(7)這個操作，就是在如下 int 型別數（二進位制表示）中，第 7 號位置設定為 1。如下圖

contains(4)這個操作，就是判斷 4 號位置是 0 還是 1，如果是 1，就說明 4 存在，如果是 0 ，說明 4 不存在。

remove(7)這個操作，就是把 7 號位置置為 0。如下效果

如果資料範圍是 0 ~ 1023，則可以用一個 int 型別陣列來表示，這個陣列只需要 32 個元素即可。因為 32 個 int 型別元素，可以表示 1024 位，正好可以覆蓋資料範圍中的所有數位。對於0 ~ 1023中任意一個數 num，num在陣列中存在第num / 32個元素中的第num % 32位中。

舉例說明：

num = 37，客觀上，num 應該在如下位置：

在 1 號（37 / 32）陣列元素的第 5 號（ 37 % 32）位置。

點陣圖的實現

為了擴大表示範圍，我們可以使用 long 型別來替代 int 型別，因為 long 型別可以表達 64 個 bit，思路還是和如上一樣。現在說明如何實現上述三個方法。

先把點陣圖的資料結構和相關方法定義好

public static class BitMap {

        // 使用每個位置的資訊。
        private long[] bits;

        public BitMap(int max) {
            // TODO
            // 點陣圖初始化
        }

        public void add(int num) {
            // TODO
            // 新增一個元素
        }

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

        public boolean contains(int num) {
            // TODO
            // 判斷一個元素是否在點陣圖中
        }
    }

注：我們這裡只考慮非負數，對於負數的情況，也可以轉換成正數來處理，比如：-3~6，可以轉換成0~9。

首先是點陣圖的初始化，即如何根據資料範圍確定點陣圖應該開闢多大的陣列？

由於是 long 型別，所以，對於 0 ~ x 區間來說，需要準備

(x + 64) / 64

這麼大的 long 型別陣列。

點陣圖中增加一個元素，比如我們要增加 53 這個元素，先定位它是陣列中的哪個元素，即53 / 64 = 0，第 0 號位置的元素，再定位是這個元素中的第幾位，即：53 % 64 = 11，即第 11 位，我們可以用 1L << 11後的值| bit[0]即可，程式碼實現如下

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

由於 num / 64其實就是 num >> 6，

num % 64其實就是num & 63，

由於位運算比算術運算效率要高，所以add方法可以進一步寫成如下形式

        public void add(int num) {
            //  bits[num / 64] |= (1L << (num % 64));
            // num % 64 ---> num & 63
            // 只適用於 2 的 n 次方
            bits[num >> 6] |= (1L << (num & 63));
        }

點陣圖中刪除一個元素，其實就是把對應位置的二進位制位置為 0，其他位置保持不變，通過

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

可以預先得到一個除目標位置是 0，其他位置都是 1 的數。

然後通過這個數去 &上陣列目標位置的元素，即可把對應位置的 1 改為 0，其他位置不變。

        public void remove(int num) {
            bits[num >> 6] &= ~(1L << (num & 63));
        }

點陣圖中是否包含某個元素，其實就是判斷對應位置是 0 還是 1，如果是 0 ，就說明存在，不是 0 ，則不存在。

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

點陣圖的完整程式碼見

    public static class BitMap {

        private long[] bits;

        public BitMap(int max) {
            // 準備多少個整數？ 0 ~ 63 需要1個整數
            // >> 6 就是 除以 64
            bits = new long[(max + 64) >> 6];
        }

        public void add(int num) {
            //  bits[num / 64] |= (1L << (num % 64));
            // num % 64 ---> num & 63
            // 只適用於 2 的 n 次方
            bits[num >> 6] |= (1L << (num & 63));
        }

        public void remove(int num) {
            bits[num >> 6] &= ~(1L << (num & 63));
        }

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

測試

通過實現的點陣圖和 Java 自帶的 HashSet 進行對比測試，可以判斷我們寫的點陣圖是否正確，測試程式碼如下

package snippet;

import java.util.HashSet;
import java.util.Set;


public class Code_0009_BitMap {

   public static void main(String[] args) {
        System.out.println("測試開始！");
        int max = 70000;
        BitMap bitMap = new BitMap(max);
        Set<Integer> set = new HashSet<>();
        int testTime = 90000000;
        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("Oops!");
                    break;
                }
            }
        }
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("測試結束！");
    }
}

執行，未列印報錯資訊，說明我們的演演算法正確。

演演算法和資料結構筆記

參考資料

演演算法和資料結構新手班-左程雲

點陣圖的使用與實現

點陣圖的使用與實現

說明

點陣圖的使用

點陣圖的實現

測試

更多

參考資料