【后端基礎】布隆過濾器原理

文章目錄

- 一、Bloom Filter（布隆過濾器）概述
- - 1. Bloom Filter 的特點
  - 2. Bloom Filter 的工作原理
- 二、示例
- - 1. 添加與查詢
  - 2. 假陽性
- 三、Bloom Filter 的操作
- - 1、假陽性概率
  - 2、空間效率
  - 3、哈希函數的選擇
- 四、應用

Bloom Filter 是一種非常高效的概率型數據結構，廣泛應用于需要快速判斷元素是否在集合中的場景。雖然它可能會產生假陽性，但通過調整位數組的大小和哈希函數的數量，可以控制假陽性率。在內存受限的環境中，Bloom Filter 提供了一個非常節省空間的解決方案。

通過適當的哈希函數和合理的配置，Bloom Filter 在大數據系統、搜索引擎、網絡安全等領域具有廣泛的應用前景。

一、Bloom Filter（布隆過濾器）概述

Bloom Filter 是一種空間高效的概率型數據結構，用于測試一個元素是否屬于一個集合。它的特點是可以快速地判斷某個元素是否在集合中，但是有一定的假陽性率。也就是說，Bloom Filter 可能會錯誤地告訴你某個元素存在，但實際上它并不在集合中；然而，假陰性（即元素確實存在，但 Bloom Filter 卻說它不存在）是永遠不會發生的。

1. Bloom Filter 的特點

空間高效：相較于傳統的哈希表，Bloom Filter 在固定大小的情況下可以表示一個元素數量極大的集合。它不需要存儲實際的元素值，而是通過一組哈希函數和一個位數組來表示集合。
永不產生假陰性： Bloom Filter 不會錯誤地告訴你某個元素不存在，只會可能錯誤地告訴你某個元素已經存在（即假陽性）。
增加元素時不會失敗：向 Bloom Filter 中添加元素不會失敗，但是隨著添加的元素增多，假陽性率會逐漸增加，直到所有的位都被設置為 1 為止，在此時所有查詢都會返回存在的結果。
無法刪除元素：刪除元素在 Bloom Filter 中是不可能的，因為如果清除某個哈希值對應的位，會影響其他元素的存在性。例如，如果你刪除 “geeks”，可能會錯誤地刪除 “nerd”。這就是 Bloom Filter 無法刪除元素的原因。

2. Bloom Filter 的工作原理

Bloom Filter 的基本操作包括：

插入元素（insert）：通過多個哈希函數計算出元素的哈希值，并將這些哈希值對應的位設置為 1。
查詢元素（lookup）：同樣計算該元素的哈希值，如果對應位全為 1，則認為元素可能存在；如果有任何一個位是 0，則可以確定元素不在集合中。

二、示例

1. 添加與查詢

通過概率+節點個數來決定布隆過濾器的函數個數、數組位數

假設我們有一個長度為 10 的位數組，所有位初始值為 0，我們使用 3 個哈希函數來添加 “geeks” 和 “nerd” 這兩個元素。

在這里插入圖片描述

添加 “geeks”：
- 計算哈希值：
  - h1(“geeks”) % 10 = 1
  - h2(“geeks”) % 10 = 4
  - h3(“geeks”) % 10 = 7
- 將位數組中的索引 1、4、7 設置為 1。
添加 “nerd”：
- 計算哈希值：
  - h1(“nerd”) % 10 = 3
  - h2(“nerd”) % 10 = 5
  - h3(“nerd”) % 10 = 4
- 將位數組中的索引 3、5、4 設置為 1。

在這里插入圖片描述

查詢 “geeks”：
- 計算哈希值并檢查位數組中的相應位置：
  - 如果所有索引（1、4、7）對應的位都為 1，則 “geeks” 可能存在。

2. 假陽性

由于多個元素可能會映射到同一位，Bloom Filter 會發生假陽性。例如，當我們查詢 “cat” 時，計算出哈希值為 1、3、7，查到這三個位置的值為 1，雖然 “cat” 并沒有被添加到 Bloom Filter 中，但它的哈希值與其他元素（如 “geeks” 和 “nerd”）重合了，因此 Bloom Filter 錯誤地認為 “cat” 存在。這就是假陽性。
在這里插入圖片描述

三、Bloom Filter 的操作

insert(x)：將元素 x 插入到 Bloom Filter 中。
lookup(x)：檢查元素 x 是否存在于 Bloom Filter 中，返回“可能存在”或“肯定不存在”。

1、假陽性概率

假陽性概率可以通過以下公式計算：

$\left( 1 - \left( 1 - \frac{1}{m} \right)^{kn} \right)^k$

其中：

m 是位數組的大小，
k 是哈希函數的數量，
n 是預計插入元素的數量。

位數組大小的計算：

$\frac{-n \cdot \ln(p)}{(\ln(2))^2}$

哈希函數數量的計算：

$\frac{m}{n} \cdot \ln(2)$

2、空間效率

Bloom Filter 的空間效率非常高。傳統的集合存儲結構（如哈希表、數組或鏈表）需要存儲數據本身，而 Bloom Filter 只需要一個位數組，這使得它在內存使用上非常高效。
?

3、哈希函數的選擇

Bloom Filter 使用的哈希函數應該是獨立且均勻分布的。常用的非加密哈希函數如 MurmurHash、FNV、Jenkins 都能很好地工作。加密哈希函數雖然穩定且具有較強的保證，但在性能上較慢，因此在 Bloom Filter 中更常用非加密哈希函數以提高性能。

四、應用

中等大小的集合過濾：Medium 用 Bloom Filter 來推薦用戶已經看過的帖子，從而避免重復推薦。
Quora：實現了一個共享的 Bloom Filter，過濾用戶已經看過的帖子。
Google Chrome：用 Bloom Filter 來識別惡意 URL。
大數據存儲系統：Google BigTable、Apache HBase、Apache Cassandra 和 PostgreSQL 等都使用 Bloom Filter 來減少磁盤查詢，特別是在沒有存在的行或列時。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/70571.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/70571.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/70571.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！