當(dāng)數(shù)據(jù)量比較大時，使用常規(guī)的方式來判重就不行了。

例如，使用 MySQL 數(shù)據(jù)庫判重，或使用 List.contains() 或 Set.contains() 判重就不可行，因為 MySQL 在數(shù)據(jù)量大時查詢就會非常慢，而數(shù)據(jù)庫又是及其珍貴的全局?jǐn)?shù)據(jù)庫資源。

《阿里巴巴Java開發(fā)手冊》上也說了，如果單表數(shù)據(jù)量超過 500 萬或 2GB 時就建議分庫分表了，如下圖所示：

圖片

所以數(shù)據(jù)庫去重顯然是不行的。而使用集合也是不合適的，因為數(shù)據(jù)量太大，使用集合會導(dǎo)致內(nèi)存不夠用或內(nèi)存溢出和 Full GC 頻繁等問題，所以此時我們的解決方案通常是采用布隆過濾器來實現(xiàn)判重，布隆過濾器的詳情請訪問：如何實現(xiàn)布隆過濾器？

知識擴展

除了布隆過濾器之外，我們還可以使用 BitMap（位圖）的數(shù)據(jù)類型來實現(xiàn)判重。

位圖（BitMap）是一種數(shù)據(jù)結(jié)構(gòu)，用于表示一個特定范圍內(nèi)的元素是否存在或者某種狀態(tài)，通常用二進制位來表示。在位圖中，每一個位只能是 0 或 1，分別表示元素不存在或存在。位圖通常用一個 bit 數(shù)組來實現(xiàn)，每個 bit 位對應(yīng)一個元素，如下圖所示：

圖片

其中，上圖中的 1 表示有值，上面 BitMap 描述的值是 1,3,5。

BitMap 優(yōu)點分析

位圖的優(yōu)勢包括：

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

BitMap VS int

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

PS：布隆過濾器的底層就是基于 BitMap 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。

BitMap 在 Java 中的使用

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

import java.util.BitSet;

public class BitmapExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個BitSet實例
        BitSet bitmap = new BitSet();

        // 設(shè)置第5個位置為1，表示第5個元素存在
        bitmap.set(5);

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

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

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

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

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