布隆過濾器

布隆過濾器（Bloom Filter）是一種機率數據結構，設計來有效地測試元素是否屬於一個集合。布隆過濾器由伯頓·霍華德·布隆（Burton Howard Bloom）於 1970 年發明，由於能夠以最小的記憶體消耗管理大型數據集，已成為電腦科學領域的基本工具。與雜湊表或二元搜尋樹等傳統數據結構不同，當某個元素不在集合中時，布隆過濾器可以提供確定的答案，但當某個元素在集合中時，它只能提供機率答案。這意味著雖然可能出現偽陽性答案，但不會出現偽陰性答案。

布隆過濾器的核心概念圍繞著一個初始值均為 0 的位元數組和一系列雜湊函數。當一個元素加入布隆過濾器時，它會經過每個雜湊函數，以在位元陣列中產生多個位置，然後再將這些位置上的位元設為 1。要檢查某個元素是否在集合中，需要再次使用相同的函數對其進行雜湊，並檢查對應的位元。如果這些位置上的所有位元都是 1，則認為該元素有可能出現在集合中；如果任何一位都是 0，則該元素肯定不在集合中。

布隆過濾器的顯著優勢是其空間效率。相比執行相同任務的其他數據結構，它所需的記憶體要少得多，尤其是當元素數量增加時。例如，無論集合中的元素數量多少，要達到 1% 的偽陽性機率，每個元素所需的位元數都少於 10 位元。因此，對於重視記憶體使用量的應用程式（例如：網路路由器、數據庫系統和分散式系統）來說，布隆過濾器特別有用。

不過，布隆過濾器也有一定的限制。其中一個主要缺點是它無法從集合中刪除元素，因為清除被多個元素設定的位元會造成偽陰性。為了解決這個問題，諸如計數布隆過濾器等變體版本已開發出來，透過對每個位元被設定的次數進行計數來刪除元素。此外，隨著元素的增加，偽陽性率也會增加，這意味著必須根據預期的元素數量和可接受的偽陽性率，謹慎選擇位元數組的大小和雜湊函數的數量。

在實際應用中，布隆過濾器在各個領域都獲得了廣泛應用。例如，在比特幣中，布隆過濾器被用於提高簡化支付驗證（Simplified Payment Verification, SPV）客戶端的隱私性，允許用戶在不暴露地址的情況下查詢交易。Akamai 等內容分發網路也會使用布隆過濾器來有效管理快取儲存，透過避免不必要的數據檢索，減少伺服器的工作量。儘管布隆過濾器具有機率性質和局限性，但仍然是設計高效、可擴展系統的寶貴工具。