布隆過濾器（Bloom 過濾器）是一種空間效率和查詢時間都比一般算法要好的數據結構，由布隆在1970年提出。它通過一個很長的二進制向量和一系列隨機映射函數來檢索一個元素是否在一個集合中。布隆過濾器的基本思想是，當一個元素加入集合時，通過K個散列函數將這個元素映射到位數組中的K個點，并把它們置為1。檢索時，通過同樣的K個散列函數映射元素，如果這些位置都是1，則元素很可能存在；如果有任何一個0，則元素一定不存在。布隆過濾器的優點包括內存占用少、插入和查詢速度快，以及不需要存儲元素本身，適合保密要求嚴格的場合。缺點是存在一定的誤識別率，并且刪除元素比較困難。
在Redis中，布隆過濾器可以通過位圖（bitmap）數據結構實現。Redisson是一個Java程序中操作Redis的庫，它實現了布隆過濾器，底層使用bitmap數據結構。Redis 4.0版本通過插件功能提供了布隆過濾器功能，具有添加元素、批量添加元素、檢索元素是否存在、自定義布隆過濾器等常用命令。在實際測試中，布隆過濾器能夠有效地處理大量數據，盡管存在一定的誤判率，但可以通過調整參數來控制誤差范圍。
Guava也提供了布隆過濾器的實現，其位數組存儲在JVM內存中，適用于單機版。Guava中的布隆過濾器在創建時需要預估數據量和期望的誤判率，通過特定的計算方法確定位數組的大小和哈希函數的個數。測試表明，通過調整誤差率參數，可以顯著減少誤判情況。此外，Guava的布隆過濾器在存儲空間上相比HashMap等傳統數據結構有明顯優勢，尤其在處理大量數據時。在處理大規模數據集時，布隆過濾器可以有效地減少內存占用并提高查詢效率。
基本概念
如果想要判斷一個元素是不是在一個集合里，一般想到的是將所有元素保存起來，然后通過比較確定。鏈表，樹等等數據結構都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。不過世界上還有一種叫作散列表（又叫哈希表，Hash table）的數據結構。它可以通過一個Hash函數將一個元素映射成一個位陣列（刨刀 array）中的一個點。這樣一來，我們只要看看這個點是不是1就可以知道集合中有沒有它了。這就是布隆過濾器的基本思想。
Hash面臨的問題就是沖突。假設Hash函數是良好的，如果我們的位陣列長度為m個點，那么如果我們想將沖突率降低到例如 1%, 這個散列表就只能容納個元素。顯然這就不叫空間效率了（Space-efficient）了。解決方法也簡單，就是使用多個Hash，如果它們有一個說元素不在集合中，那肯定就不在。如果它們都說在，雖然也有一定可能性它們在說謊，不過直覺上判斷這種事情的概率是比較低的。
優點
相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外, Hash函數相互之間沒有關系，方便由硬件并行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能。
缺點
但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。常見的補救辦法是建立一個小的白名單，存儲那些可能被誤判的元素。但是如果元素數量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全的刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。
在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。
應用
網頁URL的去重，垃圾郵件的判別，集合重復元素的判別，查詢加速（比如基于key-value的存儲系統）、數據庫防止查詢擊穿，使用BloomFilter來減少不存在的行或列的磁盤查找。
java代碼實現
參考資料 >
布隆過濾器 Bloom Filter.juejin.cn.2024-03-26