資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究效能指標
布隆過濾器的效能指標有三個可以權衡：計算或執行時間（對應於雜湊函式的數量 k）、過濾器的大小（對應於位數 m）和錯誤機率（對應於誤報率）。
f = (1 − p)k )
布隆過濾器 (BF) 引入了容錯機制來增強查詢效能和空間效率。布隆過濾器要麼返回真，要麼返回假。因此，布隆過濾器的結果屬於以下類別之一：真陽性、假陽性、真陰性、假陰性。布隆過濾器包含的最大數量是假陽性。假陽性和假陰性都會給系統帶來開銷。布隆過濾器使用陣列來儲存元素的資訊。假陽性的定義如下：如果布隆過濾器在持有元素時返回真。類似地，假陰性的定義如下：布隆過濾器在持有元素時返回假。因此，布隆過濾器屬於機率資料結構。
布隆過濾器大小和雜湊函式數量
我們知道，如果布隆過濾器的大小太小，很快所有位欄位都會變成“1”，然後我們的布隆過濾器將對每個輸入值返回“假陽性”。因此，布隆過濾器的大小是一個非常重要或需要做出的重要決策。較大的過濾器包含較少的假陽性，較小的過濾器則包含較多的假陽性。
因此，我們可以得出結論，布隆過濾器的大小完全基於“假陽性錯誤率”。
另一個重要的引數是確定我們將使用的雜湊函式的數量。我們實現的雜湊函式越多，布隆過濾器的速度就越慢，並且填充速度越快。但是，如果我們使用的雜湊函式太少，則可能會因許多假陽性而受到影響。
我們可以根據過濾器的尺寸 m、雜湊函式的數量 k 和插入的元素數量 n，使用以下公式計算假陽性錯誤率 p
p≈(1-e(-kn/m))k
我們實際上主要需要確定我們的 m 和 k 將是多少。因此，如果我們自己設定或固定錯誤容限值 p 和元素數量 n，我們可以使用以下公式來計算這些引數
m=(-n ln p)/(ln 2)2
k=(m/n)*(ln 2)
更新於： 2020年1月3日
261 次檢視
廣告