快捷導(dǎo)航

Java面試之如何實現(xiàn)10億數(shù)據(jù)判重

更新時間：2024年02月19日 15:10:09 作者：Java中文社群

當(dāng)數(shù)據(jù)量比較大時,使用常規(guī)的方式來判重就不行了,所以這篇文章小編主要來和大家介紹一下Java實現(xiàn)10億數(shù)據(jù)判重的相關(guān)方法,希望對大家有所幫助

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

知識擴展

除了布隆過濾器之外，我們還可以使用 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)勢包括：

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

課后思考

除了布隆過濾器和 BitMap 之外，還有哪些大數(shù)據(jù)量判重的實現(xiàn)方案呢？布隆過濾器實現(xiàn)判重的原理又是啥呢？

知識補充

什么是布隆過濾器？如何實現(xiàn)布隆過濾器？

布隆過濾器（Bloom Filter）是一種空間效率極高的概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷一個元素是否在一個集合中。它基于位數(shù)組和多個哈希函數(shù)的原理，可以高效地進行元素的查詢，而且占用的空間相對較小，如下圖所示：

根據(jù) key 值計算出它的存儲位置，然后將此位置標(biāo)識全部標(biāo)識為 1（未存放數(shù)據(jù)的位置全部為 0），查詢時也是查詢對應(yīng)的位置是否全部為 1，如果全部為 1，則說明數(shù)據(jù)是可能存在的，否則一定不存在。

也就是說，如果布隆過濾器說一個元素不在集合中，那么它一定不在這個集合中；但如果它說一個元素在集合中，則有可能是不存在的（存在誤差）。

1.布隆執(zhí)行過程

布隆過濾器的具體執(zhí)行步驟如下：

在 Redis 中創(chuàng)建一個位數(shù)組，用于存儲布隆過濾器的位向量。
初始化多個哈希函數(shù)，并將每個哈希函數(shù)的計算結(jié)果對應(yīng)的位數(shù)組位置設(shè)置為 1。
添加元素到布隆過濾器時，對元素進行多次哈希計算，并將對應(yīng)的位數(shù)組位置設(shè)置為 1。
查詢元素是否存在時，對元素進行多次哈希計算，并檢查對應(yīng)的位數(shù)組位置是否都為 1。

2.布隆使用場景

布隆過濾器的主要使用場景有以下幾個：

大數(shù)據(jù)量去重：可以用布隆過濾器來進行數(shù)據(jù)去重，判斷一個數(shù)據(jù)是否已經(jīng)存在，避免重復(fù)插入。
緩存穿透：可以用布隆過濾器來過濾掉惡意請求或請求不存在的數(shù)據(jù)，避免對后端存儲的頻繁訪問。
網(wǎng)絡(luò)爬蟲的 URL 去重：可以用布隆過濾器來判斷 URL 是否已經(jīng)被爬取，避免重復(fù)爬取。

3.如何實現(xiàn)布隆過濾器？

在 Redis 中不能直接使用布隆過濾器，但我們可以通過 Redis 4.0 版本之后提供的 modules (擴展模塊) 的方式引入，它的實現(xiàn)步驟如下。

① 打包RedisBloom插件