前言介紹

在學(xué)習(xí)之前的數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們使用的數(shù)據(jù)量都不是很大，但是在生活中，我們常常面臨著要處理大量數(shù)據(jù)結(jié)果并得出最終結(jié)果，那么有沒有什么數(shù)據(jù)結(jié)構(gòu)可以幫助我們實(shí)現(xiàn)這樣的功能呢？

那么在開始學(xué)習(xí)處理大量數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)之前，先讓我們看一下本文大致的講解內(nèi)容：

位圖      

圖的概念

首先我們要學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)就是位圖，那么讀者會(huì)發(fā)問(wèn)了？什么是位圖呢？以下是位圖的概念：

位圖是一種空間優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，適合用于表示大量數(shù)據(jù)的存在性。其基本思想是將每個(gè)數(shù)據(jù)用二進(jìn)制的“0”或“1”表示，“1”表示數(shù)據(jù)存在，“0”表示數(shù)據(jù)不存在。位圖特別適合用于對(duì)海量整數(shù)數(shù)據(jù)進(jìn)行存在性檢查或排序操作。

如圖：

通過(guò)上述的描述，相信讀者對(duì)位圖有了一定的了解，在了解了位圖的定義之后，讓我們用一個(gè)實(shí)例再來(lái)說(shuō)明一下位圖的作用：

假設(shè)有40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，我們需要判斷某個(gè)數(shù)是否存在于這40億個(gè)數(shù)中。通常的解決方法可能是將數(shù)據(jù)存儲(chǔ)在數(shù)組或列表中，然后進(jìn)行遍歷或使用二分查找。然而，這兩種方式的時(shí)間復(fù)雜度較高，而位圖通過(guò)將每個(gè)整數(shù)映射到相應(yīng)的比特位，能以較低的空間消耗實(shí)現(xiàn)高效查詢。如上例，假設(shè)數(shù)據(jù)集中有40億個(gè)整數(shù)，使用位圖只需要約512MB的空間即可完成數(shù)據(jù)存儲(chǔ)和查詢。

至此，我們就對(duì)位圖有了初步的了解了！

位圖的實(shí)現(xiàn)

當(dāng)我們了解了位圖是什么之后，現(xiàn)在讓我們自我實(shí)現(xiàn)一下位圖。

——位圖的核心是將整數(shù)映射到一個(gè)數(shù)組的特定位置并通過(guò)位操作來(lái)設(shè)置或獲取該位置的值。下面是位圖實(shí)現(xiàn)的代碼：

public class MyBitSet {
    private byte[] elem;
    private int usedSize;
    // 構(gòu)造函數(shù)，初始化位圖大小
    public MyBitSet(int n) {
        elem = new byte[n / 8 + 1]; // 位圖大小：n個(gè)比特位
    }
    // 設(shè)置某一位為1，表示對(duì)應(yīng)的值存在
    public void set(int val) {
        int arrayIndex = val / 8;
        int bitIndex = val % 8;
        elem[arrayIndex] |= (1 << bitIndex);
        usedSize++;
    }
    // 檢查某個(gè)值是否存在
    public boolean get(int val) {
        int arrayIndex = val / 8;
        int bitIndex = val % 8;
        return (elem[arrayIndex] & (1 << bitIndex)) != 0;
    }
    // 重置某一位為0，表示對(duì)應(yīng)的值不存在
    public void reSet(int val) {
        int arrayIndex = val / 8;
        int bitIndex = val % 8;
        elem[arrayIndex] &= ~(1 << bitIndex);
        usedSize--;
    }
    // 獲取已使用的比特位數(shù)量
    public int getUsedSize() {
        return usedSize;
    }
}

根據(jù)上邊的注釋，我們可以很好的理解如何去實(shí)現(xiàn)一個(gè)位圖，不過(guò)在此我們還是對(duì)上述的代碼進(jìn)行解釋：

