使用場景
布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，旨在快速、高效地判斷一個(gè)元素是否存在于一個(gè)集合中。
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)當(dāng)然是時(shí)間復(fù)雜度很低.但他也有缺點(diǎn)，布隆過濾器是一個(gè)概率數(shù)據(jù)結(jié)構(gòu)：
它告訴我們，該元素要么肯定不在集合中(not_in)，要么可能(maybe_in)在集合中。(會告訴你maybe_in的概率.)
原理&實(shí)踐
布隆過濾器的基本數(shù)據(jù)結(jié)構(gòu)是一個(gè)比特?cái)?shù)組。下面是一個(gè)demo數(shù)組，我們將用來演示。
該表中的每個(gè)空單元代表一個(gè)bit，下面的數(shù)字則是其索引Index。要向布隆過濾器添加一個(gè)元素，我們只需對其進(jìn)行幾次hash，并將這些hash結(jié)果所在的索引處的比特置為1。
例如,我們把集合["yanxin","yanxiaori","yanbo"], 通過Fnv和Murmur計(jì)算后, 把結(jié)果添加到布隆數(shù)組中
(Fnv和Murmur是兩個(gè)簡單的哈希函數(shù)。)
看到哈希值給出的索引處的比特被設(shè)置為1。我用綠色來顯示新添加的，但任何彩色單元都只是1。
為了測試成員資格，你只需用相同的哈希函數(shù)對字符串進(jìn)行哈希，然后看這些值是否在比特向量中被設(shè)置。如果不是，你就知道這個(gè)元素不在這個(gè)集合中。如果它們是，你只知道它可能是，因?yàn)榱硪粋€(gè)元素或其他元素的一些組合可能設(shè)置了相同的位。再一次，我們來演示一下。
以上就是布隆過濾器的基本概念.
高級
在我寫更多關(guān)于布魯姆過濾器的內(nèi)容之前，先聲明一下：我從來沒有在生產(chǎn)中使用過它們。請不要相信我的話。我所要做的只是給你一個(gè)大致的概念，并指出你可以在哪里找到更多。
在下面的文字中，我們將提到一個(gè)有k個(gè)哈希值的布隆過濾器，過濾器中的m個(gè)比特，以及被插入的n個(gè)元素。
哈希函數(shù)
布隆過濾器中使用的哈希函數(shù)應(yīng)該是獨(dú)立的、均勻分布的。它們還應(yīng)該是盡可能快的（像sha1這樣的加密散列函數(shù)，雖然被廣泛使用，但并不是很好的選擇）。
足夠獨(dú)立的快速、簡單的哈希值的例子包括murmur、fnv系列的哈希值和HashMix。
要看到比加密哈希函數(shù)更快的區(qū)別，請看這個(gè)故事，當(dāng)把一個(gè)bloom filter的實(shí)現(xiàn)從md5切換到murmur時(shí)，速度提高了大約800%。
在一個(gè)簡短的布隆過濾器實(shí)現(xiàn)的調(diào)查中。
Chromium使用HashMix。(另外，這里有一個(gè)關(guān)于他們?nèi)绾问褂胋loom filter的簡短描述)
python-bloomfilter使用加密的哈希值
Plan9使用Mitzenmacher 2005中提出的簡單哈希值
Sdroege Bloom filter使用fnv1a（包括在內(nèi)只是因?yàn)槲蚁胝故疽粋€(gè)使用fnv的。）
Squid使用MD5
布隆過濾器的時(shí)間和空間復(fù)雜度如何？
給定一個(gè)有m個(gè)比特和k個(gè)散列函數(shù)的布隆過濾器，插入和成員測試都是O(k)。
也就是說，每次你想向集合添加一個(gè)元素或檢查集合成員資格時(shí)，你只需要通過k個(gè)散列函數(shù)運(yùn)行該元素，并將其添加到集合中或檢查這些比特。
空間方面的優(yōu)勢更難總結(jié)；這同樣取決于你愿意容忍的錯(cuò)誤率。這也取決于要插入的元素的潛在范圍:
如果它非常有限，一個(gè)確定性的比特向量可以做得更好。如果你甚至不能粗略估計(jì)要插入的元素的數(shù)量，你可能最好使用哈希表或可擴(kuò)展的布魯姆過濾器4。
