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

什么是BitMap？有什么用？

(1) 基本概念

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

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

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

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

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

位圖有很多種用途，特別適合用在去重、排序等場(chǎng)景中，著名的布隆過濾器就是基于位圖實(shí)現(xiàn)的。

(2) 位圖的優(yōu)勢(shì)

• 空間效率優(yōu)勢(shì)：為徒極大的節(jié)省了存儲(chǔ)空間，對(duì)于大量稀疏數(shù)據(jù)，特別是當(dāng)元素?cái)?shù)量遠(yuǎn)大于實(shí)際存在的項(xiàng)時(shí)，相比較于使用傳統(tǒng)的列表、集合等數(shù)據(jù)結(jié)構(gòu)，位圖的空間占用極小。
• 查詢速度：由于內(nèi)存訪問時(shí)按字節(jié)或字進(jìn)行的。因此對(duì)單個(gè)元素的存在性檢查時(shí)間復(fù)雜度為O(1)，即常量時(shí)間，非常快速。
• 批量操作高效：對(duì)于批量插入、刪除和查詢操作，尤其是統(tǒng)計(jì)范圍內(nèi)元素的數(shù)量，位圖表現(xiàn)出優(yōu)秀的性能。

(3) 位圖的劣勢(shì)

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

BitMap和Int的區(qū)別

以Java中的int為例，來對(duì)比觀察BitMap的優(yōu)勢(shì)，再Java中，int類型通常需要32位，而BitMap使用1位就可以來標(biāo)識(shí)此元素是否存在，所以可以認(rèn)為BitMap占用的空間大小只有int類型的1/32，所以有大量數(shù)據(jù)判重時(shí)，使用BitMap也可以實(shí)現(xiàn)。

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

40億個(gè)無符號(hào)整數(shù)內(nèi)存只有1G，如果要去重的話，如何解決

假設(shè)40億個(gè)無符號(hào)整數(shù)數(shù)據(jù)都是10位的話，如果直接使用內(nèi)存來存儲(chǔ)，大約需要14.9GB 的空間。

• 每個(gè)無符號(hào)整數(shù)通常占用4個(gè)字節(jié)（32位），因此40億個(gè)無符號(hào)整數(shù)所需要的總字節(jié)數(shù)位4*4000000000字節(jié)。
• 總字節(jié)數(shù)轉(zhuǎn)換為GB：4*4000000000 / 1024 / 1024 /1024 = 14.9 GB

考慮到其中有一些重復(fù)的數(shù)據(jù)，即使這樣1G的空間基本上也是不夠的。所以想要實(shí)現(xiàn)這個(gè)功能可以借助BitMap。

如果使用位圖的話，40億數(shù)據(jù)存儲(chǔ)所需要的內(nèi)存大概也就是 476M：

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

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

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

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

BitMap在Java中的使用

BitMap在Java中的具體實(shí)現(xiàn)時(shí)java.util中的BitSet，BitSet是一個(gè)可變大小的位向量，能夠動(dòng)態(tài)增長(zhǎng)以容納更多的數(shù)據(jù)，以下是BitSet基本使用示例：

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

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

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

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

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

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