機率數據結構
布隆過濾器是一種機率數據結構，它使用一個很長的二進制向量和一系列隨機映射函式（哈希函式）來判斷一個元素是否屬於某個集合。當元素被加入集合時，通過K個散列函式將這個元素映射到二進制向量中的K個點，並將這些點設定為1。在檢索時，如果這些點都是1，則元素可能存在於集合中；如果有任何一個點是0，則元素一定不在集合中。布隆過濾器有一定的誤判機率，即可能會錯誤地認為某個元素存在於集合中，但不會錯誤地認為元素不在集合中。
布隆過濾器的優點是空間效率和查詢時間效率較高，適用於大數據集的成員資格測試。它的缺點是存在一定的誤識別率，即有可能錯誤地認為某個元素存在於集合中，以及不支持刪除已添加的元素。
布隆過濾器可以套用於多種場景，如垃圾郵件地址過濾、瀏覽器檢測釣魚網站、防快取穿透攻擊等。在使用布隆過濾器之前，通常需要評估預期添加元素的最大數量和對錯誤結果的容忍程度，以確定最佳的布隆過濾器長度和哈希函式數量。
布隆過濾器是由布隆在1970年提出的，它的原理是通過哈希函式將元素映射到位數組中的特定位置，並將這些位置設定為1。檢索時，如果所有映射的位置都是1，則認為元素可能存在；如果有任何一個位置是0，則元素一定不存在。布隆過濾器在處理大量數據時具有優勢，但需要注意的是它的誤判機率與位數組的大小、已添加元素的數量和哈希函式的數量有關。