面試題：淺談布隆過濾器

問題情景

如果面試官問你，一個網站有 100 億 url 存在一個黑名單中，每條 url 平均 64 字節。問這個黑名單要怎麼存？若此時隨便輸入一個 url，如何判斷該 url 是否在這個黑名單中？

對於第一個問題，如果把黑名單看成一個集合，將其存在 hashmap 中，貌似太大了，需要 640G，明顯不科學。

那該怎麼辦？ok，現在該介紹今天的主角了 —— 布隆過濾器就可以解決這樣的問題。

首先，布隆過濾器是什麼？維基百科是這樣解釋的：

官方說法看下就好，如果不理解沒關係，其實不會難，下面我們講人話慢慢來。

具體介紹

「很長的二進制矢量」：這是一個長度很長的數組，什麼類型的數組呢？bit 類型的數組，也是我們說的「位」，（1Byte = 8bit，1KB = 1024Byte）。

「一系列隨機映射函數」：有多個哈希函數。那什麼是哈希函數呢？JDK 裡面有計算得到哈希值的方法，那就是一個哈希函數。

這個不就可以解決我們最開始的問題嗎？那它是怎麼解決的呢？

解決過程

下面我說下大體的過程，細節部分可先不理解，重要的是明白流程，細節我後面補充。

假設，bit 類型數組的長度為 m，每個元素值為 0，有 k 個哈希函數。

首先，當輸入一個 url 的時候，此時這個 url 會經過 k 個哈希函數處理，得到多個哈希值（v1,v2,...,vk）。之後分別將這些哈希值除以數組的長度 m，和對 m 取模，得到這些哈希值對應在數組的下標位置，最後將這些下標的元素都置為 1。

那麼如何判斷一個 url 在黑名單裡面呢？輸入一條 url，它經過上述處理之後，會得到多個數組的下標位置。如果這些下標的元素值都已經為 1 了，說明該在黑名單裡面，否則不在。

總體就是這樣的流程，下面說下大家可能存在的疑問。

1、bit 類型的數組如何構建

2、得到 v1,v2,...,vk 這些哈希值後，如何得到其在數組的下標位置，並將其設置為 1 呢？

兩個問題我一起說下，Java 裡面沒有 bit 這樣的類型，怎麼構建呢？—— 不難，我們可以使用 int，一個 int 是 32 位。

因此上面再會說「分別將這些哈希值除以數組的長度 m，和對 m 取模，得到這些哈希值對應在數組的下標位置」。

具體我們可以拿一個哈希值 data 來舉個栗子，假設 int 數組長度為 100。

使用效果

最開始我們提到，如果將 100 億 url 放到 HashMap 中需要 640GB，那麼使用布隆過濾器後又需要多少空間呢？答案是約等於 23 GB。相比之下，這個空間大小是不是就可以接受很多了。

缺點

布隆過濾器有寧可錯殺一百，也不能放過一個的性質。講人話就是屬於黑名單的 url 一定能夠正確判斷它在黑名單中，但不屬於黑名單中的 url 也可能會被認為在黑名單中，存在一定的失誤率。

至於失誤率要保持在多少，數組長度，哈希函數的個數分別要設置多少就需要根據實際情況來選擇了，網上有對應的數學公式計算，這裡就不展開講了。

後記

最後碎碎念一下，由於最近在準備面試，所以最近的推文可能會比較偏向筆試面試的問題，未來可能會有數據結構和算法的內容，這個真的是我的軟肋哈，以前挖的坑現在終於來填了。

閱讀更多 Java小優秀 的文章

關鍵字: 黑名單 數據結構 淺談