• elem 數(shù)組用于存儲(chǔ)比特位信息，每個(gè)字節(jié)（8位）可存儲(chǔ)8個(gè)整數(shù)的存在狀態(tài)。
• set() 方法通過(guò)位運(yùn)算將某一位設(shè)置為1。
• get() 方法通過(guò)按位與運(yùn)算檢查某位是否為1，從而判斷對(duì)應(yīng)的整數(shù)是否存在。
• reSet() 方法則將某一位重置為0，表示數(shù)據(jù)不存在。

這樣我們就了解了如何去自我實(shí)現(xiàn)位圖了！

位圖的應(yīng)用

了解完了什么是位圖和如何去實(shí)現(xiàn)一個(gè)位圖之后，讀者可以會(huì)發(fā)問(wèn)到：位圖除了可以處理大量數(shù)據(jù)之外，位圖在生活中還有什么用處呢？

以下為位圖的一些應(yīng)用場(chǎng)景：

• 快速判斷數(shù)據(jù)是否存在：例如，在大數(shù)據(jù)集群中判斷某個(gè)用戶ID是否存在。
• 數(shù)據(jù)去重：通過(guò)位圖可以快速判斷某數(shù)據(jù)是否已經(jīng)存在，從而避免重復(fù)操作。
• 集合運(yùn)算：位圖能夠高效地實(shí)現(xiàn)集合的并集、交集等操作，尤其適合用于處理大規(guī)模的集合數(shù)據(jù)。
• 排序和去重：位圖可以用于對(duì)大量整數(shù)進(jìn)行排序和去重操作，例如，系統(tǒng)中磁盤塊的標(biāo)記操作。

這樣我們就了解了位圖的應(yīng)用了！

布隆過(guò)濾器

同位圖一樣，在正式開始學(xué)習(xí)布隆過(guò)濾器之前，先讓我們了解一下什么是布隆過(guò)濾器

布隆過(guò)濾器的概念

布隆過(guò)濾器是一種概率型的數(shù)據(jù)結(jié)構(gòu)，主要用于集合查詢。與位圖不同，布隆過(guò)濾器能夠高效地判斷某個(gè)元素是否“可能存在”或“肯定不存在”。它的特點(diǎn)是通過(guò)多個(gè)哈希函數(shù)將元素映射到位數(shù)組的不同位置，并設(shè)置對(duì)應(yīng)比特位為1。當(dāng)查詢一個(gè)元素時(shí)，如果所有哈希函數(shù)映射的比特位都為1，則認(rèn)為該元素“可能存在”；若有一個(gè)比特位為0，則該元素“肯定不存在”。

如圖：

光看上述的文字解釋可能有點(diǎn)晦澀難懂，那么這里我們使用一個(gè)生活中的案例來(lái)對(duì)其進(jìn)行解釋：

想象你在家里開派對(duì)，邀請(qǐng)了50位朋友，但你不記得是否某位朋友已經(jīng)到達(dá)。你可以通過(guò)查看他們是否簽了名（簽名簿）來(lái)判斷。每個(gè)朋友到達(dá)后，你會(huì)要求他們簽名在一個(gè)特定的位置上，這類似于哈希函數(shù)的映射。如果你檢查到所有他們應(yīng)簽的位都已經(jīng)被簽了，那就可能意味著他們已經(jīng)來(lái)過(guò)了，但也可能是誤判。

相信通過(guò)上述的解釋之后，讀者可以對(duì)布隆過(guò)濾器有了更好的理解！

布隆過(guò)濾器的實(shí)現(xiàn)

了解完了布隆過(guò)濾器的定義之后，現(xiàn)在讓我們自我實(shí)現(xiàn)一個(gè)布隆過(guò)濾器。

布隆過(guò)濾器的基本實(shí)現(xiàn)包含一個(gè)位數(shù)組和多個(gè)不同的哈希函數(shù)。每個(gè)哈希函數(shù)將輸入的元素映射到位數(shù)組的一個(gè)位置，并將該位置的比特位設(shè)置為1。

下面是實(shí)現(xiàn)布隆過(guò)濾器的代碼：

