提到布隆過濾器總想起上大學(xué)時候?qū)W習(xí)的什么切比雪夫濾波器之類的東西（博主是學(xué)通信的），布隆過濾器是一種布爾型判斷器，可以非常高效的判斷一個物品是否在某個列表里。有人說判斷一個item是否在一個item列表里，只要將所有item存在數(shù)據(jù)庫，或者做一層緩存存在redis里，再遍歷的查一次不就得了？這么做沒問題，但是當item量巨大的時候，會出現(xiàn)緩存擊穿等問題。布隆過濾器很好地解決了這個問題，接下來會具體介紹原理。

布隆過濾器會被應(yīng)用在許多場景下，我接觸比較多的就是推薦場景的應(yīng)用，接下來講下具體的業(yè)務(wù)場景和原理。

01 布隆過濾器在推薦場景下的應(yīng)用

推薦系統(tǒng)中應(yīng)用布隆過濾器主要體現(xiàn)以下幾個場景：

場景1：判斷一個用戶是否是新用戶

場景2：判斷一個Item是否是新Item

場景3：判斷一個Item是否曾經(jīng)推薦給過某個User

這些場景的特點是都不需要獲取具體信息，只需要知道是否存在這個信息即可。比如判斷用戶是否是新用戶這個場景，用戶進來后首先判斷是否是新客，如果是新客就走冷啟動推薦邏輯，如果是老客就走傳統(tǒng)的召回+排序的推薦邏輯：

02 布隆過濾器具體原理

用過Redis都知道，Redis是將數(shù)據(jù)通過KV形式完整存儲到內(nèi)存里，并且提供了O(1)復(fù)雜度的查詢速度。但是Redis受限于內(nèi)存大小，承載不了特別大的數(shù)據(jù)。比如一個系統(tǒng)包含10億個賬號，每個賬號占位100B，那么全寫到Redis里得有快100G的內(nèi)存才行，比較難達到。

布隆過濾器之所以快并且占用空間小，主要原因是布隆過濾器并不直接存儲內(nèi)容，存儲的是哈希后的結(jié)果。比如下面這個圖，假設(shè)是hash(A)的結(jié)果，

則第3個、第6個、第10個這三個等于“1”。在查詢的時候只要查詢這三個位置是否是1就能確定A是否存在。

但是因為哈希存在哈希沖突這樣的問題，有可能第3個、第6個、第10個這三個等于“1”，但是這三個位置不是代表著A，而是B，因為A的哈希和B的哈希結(jié)果有沖突，這種概率很低。所以布隆過濾器的返回結(jié)果是一個概率值，返回的是某個對下可能存在的概率是多少。

總結(jié)

以上是生活随笔為你收集整理的布隆过滤器原理及在推荐业务的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。