目錄

1 原理

2 代碼示例

3 位數(shù)組

4 布隆過濾器的實(shí)際應(yīng)用場(chǎng)景

---

1 原理

布隆過濾器（Bloom Filter）是一種數(shù)據(jù)結(jié)構(gòu)，用于快速判斷一個(gè)元素是否存在于一個(gè)集合中，具有高效的插入和查詢操作。它的設(shè)計(jì)目的是在空間效率和查詢效率之間尋求一種折衷方案。

布隆過濾器基于位向量（bit array）和一系列的哈希函數(shù)。它適用于需要進(jìn)行高速判斷的場(chǎng)景，例如緩存系統(tǒng)、拼寫檢查、垃圾郵件過濾等。

布隆過濾器的原理如下：

1. 初始化：創(chuàng)建一個(gè)大小為 m 的位向量，所有位初始化為 0。

2. 插入：當(dāng)要插入一個(gè)元素時(shí)，對(duì)該元素進(jìn)行 k 次哈希函數(shù)計(jì)算，將對(duì)應(yīng)的 k 個(gè)位設(shè)為 1。

3. 查詢：當(dāng)要查詢一個(gè)元素是否存在時(shí)，同樣對(duì)該元素進(jìn)行 k 次哈希函數(shù)計(jì)算，檢查對(duì)應(yīng)的 k 個(gè)位是否都為 1，如果有任何一個(gè)位不為 1，則確定該元素不存在于集合中。如果所有位都為 1，則該元素可能存在于集合中（但不確定，考慮到誤判率）。

因?yàn)椴悸∵^濾器采用了多次哈希函數(shù)，并將元素映射到多個(gè)位，所以存在一定的誤判率。即使一個(gè)元素不存在于集合中，由于其哈希值可能會(huì)與其他元素的哈希值重疊，導(dǎo)致誤判為存在。但是，布隆過濾器具有占用空間小、查詢速度快的特點(diǎn)，適用于需要快速判斷元素是否可能存在的場(chǎng)景。

需要注意的是，布隆過濾器不支持刪除操作，因?yàn)閯h除操作會(huì)影響到其他可能存在的元素。如果需要支持刪除操作，可能需要考慮其他數(shù)據(jù)結(jié)構(gòu)。

2 代碼示例

import java.util.BitSet;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;public class BloomFilter {private int size; // 位數(shù)組的大小private int hashCount; // 哈希函數(shù)的個(gè)數(shù)private BitSet bitArray; // 位數(shù)組public BloomFilter(int size, int hashCount) {this.size = size;this.hashCount = hashCount;this.bitArray = new BitSet(size);}public void add(String item) {for (int i = 0; i < hashCount; i++) {int index = hashFunction(item, i) % size;bitArray.set(index, true);}}public boolean contains(String item) {for (int i = 0; i < hashCount; i++) {int index = hashFunction(item, i) % size;if (!bitArray.get(index)) {return false;}}return true;}private int hashFunction(String item, int seed) {try {MessageDigest md = MessageDigest.getInstance("MD5");md.update((item + seed).getBytes());byte[] digest = md.digest();return Math.abs(java.util.Arrays.hashCode(digest));} catch (NoSuchAlgorithmException e) {throw new RuntimeException("Hash function error: " + e.getMessage());}}public static void main(String[] args) {BloomFilter bloomFilter = new BloomFilter(100, 3);bloomFilter.add("apple");bloomFilter.add("banana");bloomFilter.add("cherry");System.out.println(bloomFilter.contains("apple"));   // 輸出 trueSystem.out.println(bloomFilter.contains("banana"));  // 輸出 trueSystem.out.println(bloomFilter.contains("grape"));   // 輸出 false}
}

根據(jù)上述代碼可知，要使用布隆過濾器，需要的成員屬性有：size（位數(shù)組大小）、hashCount（哈希函數(shù)的個(gè)數(shù)）、bitArray（位數(shù)組）、hashFunction（）這個(gè)是定義哈希函數(shù)的方法，參數(shù)是要加入集合的值以及哈希計(jì)算的次數(shù)，注意hashCount一般會(huì)通過for循環(huán)去調(diào)用它，以便k次哈希計(jì)算中每次使用的哈希函數(shù)是不同的。

3 位數(shù)組

這里提下位數(shù)組的概念以及與普通數(shù)組的區(qū)別

1. 存儲(chǔ)方式：

   • 位數(shù)組：位數(shù)組中的每個(gè)元素只占用一個(gè)位（0 或 1），因此在存儲(chǔ)上非常緊湊。它使用的是比特位來表示數(shù)據(jù)。
   • 普通數(shù)組：普通數(shù)組中的每個(gè)元素可以是任意數(shù)據(jù)類型，比如整數(shù)、浮點(diǎn)數(shù)、對(duì)象等。根據(jù)數(shù)據(jù)類型的不同，存儲(chǔ)占用的空間可能會(huì)更多。

2. 存儲(chǔ)內(nèi)容：

   • 位數(shù)組：通常用于表示某種狀態(tài)、存在與否、開關(guān)等，每個(gè)位代表一個(gè)二進(jìn)制信息，例如布爾值。
   • 普通數(shù)組：存儲(chǔ)任意數(shù)據(jù)類型，可以包含數(shù)字、字符串、對(duì)象等。

