什么是『布隆過濾器』

布隆過濾器是一個神奇的數據結構，可以用來判斷一個元素是否在一個集合中。很常用的一個功能是用來去重。在爬蟲中常見的一個需求：目標網站 URL 千千萬，怎么判斷某個 URL 爬蟲是否寵幸過？簡單點可以爬蟲每采集過一個 URL，就把這個 URL 存入數據庫中，每次一個新的 URL 過來就到數據庫查詢下是否訪問過。

select id from table where url = 'https://jaychen.cc'

但是隨著爬蟲爬過的 URL 越來越多，每次請求前都要訪問數據庫一次，并且對于這種字符串的 SQL 查詢效率并不高。除了數據庫之外，使用 Redis 的 set 結構也可以滿足這個需求，并且性能優于數據庫。但是 Redis 也存在一個問題：耗費過多的內存。這個時候布隆過濾器就很橫的出場了：這個問題讓我來。

相比于數據庫和 Redis，使用布隆過濾器可以很好的避免性能和內存占用的問題。

布隆過濾器本質是一個位數組，位數組就是數組的每個元素都只占用 1 bit 。每個元素只能是 0 或者 1。這樣申請一個 10000 個元素的位數組只占用 10000 / 8 = 1250 B 的空間。布隆過濾器除了一個位數組，還有 K 個哈希函數。當一個元素加入布隆過濾器中的時候，會進行如下操作：

• 使用 K 個哈希函數對元素值進行 K 次計算，得到 K 個哈希值。
• 根據得到的哈希值，在位數組中把對應下標的值置為 1。

舉個
注：相關教程知識閱讀請移步到Redis頻道。