Java的布隆過濾器如何實現

今天小編給大家分享一下Java的布隆過濾器如何實現的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

BitMap

現代計算機用二進制（bit，位）作為信息的基礎單位，1 個字節等于 8 位，例如big字符串是由 3 個字節組成，但實際在計算機存儲時將其用二進制表示，big分別對應的 ASCII 碼分別是 98、105、103，對應的二進制分別是 01100010、01101001 和 01100111。

許多開發語言都提供了操作位的功能，合理地使用位能夠有效地提高內存使用率和開發效率。

Bit-map 的基本思想就是用一個 bit 位來標記某個元素對應的 value，而 key 即是該元素。由于采用了 bit 為單位來存儲數據，因此在存儲空間方面，可以大大節省。

在 Java 中，int 占 4 字節，1 字節 = 8位（1 byte = 8 bit），如果我們用這個 32 個 bit 位的每一位的值來表示一個數的話是不是就可以表示 32 個數字，也就是說 32 個數字只需要一個 int 所占的空間大小就可以了，那就可以縮小空間 32 倍。

1 Byte = 8 Bit，1 KB = 1024 Byte，1 MB = 1024 KB，1GB = 1024 MB

假設網站有 1 億用戶，每天獨立訪問的用戶有 5 千萬，如果每天用集合類型和 BitMap 分別存儲活躍用戶：

1.假如用戶 id 是 int 型，4 字節，32 位，則集合類型占據的空間為 50 000 000 * 4/1024/1024 = 200M；

2.如果按位存儲，5 千萬個數就是 5 千萬位，占據的空間為 50 000 000/8/1024/1024 = 6M。

那么如何用 BitMap 來表示一個數呢？

上面說了用 bit 位來標記某個元素對應的 value，而 key 即是該元素，我們可以把 BitMap 想象成一個以位為單位的數組，數組的每個單元只能存儲 0 和 1（0 表示這個數不存在，1 表示存在），數組的下標在 BitMap 中叫做偏移量。比如我們需要表示{1,3,5,7}這四個數，如下：

那如果還存在一個數 65 呢？只需要開int[N/32+1]個 int 數組就可以存儲完這些數據（其中 N 表示這群數據中的最大值），即：

int[0]：可以表示 0~31

int[1]：可以表示 32~63

int[2]：可以表示 64~95

假設我們要判斷任意整數是否在列表中，則 M/32 就得到下標，M%32就知道它在此下標的哪個位置，如：

65/32 = 2，65%32=1，即 65 在int[2] 中的第 1 位。

布隆過濾器

本質上布隆過濾器是一種數據結構，比較巧妙的概率型數據結構，特點是高效地插入和查詢，可以用來告訴你 “某 樣東西一定不存在或者可能存在”。

相比于傳統的 List、Set、Map 等數據結構，它更高效、占用空間更少，但是缺點是其返回的結果是概率性的，而不是確切的。

實際上，布隆過濾器廣泛應用于網頁黑名單系統、垃圾郵件過濾系統、爬蟲網址判重系統等，Google 著名的分布式數據庫 Bigtable 使用了布隆過濾器來查找不存在的行或列，以減少磁盤查找的 IO 次數，Google Chrome 瀏覽器使用了布隆過濾器加速安全瀏覽服務。

在很多 Key-Value 系統中也使用了布隆過濾器來加快查詢過程，如 Hbase，Accumulo，Leveldb，一般而言，Value 保存在磁盤中，訪問磁盤需要花費大量時間，然而使用布隆過濾器可以快速判斷某個 Key 對應的 Value 是否存在，因此可以避免很多不必要的磁盤 IO 操作。

通過一個 Hash 函數將一個元素映射成一個位陣列（Bit Array）中的一個點。這樣一來，我們只要看看這個點是不是 1 就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。

運用場景

1、目前有 10 億數量的自然數，亂序排列，需要對其排序。限制條件在 32 位機器上面完成，內存限制為 2G。如何完成？

2、如何快速在億級黑名單中快速定位 URL 地址是否在黑名單中？(每條 URL 平均 64 字節)

3、需要進行用戶登陸行為分析，來確定用戶的活躍情況？

4、網絡爬蟲-如何判斷 URL 是否被爬過？

5、快速定位用戶屬性（黑名單、白名單等）？

6、數據存儲在磁盤中，如何避免大量的無效 IO？

7、判斷一個元素在億級數據中是否存在？

8、緩存穿透。

傳統數據結構的不足

一般來說，將網頁 URL 存入數據庫進行查找，或者建立一個哈希表進行查找就 OK 了。

當數據量小的時候，這么思考是對的，確實可以將值映射到 HashMap 的 Key，然后可以在 O(1) 的時間復雜度內 返回結果，效率奇高。但是 HashMap 的實現也有缺點，例如存儲容量占比高，考慮到負載因子的存在，通常空間是不能被用滿的，舉個例子如果一個 1000 萬 HashMap，Key=String（長度不超過 16 字符，且重復性極小），Value=Integer，會占據多少空間呢？1.2 個 G。

實際上用 bitmap，1000 萬個 int 型，只需要 40M（ 10 000 000 * 4/1024/1024 =40M）左右空間，占比 3%，1000 萬個 Integer，需要 161M 左右空間，占比 13.3%。

可見一旦你的值很多例如上億的時候，那 HashMap 占據的內存大小就可想而知了。

但如果整個網頁黑名單系統包含 100 億個網頁 URL，在數據庫查找是很費時的，并且如果每個 URL 空間為 64B，那么需要內存為 640GB，一般的服務器很難達到這個需求。

