最後更新：2026-07-13

布隆過濾器容量

布隆過濾器是回答單一問題的精簡方法：「我大概看過這個元素了嗎？」它不儲存任何鍵，只保留一個位元陣列，以極小且可調的誤判機率換取大幅的記憶體節省。決定其形狀的是兩個數字——你預期儲存多少元素，以及你能容忍多頻繁的誤報——由此便可直接推得最佳的位元陣列大小與雜湊函數數量。

公式

對於 $n$ 個預期元素與目標誤判率 $p$，使記憶體最小的位元陣列長度為

此時最佳雜湊函數數量為

取整為最接近的整數。其中 $m$ 是位元數，$k$ 是套用在每個元素上的獨立雜湊函數數量，$\ln 2 \approx 0.693$。由於 $p$ 是小於 1 的機率，其自然對數為負，因此兩式皆得到正值。

計算範例。 一個容納一百萬元素（$n = 1{,}000{,}000$）、目標 1%（$p = 0.01$）的過濾器：

因此一百萬元素在 1% 下約需 1.14 MiB 記憶體與七個雜湊函數——大約每元素 9.6 位元，這個數字在該精度下對任何元素數量都成立。

每元素位元數與精度階梯

由於大小公式對 $n$ 為線性，每元素的儲存成本 $m / n = -\ln p / (\ln 2)^2$ 只取決於目標比率。這使它成為比較精度預算的乾淨指標。

誤判率每降低十倍，每元素約增加 4.8 位元與大約三個雜湊函數。記憶體僅線性增長，錯誤率卻幾何式下降，這正是布隆過濾器吸引人之處。

為什麼雜湊數量很重要

在陣列大小固定時，雜湊函數太少會讓位元稀疏、容易偶然命中；太多則會把陣列填得過密，使幾乎每個位元都被設定。最佳點會設定大約一半的位元，落在 $k = (m/n)\ln 2$。由於 $k$ 必須為整數，計算器會取整，而實際誤判率則由該取整值重新計算：

在上述範例中，取整後的 $k = 7$ 得到約 1.004%，略高於 1% 的目標，因為理想的 $k$ 是 6.64 而非整數。

布隆過濾器能與不能做什麼

布隆過濾器永遠不會產生漏判：若它說某元素不存在，那就確實不存在。唯一的誤差是誤報，其比率正是本計算器所規劃的。標準過濾器支援插入與查詢，但不支援刪除，因為位元在元素間共用——清除某個元素的位元可能破壞其他元素。當需要刪除時，計數式布隆過濾器以小型計數器取代每個位元，代價是數倍記憶體；布穀鳥過濾器則能在相近的大小下提供刪除。

一項提醒：過濾器是為固定的 $n$ 規劃的。若插入遠多於規劃的元素，陣列會飽和，把誤判率推高到目標之上。若成長可能發生，請一開始就以較大的數量規劃，或採用串接多個過濾器的可擴充設計。

實務中的取整

公式得到的位元數 $m$ 很少是整數。實際實作會配置整數個機器字組或記憶體分頁，因此把 $m$ 向上取整，這會使實際達成的誤判率略低於目標——是個小小的紅利。此處顯示的大小是取整前的理論最小值。

相關計算

布隆過濾器倚賴雜湊，因此兩個元素共用同一雜湊值的機率由同樣的生日數學所支配——請見雜湊碰撞機率計算機。對於固定長度的識別碼，UUID 碰撞機率計算器 將同樣的推理套用於 UUID，而 夏農熵計算 則衡量一組資料所攜帶的資訊量。