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

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

《阿里巴巴Java開(kāi)發(fā)手冊(cè)》上也說(shuō)了，如果單表數(shù)據(jù)量超過(guò) 500 萬(wàn)或 2GB 時(shí)就建議分庫(kù)分表了，如下圖所示：

圖片

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

知識(shí)擴(kuò)展

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

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

圖片

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

BitMap 優(yōu)點(diǎn)分析

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

1. 空間效率優(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)，位圖占用的空間極小。
2. 查詢速度：由于內(nèi)存訪問(wèn)是按字節(jié)或字進(jìn)行的，因此對(duì)單個(gè)元素的存在性檢查時(shí)間復(fù)雜度為 O(1)，即常量時(shí)間，非常快速。
3. 批量操作高效：對(duì)于批量插入、刪除和查詢操作，尤其是統(tǒng)計(jì)某一范圍內(nèi)元素的數(shù)量，位圖表現(xiàn)出優(yōu)秀的性能。

BitMap VS int

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

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

BitMap 在 Java 中的使用

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

import java.util.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);

        // 檢查第5個(gè)位置是否已設(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ù)是包含起始點(diǎn)和不包含終點(diǎn)的區(qū)間

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

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

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