實現原理

假設我們有個集合 A，A 中有 n 個元素。利用k個哈希散列函數，將A中的每個元素映射到一個長度為 a 位的數組 B中的不同位置上，這些位置上的二進制數均設置為 1。如果待檢查的元素，經過這 k個哈希散列函數的映射后，發現其 k 個位置上的二進制數全部為 1，這個元素很可能屬于集合A，反之，一定不屬于集合A。

比如我們有 3 個 URL {URL1,URL2,URL3}，通過一個hash 函數把它們映射到一個長度為 16 的數組上，如下：

若當前哈希函數為 Hash2()，通過哈希運算映射到數組中，假設Hash2(URL1) = 3，Hash2(URL2) = 6，Hash2(URL3) = 6，如下：

因此，如果我們需要判斷URL1是否在這個集合中，則通過Hash(1)計算出其下標，并得到其值若為 1 則說明存在。

由于 Hash 存在哈希沖突，如上面URL2,URL3都定位到一個位置上，假設 Hash 函數是良好的，如果我們的數組長度為 m 個點，那么如果我們想將沖突率降低到例如 1%， 這個散列表就只能容納 m/100 個元素，顯然空間利用率就變低了，也就是沒法做到空間有效（space-efficient）。

解決方法也簡單，就是使用多個 Hash 算法，如果它們有一個說元素不在集合中，那肯定就不在，如下：

Hash2(URL1) = 3,Hash3(URL1) = 5,Hash4(URL1) = 6
Hash2(URL2) = 5,Hash3(URL2) = 8,Hash4(URL2) = 14
Hash2(URL3) = 4,Hash3(URL3) = 7,Hash4(URL3) = 10

以上就是布隆過濾器做法，使用了k個哈希函數，每個字符串跟 k 個 bit 對應，從而降低了沖突的概率。

誤判現象

上面的做法同樣存在問題，因為隨著增加的值越來越多，被置為 1 的 bit 位也會越來越多，這樣某個值即使沒有被存儲過，但是萬一哈希函數返回的三個 bit 位都被其他值置位了 1 ，那么程序還是會判斷這個值存在。比如此時來一個不存在的 URL1000，經過哈希計算后，發現 bit 位為下：

Hash2(URL1000) = 7,Hash3(URL1000) = 8,Hash4(URL1000) = 14

但是上面這些 bit 位已經被URL1,URL2,URL3置為 1 了，此時程序就會判斷 URL1000 值存在。

這就是布隆過濾器的誤判現象，所以，布隆過濾器判斷存在的不一定存在，但是，判斷不存在的一定不存在。

布隆過濾器可精確的代表一個集合，可精確判斷某一元素是否在此集合中，精確程度由用戶的具體設計決定，達到 100% 的正確是不可能的。但是布隆過濾器的優勢在于，利用很少的空間可以達到較高的精確率。

實現

Redis 的 bitmap

基于redis 的 bitmap數據結構的相關指令來執行。

RedisBloom

布隆過濾器可以使用 Redis 中的位圖(bitmap)操作實現，直到 Redis4.0 版本提供了插件功能，Redis 官方提供的布隆過濾器才正式登場，布隆過濾器作為一個插件加載到 Redis Server 中，官網推薦了一個 RedisBloom 作為 Redis 布隆過濾器的 Module。

Guava 的 BloomFilter

Guava 項目發布版本11.0時，新添加的功能之一是BloomFilter類。

Redisson

Redisson 底層基于位圖實現了一個布隆過濾器。

public static void main(String[] args) {
    Config config = new Config();
    // 單機環境
    config.useSingleServer().setAddress("redis://192.168.153.128:6379");
    //構造Redisson
    RedissonClient redisson = Redisson.create(config);
    RBloomFilter<String> bloomFilter = redisson.getBloomFilter("nameList");
    //初始化布隆過濾器：預計元素為100000000L,誤差率為3%,根據這兩個參數會計算出底層的 bit 數組大小
    bloomFilter.tryInit(100000L, 0.03);
    //將 10086 插入到布隆過濾器中
    bloomFilter.add("10086");
    //判斷下面號碼是否在布隆過濾器中
    System.out.println(bloomFilter.contains("10086"));//true
    System.out.println(bloomFilter.contains("10010"));//false
    System.out.println(bloomFilter.contains("10000"));//false
}

解決緩存穿透

緩存穿透是指查詢一個根本不存在的數據，緩存層和存儲層都不會命中，如果從存儲層查不到數據則不寫入緩存層。

緩存穿透將導致不存在的數據每次請求都要到存儲層去查詢，失去了緩存保護后端存儲的意義。緩存穿透問題可能會使后端存儲負載加大，由于很多后端存儲不具備高并發性，甚至可能造成后端存儲宕掉。

因此我們可以用布隆過濾器來解決，在訪問緩存層和存儲層之前，將存在的 key 用布隆過濾器提前保存起來，做第一層攔截。

例如：一個推薦系統有 4 億個用戶 id，每個小時算法工程師會根據每個用戶之前歷史行為計算出推薦數據放到存儲層中，但是最新的用戶由于沒有歷史行為，就會發生緩存穿透的行為，為此可以將所有推薦數據的用戶做成布隆過濾器。如果布隆過濾器認為該用戶 id 不存在，那么就不會訪問存儲層，在一定程度保護了存儲層。

注：布隆過濾器可能會誤判，放過部分請求，當不影響整體，所以目前該方案是處理此類問題最佳方案

以上就是“Java的布隆過濾器如何實現”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。