布隆過濾器是偶然聽到的一個東西瓢谢，名字有點(diǎn)吸引我畸写。于是去作了一番了解。
布隆過濾器與散列表氓扛、鏈表性質(zhì)一樣枯芬，是一種數(shù)據(jù)結(jié)構(gòu)。它的應(yīng)用優(yōu)點(diǎn)在于節(jié)省空間同時(shí)提高查找效率采郎。
這里明確一點(diǎn)是布隆過濾器本身是不存值的千所，所以用它來判斷一個值是否存在列表中是一個非常合適的場景。與此同時(shí)蒜埋，它不能判斷值一定存在列表中淫痰，因?yàn)樗鼤霈F(xiàn)誤判。下面會細(xì)說整份。
布隆過濾器的本質(zhì)是一張位圖(BitMap)待错，如下
當(dāng)我們用關(guān)鍵字存值時(shí)，需要借用一個工具——哈希函數(shù)烈评，哈希函數(shù)在散列表上也有應(yīng)用火俄，這里不談了。
通過哈希函數(shù)讲冠，我們可以對一個關(guān)鍵字(Key)瓜客，算出一個哈希值，這里的哈希值假設(shè)算出上圖的下標(biāo)（1），那么存值的時(shí)候我們的布隆過濾器是這樣表示的：
這樣意味著1這個位置存了值谱仪，如果我們需要檢驗(yàn)關(guān)鍵字（Key）是否存在玻熙，那么再次通過散列函數(shù)算出來下標(biāo)，如果位圖這個位置標(biāo)記為1芽卿，那么說明這個Key是存在的揭芍。原理就是如此簡單胳搞。
實(shí)際上卸例，布隆過濾器往往會采用多個散列函數(shù)來生成多個下標(biāo)，例如3個散列函數(shù)生成3個下標(biāo)（1,5,6）肌毅，那么表達(dá)起來就會是這樣：
為什么需要多個散列函數(shù)筷转？
其實(shí)是為了提高它準(zhǔn)確率，因?yàn)樯⒘泻瘮?shù)很可能對于不同的Key可能會產(chǎn)生相同的散列值悬而，所以設(shè)置多個散列函數(shù)能讓Key留存率高一點(diǎn)呜舒，比較后面也許會有其它值把它沖掉，比如另外一個KeyOther笨奠，計(jì)算出的散列值(2,5,7)袭蝗。那么存了KeyOther的時(shí)候，位圖就變?yōu)檫@樣了：
可以看出5下標(biāo)被覆蓋掉了般婆，這時(shí)如果你要判斷Key存不存在怎么辦到腥？你算出了(1,5,6)，那么如果通過查看（1蔚袍，5乡范，6）的位置都為1的時(shí)候，是不是意味著Key是有可能存在了啤咽。注意晋辆，這里是有可能存在，也是布隆過濾器為什么會出現(xiàn)誤算的原因宇整。
我總結(jié)了兩點(diǎn)：
1.布隆過濾器不能算出值的必然存在
2.布隆過濾器能算出值的必定不存在
最后思考
位圖的長度會影響布隆過濾器的長度
哈希函數(shù)的個數(shù)會影響布隆過濾器的誤報(bào)率以及效率
其中的函數(shù)關(guān)系瓶佳，靠自我腦補(bǔ)了。
額外知識
支持刪除的布隆過濾器：Couting Bloom Filter
哈希算法：FNV
以上均為個人見解鳞青，不做任何參考霸饲。
參考資料：維基百科
