布隆過濾器

布隆過濾器被定義為一種資料結構，旨在以快速且記憶體高效的方式識別元素是否在一個集合中存在。

布隆過濾器實現了一種名為**機率資料結構**的特定資料結構。這種資料結構幫助我們識別一個元素是存在還是不存在於一個集合中。

**位向量作為基礎資料結構實現。** 以下是一個我們將用來解釋的小例子

表中的每個空單元格指定一個位，下面的數字是其索引或位置。要將元素追加到布隆過濾器中，我們只需對其進行幾次雜湊運算，並將位向量中這些雜湊值的位置或索引處的位設定為 1。

布隆過濾器的詳細實現將在以下內容中討論

布隆過濾器支援兩種操作，首先是追加物件並跟蹤物件，其次是驗證之前是否已見過某個物件。

將物件追加到布隆過濾器

• 我們計算要追加的物件的雜湊值；
• 我們使用這些雜湊值來設定布隆過濾器狀態中的某些位（雜湊值是要設定的位的位置）。

驗證布隆過濾器是否包含某個物件 -

• 我們計算要追加的物件的雜湊值；
• 接下來，我們驗證布隆過濾器狀態中這些雜湊值索引的位是否已設定。

我們必須記住，物件的雜湊值不會直接追加到布隆過濾器狀態；每個雜湊函式僅確定要設定或驗證哪個位。例如：如果只使用一個雜湊函式，則只驗證或檢查一個位。

Arnab Chakraborty

更新於： 2020年1月3日

3K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習