什麼是布隆過濾器？ Redis中如何使用？

布隆過濾器是一個神奇的資料結構，這篇文章帶大家深入了解一下布隆過濾器，介紹一下Redis中使用布隆過濾器的方法。

什麼是『布隆過濾器』

#布隆過濾器是一個神奇的資料結構，可以用來判斷一個元素是否在一個集合中。很常用的功能是用來去重。在爬蟲中常見的一個需求：目標網站 URL 千千萬，怎麼判斷某個 URL 爬蟲是否寵幸過？簡單點可以爬蟲每採集過一個 URL，就把這個 URL 存入資料庫中，每次一個新的 URL 過來就到資料庫查詢下是否有造訪​​過。 【相關推薦：Redis影片教學】

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。

舉個，假設布隆過濾器有 3 個雜湊函數：f1, f2, f3 和一個位元組 arr。現在要把 https://jaychen.cc 插入布隆過濾器中：

• 對值進行三次雜湊計算，得到三個值 n1, n2, n3。
• 把位數組中三個元素 arr[n1], arr[n2], arr[3] 設為 1。

當要判斷一個值是否在布隆過濾器中，對元素再次進行哈希計算，得到值之後判斷位數組中的每個元素是否都為1，如果值都為1，那麼說明這個值在布隆過濾器中，如果存在一個值不為1，表示該元素不在布隆過濾器中。

看不懂文字看下面的靈魂畫手的圖解釋

#看了上面的說明，必然會提出一個問題：當插入的元素原來越多，位數組中被置為1 的位置就越多，當一個不在布隆過濾器中的元素，經過哈希計算之後，得到的值在位數組中查詢，有可能這些位置也都被置為1。這樣一個不存在布隆過濾器中的也有可能被誤判成在布隆過濾器中。但是如果布隆過濾器判斷說一個元素不在布隆過濾器中，那麼這個值就一定不在布隆過濾器中。簡單來說：

• 布隆過濾器說某個元素在，可能會被誤判。
• 布隆濾鏡說某個元素不在，那一定不在。

這個布隆過濾器的缺陷放到上面爬蟲的需求中，可能存在某些沒有訪問過的URL 可能會被誤判為訪問過，但是如果是訪問過的URL 一定不會誤判沒訪問過。

Redis 中的布隆過濾器

redis 在4.0 的版本中加入了module 功能，布隆過濾器可以透過module 的形式加入redis 中，所以使用redis 4.0 以上的版本可以透過載入module 來使用redis 中的布隆過濾器。但這不是最簡單的方式，使用 docker 可以直接在 redis 中體驗布隆過濾器。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis 布隆過濾器主要就兩個指令：

• #bf.add 新增元素到布隆過濾器中：bf. add urls https://jaychen.cc。
• bf.exists 判斷某個元素是否在篩選器中：bf.exists urls https://jaychen.cc。

上面說過布隆過濾器有誤判的情況，在 redis 中有兩個值決定布隆過濾器的準確率：

• error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
• initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

三个参数的含义：

• 第一个值是过滤器的名字。
• 第二个值为 error_rate 的值。
• 第三个值为 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists

更多编程相关知识，请访问：编程入门！！

以上是什麼是布隆過濾器？ Redis中如何使用？的詳細內容。更多資訊請關注PHP中文網其他相關文章！