Java算法之位圖的概念和實現(xiàn)詳解

更新時間：2023年10月26日 10:44:43 作者：CodeJiao

這篇文章主要介紹了Java算法之位圖的概念和實現(xiàn)詳解,位圖可以利用每一位來對應一個值,比如可以利用int類型的數(shù)去存儲0~31這個集合的數(shù)字,如果該集合內(nèi)的數(shù)字存在,則把對應的位設置位1默認為0,需要的朋友可以參考下

位圖的介紹

位圖可以利用每一位來對應一個值，比如可以利用int類型的數(shù)去存儲0~31這個集合的數(shù)字。如果該集合內(nèi)的數(shù)字存在，則把對應的位設置位1（默認為0）。

在這里插入圖片描述

如果要存儲的集合元素范圍超過了32個，則可以用int數(shù)組去實現(xiàn)位圖，第一個數(shù)組元素保存0~31的元素，第二個數(shù)組元素保存32~63的數(shù)組元素。

位圖的好處就是可以節(jié)省大量的空間，缺點是實現(xiàn)比較復雜。

注意：

并不是說int類型的位圖只可以存儲0~31的集合元素，也可以存儲例如5~36的元素，在存儲的時候設置一下規(guī)則就行了，1位對應5，2位對應6，…32位對應36。

位圖的實現(xiàn)

我們先把完整的實現(xiàn)代碼放在這里，后面會分析里面的具體實現(xiàn)。

public class BitMap {
    private final long[] bitMap;

    /**
     * 構(gòu)造函數(shù)
     *
     * @param max 位圖存儲著 [0,max]的元素
     */
    public BitMap(int max) {
        bitMap = new long[(max + 64) >> 6];
    }

    /**
     * 往位圖里面添加元素
     *
     * @param num 待添加的元素
     */
    public void add(int num) {
        bitMap[num >> 6] |= (1L << (num & 63));
    }

    /**
     * 刪除位圖里面的元素
     *
     * @param num 待刪除的元素
     */
    public void delete(int num) {
        bitMap[num >> 6] &= ~(1L << (num & 63));
    }

    /**
     * 觀察目標元素num在位圖中是存在
     *
     * @param num 目標元素
     * @return 存在返回1，否則返回0
     */
    public boolean contains(int num) {
        return (bitMap[num >> 6] & (1L << (num & 63))) != 0;
    }
}

構(gòu)造函數(shù)

代碼實現(xiàn)：

    /**
     * 構(gòu)造函數(shù)
     *
     * @param max 位圖存儲著 [0,max]的元素
     */
    public BitMap(int max) {
        bitMap = new long[(max + 64) >> 6];
    }

分析：

在這里插入圖片描述

添加元素

代碼實現(xiàn)：

    /**
     * 往位圖里面添加元素
     *
     * @param num 待添加的元素
     */
    public void add(int num) {
        bitMap[num >> 6] |= (1L << (num & 63));
    }

分析：

在這里插入圖片描述

刪除元素

代碼實現(xiàn)：

    /**
     * 刪除位圖里面的元素
     *
     * @param num 待刪除的元素
     */
    public void delete(int num) {
        bitMap[num >> 6] &= ~(1L << (num & 63));
    }

分析：

刪除元素與添加元素類似，只是需要把該位置元素設置為0，而不是1。這里使用&元素去實現(xiàn)。

在這里插入圖片描述

判斷元素是否存在

代碼實現(xiàn)：

    /**
     * 觀察目標元素num在位圖中是存在
     *
     * @param num 目標元素
     * @return 存在返回1，否則返回0
     */
    public boolean contains(int num) {
        return (bitMap[num >> 6] & (1L << (num & 63))) != 0;
    }

分析：

在這里插入圖片描述