一倘零、布隆過濾器可以用來做什么
????????布隆過濾器可用來判定一個元素是否屬于一個集合戳寸，比如在一個大的集合A中，是否存在值a疫鹊。由于hash碰撞(兩個不同輸入值的hash值相同)的原因拆吆，在判定a是否存在于A中時可能會有誤判。如果判定結(jié)果是a不存在于A中枣耀，a肯定是不在A中；如果判定結(jié)果是存在，這時可能是因為與a的hash值相同其他元素存在于A中佩微，而a并不存在。
????????關(guān)于布隆過濾器的使用場景谷浅，大多是用來判定“是否需要繼續(xù)執(zhí)行讀取磁盤等效率低的操作”奶卓。比如，Google 的BitTable 和Apach HBase夺姑，都使用布隆過濾器判斷查詢的數(shù)據(jù)是否存在，來確定是否需要繼續(xù)讀取磁盤眉睹。再比如，用爬蟲抓取網(wǎng)頁時慕蔚，有些網(wǎng)頁會相互鏈接或者多個網(wǎng)頁含有同一網(wǎng)頁鏈接斋配，所以可以使用布隆過濾器判斷url是否爬取過了，來確定是否繼續(xù)發(fā)起該url的訪問艰争。
二、布隆過濾器是怎么實現(xiàn)和使用的
1惦积、如何實現(xiàn)
????????布隆過濾器由兩個部分組成：一個位數(shù)組(只有0猛频、1值)和一組散列函數(shù)。布隆過濾器在剛初始化時鹿寻，數(shù)組中的值都是0，假設(shè)數(shù)組長度是10：
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
????????添加元素時坦敌，將元素作為輸入提供給散列函數(shù)痢法。 每個散列函數(shù)都將輸出一個數(shù)字作為數(shù)組索引，將索引對應(yīng)位置值更新為1蘸炸。 比如尖奔，將字符串“hello”傳遞給兩個散列函數(shù)f1，f2提茁，這兩個散列函數(shù)給出索引0和4，我們將位數(shù)組中的相應(yīng)位設(shè)置為1：
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
2铃岔、如何使用
????????當查詢一個元素是否存在于集合時丹弱，也先將元素傳給兩個散列函數(shù)铲咨，獲得兩個索引后蜓洪，檢查數(shù)組中相應(yīng)位的值：
- 如果兩個值中有0，即可判定該元素不在集合中摇天。所以恐仑，不一定需要檢查所有函數(shù)返回位的值，如果發(fā)現(xiàn)至少有一個值是0裳仆，那么即可判定該元素不在集合中。
- 如果兩個值都是1纯丸，只可判定為“該元素可能在集合中”静袖，因為散列函數(shù)可能會產(chǎn)生碰撞。比如我們使用兩個函數(shù)獲取“bloom”的索引可能為1和9坠陈，獲取“filter”的索引可能為5和7捐康，而此時再去查詢“word”，會因為1和9已被“bloom”和“filter”已經(jīng)設(shè)置為1而產(chǎn)出碰撞解总。因此，我們不能100%確定查詢的元素在集合中。
三萍嬉、為什么布隆過濾器效率比較高
時間復(fù)雜度
- 添加元素時壤追，由于不需要迭代位數(shù)組，而是簡單的設(shè)置索引位的值行冰，所以操作所花費的時間僅取決于散列函數(shù)的個數(shù)伶丐。對于對于k個哈希函數(shù)的布隆過濾器疯特，添加元素的時間復(fù)雜度為O(k) 。
- 查詢元素時录别，對于k個哈希函數(shù)的布隆過濾器邻吞，只需要在位數(shù)組中檢查的索引數(shù)量有一個不變的上界，所以查詢元素的時間復(fù)雜度也為O(k)抱冷。
空間復(fù)雜度
????????由于不需要存儲元素旺遮，只需依賴一定長度的位數(shù)組判斷是否存在，并且數(shù)組長度的大小不也取決于集合中元素的多少趣效，可以在誤判率變大或效率變低的代價下減少存儲（位數(shù)組）。
四讯私、布隆過濾器有哪些缺點
????????主要缺點是有一定的誤判率西傀，所以隨著存入集合的元素的增加，誤判率也隨之增加娘锁。誤判率大小和三個指標有關(guān)：位數(shù)組長度m饺鹃、集合長度n、散列函數(shù)個數(shù)k悔详，其之間關(guān)系可以參考文獻 ，該文獻證明了對于給定的m缝驳、n，當 k = ln(2)* m/n 時誤判率是最小的运怖。