import java.util.BitSet;
// 簡(jiǎn)單哈希類
class SimpleHash {
    private int cap; // 哈希表的大小
    private int seed; // 哈希種子
    // 構(gòu)造函數(shù)，初始化哈希表大小和種子
    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }
    // 哈希函數(shù)
    public int hash(String value) {
        int result = 0;
        int len = value.length();
        // 遍歷字符串的每一個(gè)字符
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i); // 計(jì)算哈希值
        }
        // 返回哈希值與 cap-1 的位與操作結(jié)果
        return (cap - 1) & result;
    }
}
// 布隆過(guò)濾器類
public class BloomFilter {
    private static final int DEFAULT_SIZE = 1 << 24; // 位數(shù)組大小
    private static final int[] seeds = {5, 7, 11, 13, 31, 37, 61}; // 哈希種子
    private BitSet bits = new BitSet(DEFAULT_SIZE); // 位數(shù)組
    private SimpleHash[] func = new SimpleHash[seeds.length]; // 哈希函數(shù)數(shù)組
    // 構(gòu)造函數(shù)，初始化哈希函數(shù)
    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); // 根據(jù)種子初始化 SimpleHash
        }
    }
    // 插入數(shù)據(jù)
    public void set(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value)); // 使用每個(gè)哈希函數(shù)設(shè)置位
        }
    }
    // 查詢數(shù)據(jù)是否存在
    public boolean contains(String value) {
        for (SimpleHash f : func) {
            if (!bits.get(f.hash(value))) {
                return false; // 只要有一個(gè)哈希函數(shù)返回 false，就說(shuō)明不在集合中
            }
        }
        return true; // 有可能誤判
    }
    // 主函數(shù)，用于測(cè)試
    public static void main(String[] args) {
        BloomFilter filter = new BloomFilter();
        filter.set("test"); // 插入字符串 "test"
        System.out.println(filter.contains("test")); // 輸出: true，表示 "test" 存在
        System.out.println(filter.contains("hello")); // 輸出: false，表示 "hello" 不存在
    }
}

代碼解釋：

• SimpleHash 類實(shí)現(xiàn)了哈希函數(shù)，通過(guò)不同的種子（seed）保證多個(gè)哈希函數(shù)的多樣性。
• BloomFilter 類使用位數(shù)組和多個(gè)哈希函數(shù)實(shí)現(xiàn)數(shù)據(jù)的插入與查詢操作。set() 方法將數(shù)據(jù)插入布隆過(guò)濾器，而 contains() 方法則檢查數(shù)據(jù)是否可能存在。
• 布隆過(guò)濾器的查詢可能存在誤判，但能保證元素“肯定不存在”的準(zhǔn)確性。

這樣我們就大致的了解了如何去自我實(shí)現(xiàn)一個(gè)布隆過(guò)濾器了！

布隆過(guò)濾器的優(yōu)缺點(diǎn)

從上述的布隆過(guò)濾器的自我實(shí)現(xiàn)中，我們就可以發(fā)現(xiàn)布隆過(guò)濾器的一些優(yōu)點(diǎn)和缺點(diǎn)，那么布隆過(guò)濾器有哪些優(yōu)缺點(diǎn)呢？

優(yōu)點(diǎn)：

• 高效的空間利用：布隆過(guò)濾器能夠通過(guò)少量的空間判斷數(shù)據(jù)是否存在，大大減少了內(nèi)存占用。
• 快速查詢：插入和查詢的時(shí)間復(fù)雜度為O(K)，其中K為哈希函數(shù)的個(gè)數(shù)，與數(shù)據(jù)量大小無(wú)關(guān)。
• 并行化處理：多個(gè)哈希函數(shù)的操作可以并行執(zhí)行，提高了性能。

缺點(diǎn)：

• 誤判：布隆過(guò)濾器可能會(huì)誤判某些不存在的元素為存在，但它能保證不存在的元素一定不會(huì)被誤判為存在。
• 不支持刪除：一旦元素插入布隆過(guò)濾器，無(wú)法刪除，因?yàn)閯h除操作可能會(huì)誤刪除其他哈希值相同的元素。

