首先片林，先來了解布隆過濾器的概念集漾。
布隆過濾器（Bloom Filter）是一個(gè)叫做 Bloom 的老哥于1970年提出的合呐。可以把它看作由二進(jìn)制向量（或者說位數(shù)組）和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)漩勤。相比于我們平時(shí)常用的的 List感挥、Map 、Set 等數(shù)據(jù)結(jié)構(gòu)越败，它占用空間更少并且效率更高触幼，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是非常準(zhǔn)確的究飞。理論情況下添加到集合中的元素越多置谦，誤報(bào)的可能性就越大；并且亿傅，存放在布隆過濾器的數(shù)據(jù)不容易刪除媒峡。
布隆過濾器示意圖
位數(shù)組中的每個(gè)元素都只占用 1 bit ，并且每個(gè)元素只能是 0 或者 1葵擎。這樣申請一個(gè) 100w 個(gè)元素的位數(shù)組只占用 1000000 / 8 = 125000 B = 15625 byte ≈ 15.3 kb 的空間谅阿。
總結(jié)：一個(gè)名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)是高效且性能很好的酬滤，但缺點(diǎn)是具有一定的錯(cuò)誤識別率和刪除難度签餐。并且，理論情況下盯串，添加到集合中的元素越多贱田，誤報(bào)的可能性就越大。
