有許多方法可以用來去重，比如使用列表、集合等等，但這些方法通常只適用于一般情況。然而，當涉及到大量數據去重時，常見的 Java Set、List，甚至是 Java 8 的新特性 Stream 流等方式就顯得不太合適了。在處理大量數據的需求場景下，我們不得不提及 BitMap。

什么是BitMap？有什么用？

(1) 基本概念

位圖（BitMap），基本思想就是用一個bit來標記元素，bit是計算機中最小的單位，也就是我們常說的計算機中的0和1，這種就是用一個位來表示的。

所謂位圖，其實就是一個bit數組，即每一個位置都是一個bit，其中的取值可以是0或者1

像上面的這個位圖，可以用來表示1，,4，6：

如果不用位圖的話，我們想要記錄1，4，,6 這三個整型的話，就需要用三個unsigned int，已知每個unsigned int占4個字節，那么就是34 = 12個字節，一個字節有8 bit，那么就是 128 = 96 個bit。

所以，位圖最大的好處就是節省空間。

位圖有很多種用途，特別適合用在去重、排序等場景中，著名的布隆過濾器就是基于位圖實現的。

(2) 位圖的優勢

• 空間效率優勢：為徒極大的節省了存儲空間，對于大量稀疏數據，特別是當元素數量遠大于實際存在的項時，相比較于使用傳統的列表、集合等數據結構，位圖的空間占用極小。
• 查詢速度：由于內存訪問時按字節或字進行的。因此對單個元素的存在性檢查時間復雜度為O(1)，即常量時間，非常快速。
• 批量操作高效：對于批量插入、刪除和查詢操作，尤其是統計范圍內元素的數量，位圖表現出優秀的性能。

(3) 位圖的劣勢

但是位圖也有著一定的限制，那就是他只能表示0和1，無法存儲其他的數字。所以他只適合這種能表示true or false的場景。

BitMap和Int的區別

以Java中的int為例，來對比觀察BitMap的優勢，再Java中，int類型通常需要32位，而BitMap使用1位就可以來標識此元素是否存在，所以可以認為BitMap占用的空間大小只有int類型的1/32，所以有大量數據判重時，使用BitMap也可以實現。

了解了什么是BitMap，那么我們就可以使用BitMap來解決大量數據去重的問題。

40億個無符號整數內存只有1G，如果要去重的話，如何解決

假設40億個無符號整數數據都是10位的話，如果直接使用內存來存儲，大約需要14.9GB 的空間。

• 每個無符號整數通常占用4個字節（32位），因此40億個無符號整數所需要的總字節數位4*4000000000字節。
• 總字節數轉換為GB：4*4000000000 / 1024 / 1024 /1024 = 14.9 GB

考慮到其中有一些重復的數據，即使這樣1G的空間基本上也是不夠的。所以想要實現這個功能可以借助BitMap。

如果使用位圖的話，40億數據存儲所需要的內存大概也就是 476M：

• 40億無符號整數數據的總字節數是4000000000 字節，在位圖中1個10位的無符號整數可以使用1 bit表示，然后1 字節 = 8 位（bit）。
• 4000000000 bit * 1/8  求出字節數，再 / 1024得到占用的KB數，最后/ 1024得到占用的MB數
• 4000000000 * 1 /8 /1024/1024 = 476M

這樣相比于之前的14.9G來說，大大的節省了很多空間。

比如要把數據"714771310"放到BitMap中，就需要找到第714771310這個位置，然后把他設置成1就可以了。

這樣，把40億個數字都放到BitMap之后，所有位置上是1的表示存在，不為1的表示不存在，相同的數據只需要設置一次1就可以了，那么，最終就把所有是1的數字遍歷出來就行了。

BitMap在Java中的使用

BitMap在Java中的具體實現時java.util中的BitSet，BitSet是一個可變大小的位向量，能夠動態增長以容納更多的數據，以下是BitSet基本使用示例：

public class BitmapExample {
    public static void main(String[] args) {
        // 創建一個BitSet實例
        BitSet bitMap = new BitSet();
        // 設置第5個位置為1，表示第5個元素存在
        bitMap.set(5);

        // 檢查第五個位置是否已經設置
        boolean exists = bitMap.get(5);
        
        // 輸出：Element at position 5 exists: true
        System.out.println("Element at position 5 exists: " + exists);

        // 設置從索引10到20的所有位置為1，參數是包含起始點不包含終點的區間
        bitMap.set(10, 21);

        // 計算BitSet中所有位置為1的位的數量，相當于計算設置了的元素個數
        int count = bitMap.cardinality();
        System.out.println("Number of set bits: " + count);

        // 清除第五個位置
        bitMap.clear(5);

        // 判斷位圖是否為空
        boolean isEmpty = bitMap.isEmpty();
        System.out.println("Is the BitSet empty after clearing some bits? " + isEmpty);
        
        
    }
}