布隆過(guò)濾器的應(yīng)用

通過(guò)上述對(duì)布隆過(guò)濾器的解釋，我相信讀者可以對(duì)布隆過(guò)濾器有一定的了解了，那么布隆過(guò)濾器有哪些應(yīng)用呢？

布隆過(guò)濾器在以下場(chǎng)景中被廣泛使用：

• 網(wǎng)絡(luò)爬蟲的URL去重：在大規(guī)模的網(wǎng)絡(luò)爬蟲中，布隆過(guò)濾器用于判斷某個(gè)URL是否已經(jīng)被訪問(wèn)過(guò)，防止重復(fù)爬取。
• 垃圾郵件過(guò)濾：布隆過(guò)濾器用于記錄垃圾郵件發(fā)送者的地址，并在郵件服務(wù)器上快速過(guò)濾垃圾郵件。
• 數(shù)據(jù)庫(kù)緩存穿透：在大規(guī)模分布式系統(tǒng)中，布隆過(guò)濾器可以用于防止頻繁的數(shù)據(jù)庫(kù)查詢，減少緩存穿透的風(fēng)險(xiǎn)。

這樣我們就了解了布隆過(guò)濾器的應(yīng)用場(chǎng)景了！

海量數(shù)據(jù)處理中的應(yīng)用場(chǎng)景

從上面的文章內(nèi)容中我們可以知道，位圖和布隆過(guò)濾器都是對(duì)海量數(shù)據(jù)進(jìn)行處理的數(shù)據(jù)結(jié)構(gòu)，那么其在海量數(shù)據(jù)處理中的應(yīng)用場(chǎng)景有哪些呢？

位圖在海量數(shù)據(jù)處理中的應(yīng)用

位圖可以處理非常龐大的數(shù)據(jù)集，特別是在內(nèi)存有限的情況下，位圖通過(guò)其空間效率優(yōu)勢(shì)可以快速解決諸如數(shù)據(jù)去重、集合運(yùn)算等問(wèn)題。例如，假設(shè)有兩個(gè)包含100億個(gè)整數(shù)的文件，我們只有1GB的內(nèi)存，可以通過(guò)位圖來(lái)實(shí)現(xiàn)這兩個(gè)集合的交集、并集等操作。

案例：找到只出現(xiàn)一次的整數(shù)

// 假設(shè)我們有一個(gè)包含100億個(gè)整數(shù)的文件，下面的代碼實(shí)現(xiàn)了位圖的簡(jiǎn)單應(yīng)用
MyBitSet bitSet = new MyBitSet(10000000000);  // 10 billion bits
for (int num : nums) {
    if (!bitSet.get(num)) {
        bitSet.set(num);  // 如果沒有出現(xiàn)過(guò)，設(shè)置為1
    } else {
        bitSet.reSet(num);  // 如果再次出現(xiàn)，重置為0
    }
}
// 遍歷 bitSet，輸出所有只出現(xiàn)一次的整數(shù)

布隆過(guò)濾器在海量數(shù)據(jù)處理中的應(yīng)用

        布隆過(guò)濾器由于其空間優(yōu)勢(shì)和高效的查詢能力，在海量數(shù)據(jù)處理中被廣泛應(yīng)用于去重、快速查詢等場(chǎng)景。例如，在網(wǎng)絡(luò)爬蟲中，布隆過(guò)濾器用于檢測(cè)某個(gè)URL是否已經(jīng)訪問(wèn)過(guò)，防止重復(fù)抓取。

案例：布隆過(guò)濾器在URL去重中的應(yīng)用

BloomFilter filter = new BloomFilter();
for (String url : urls) {
    if (!filter.contains(url)) {
        // 處理未訪問(wèn)過(guò)的 URL
        filter.set(url);
    }
}

到此這篇關(guān)于Java的位圖和布隆過(guò)濾器深入詳細(xì)講解的文章就介紹到這了,更多相關(guān)Java位圖和布隆過(guò)濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論