3. 內(nèi)存占用：

   • 位數(shù)組：由于每個(gè)元素只占用一個(gè)位，因此在相同存儲(chǔ)空間下，可以存儲(chǔ)更多的元素，適用于需要存儲(chǔ)大量布爾信息的情況。
   • 普通數(shù)組：根據(jù)元素的數(shù)據(jù)類型和數(shù)量，占用的內(nèi)存空間會(huì)更大。

4. 使用場(chǎng)景：

   • 位數(shù)組：適用于需要緊湊地表示某種狀態(tài)或標(biāo)記，如布隆過濾器、位圖索引等。
   • 普通數(shù)組：適用于存儲(chǔ)多種數(shù)據(jù)類型的數(shù)組，如整數(shù)數(shù)組、字符串?dāng)?shù)組、對(duì)象數(shù)組等。

總之，位數(shù)組和普通數(shù)組的主要區(qū)別在于存儲(chǔ)方式和存儲(chǔ)內(nèi)容。位數(shù)組通常用于緊湊地存儲(chǔ)標(biāo)志、狀態(tài)等信息，而普通數(shù)組可以存儲(chǔ)多種類型的數(shù)據(jù)。選擇使用哪種類型的數(shù)組取決于具體的應(yīng)用場(chǎng)景和需求。

4 布隆過濾器的實(shí)際應(yīng)用場(chǎng)景

背景：我們知道，現(xiàn)如今的電商系統(tǒng)特別是像阿里旗下的、京東等肯定是需要面對(duì)高并發(fā)請(qǐng)求問題的，這時(shí)避免不了用到中間件技術(shù)例如Redis、MQ。而以某寶為例，即使在用戶不登錄的情況下，它是需要有一些開放的API供未登錄用戶去看的，如“/product/{id}”,表示界面上對(duì)應(yīng)的商品。當(dāng)商品特別多，且用戶同時(shí)點(diǎn)擊作請(qǐng)求的次數(shù)太大時(shí)，Redis作為緩存是讓服務(wù)器能夠穩(wěn)定運(yùn)行的前提。這看起來似乎是解決了高并發(fā)問題，且能夠避免最影響整個(gè)系統(tǒng)服務(wù)性能的數(shù)據(jù)庫被頻繁訪問。但對(duì)于黑客來說，這其中有個(gè)漏洞可鉆。既然id是指商品的標(biāo)識(shí)符，那我不斷輸入不存在的商品id，而Redis又發(fā)現(xiàn)緩存中沒有這樣的id，就會(huì)轉(zhuǎn)向數(shù)據(jù)庫作請(qǐng)求，如此這般，便造成了緩存穿透。所以，一個(gè)新的問題是：我要如何識(shí)別并處理這些不存在的id，避免讓它們頻繁“騷擾”數(shù)據(jù)庫呢？這時(shí)布隆過濾器就這樣閃亮登場(chǎng)了。

解決：

上面提到的緩存穿透，總結(jié)來講是指在緩存中找不到所需的數(shù)據(jù)，導(dǎo)致每次請(qǐng)求都需要訪問數(shù)據(jù)庫或其他數(shù)據(jù)源，從而造成系統(tǒng)負(fù)擔(dān)過大。這種情況可能是由于惡意請(qǐng)求、非法輸入或者業(yè)務(wù)邏輯問題導(dǎo)致的。

布隆過濾器可以在緩存層面起到一定的預(yù)防作用，減輕緩存穿透帶來的影響。具體來說，以下是布隆過濾器如何用于防止緩存穿透的細(xì)節(jié)：

1. 在查詢緩存前進(jìn)行判斷： 在查詢緩存之前，先將查詢的參數(shù)進(jìn)行布隆過濾器的檢查。如果布隆過濾器判斷這個(gè)參數(shù)不在緩存的可能存在集合中，那么就不會(huì)去查詢緩存，避免了不必要的數(shù)據(jù)庫或其他數(shù)據(jù)源訪問。

2. 合法參數(shù)和非法參數(shù)的判斷： 布隆過濾器可以幫助區(qū)分合法參數(shù)和非法參數(shù)。如果一個(gè)參數(shù)不在布隆過濾器中，說明它肯定是非法的，可以直接返回一個(gè)錯(cuò)誤或默認(rèn)值，而不會(huì)繼續(xù)訪問后端數(shù)據(jù)源。

3. 動(dòng)態(tài)更新布隆過濾器： 當(dāng)緩存中的數(shù)據(jù)更新時(shí)，需要相應(yīng)地更新布隆過濾器中的信息，以確保布隆過濾器的準(zhǔn)確性。否則，布隆過濾器可能會(huì)誤判某個(gè)參數(shù)在緩存中不存在。

需要注意的是，布隆過濾器雖然可以減輕緩存穿透問題，但并不是完全解決方案。它可以用來過濾掉一部分明顯無效的請(qǐng)求，但不能保證百分之百防止緩存穿透。在實(shí)際應(yīng)用中，布隆過濾器通常與其他技術(shù)一起使用，如合理設(shè)置緩存過期時(shí)間、使用緩存預(yù)熱等，來綜合解決緩存穿透問題。

其它的應(yīng)用場(chǎng)景包括拼寫檢查、垃圾郵件過濾等