快捷導(dǎo)航

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

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

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

所以數(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)參開(kāi)文末補(bǔ)充內(nèi)容

知識(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ì)包括：

空間效率優(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)存訪問(wèn)是按字節(jié)或字進(jìn)行的，因此對(duì)單個(gè)元素的存在性檢查時(shí)間復(fù)雜度為 O(1)，即常量時(shí)間，非常快速。
批量操作高效：對(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);
    }
}

課后思考

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

知識(shí)補(bǔ)充

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

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

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

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

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

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

在 Redis 中創(chuàng)建一個(gè)位數(shù)組，用于存儲(chǔ)布隆過(guò)濾器的位向量。
初始化多個(gè)哈希函數(shù)，并將每個(gè)哈希函數(shù)的計(jì)算結(jié)果對(duì)應(yīng)的位數(shù)組位置設(shè)置為 1。
添加元素到布隆過(guò)濾器時(shí)，對(duì)元素進(jìn)行多次哈希計(jì)算，并將對(duì)應(yīng)的位數(shù)組位置設(shè)置為 1。
查詢?cè)厥欠翊嬖跁r(shí)，對(duì)元素進(jìn)行多次哈希計(jì)算，并檢查對(duì)應(yīng)的位數(shù)組位置是否都為 1。

2.布隆使用場(chǎng)景

布隆過(guò)濾器的主要使用場(chǎng)景有以下幾個(gè)：

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

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

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

① 打包RedisBloom插件