布隆過濾器

使用場景

布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)汹忠，旨在快速秉版、高效地判斷一個元素是否存在于一個集合中坐榆。

優(yōu)缺點

優(yōu)點當(dāng)然是時間復(fù)雜度很低.但他也有缺點础废，布隆過濾器是一個概率數(shù)據(jù)結(jié)構(gòu)：
它告訴我們拗馒，該元素要么肯定不在集合中(not_in)路星，要么可能(maybe_in)在集合中。(會告訴你maybe_in的概率.)

原理&實踐

布隆過濾器的基本數(shù)據(jù)結(jié)構(gòu)是一個比特數(shù)組诱桂。下面是一個demo數(shù)組洋丐，我們將用來演示。

image.png

該表中的每個空單元代表一個bit挥等，下面的數(shù)字則是其索引Index友绝。要向布隆過濾器添加一個元素，我們只需對其進(jìn)行幾次hash肝劲，并將這些hash結(jié)果所在的索引處的比特置為1迁客。

例如,我們把集合["yanxin","yanxiaori","yanbo"], 通過Fnv和Murmur計算后, 把結(jié)果添加到布隆數(shù)組中
(Fnv和Murmur是兩個簡單的哈希函數(shù)。)

image.png

當(dāng)你添加一個字符串時辞槐，你可以

image

看到哈希值給出的索引處的比特被設(shè)置為1掷漱。我用綠色來顯示新添加的，但任何彩色單元都只是1榄檬。

image.png

為了測試成員資格卜范，你只需用相同的哈希函數(shù)對字符串進(jìn)行哈希，然后看這些值是否在比特向量中被設(shè)置鹿榜。如果不是海雪，你就知道這個元素不在這個集合中。如果它們是舱殿，你只知道它可能是奥裸，因為另一個元素或其他元素的一些組合可能設(shè)置了相同的位。再一次怀薛，我們來演示一下刺彩。

image.png

以上就是布隆過濾器的基本概念.

高級

在我寫更多關(guān)于布魯姆過濾器的內(nèi)容之前，先聲明一下：我從來沒有在生產(chǎn)中使用過它們枝恋。請不要相信我的話创倔。我所要做的只是給你一個大致的概念，并指出你可以在哪里找到更多焚碌。

在下面的文字中畦攘，我們將提到一個有k個哈希值的布隆過濾器，過濾器中的m個比特十电，以及被插入的n個元素知押。

哈希函數(shù)

布隆過濾器中使用的哈希函數(shù)應(yīng)該是獨立的叹螟、均勻分布的。它們還應(yīng)該是盡可能快的（像sha1這樣的加密散列函數(shù)台盯，雖然被廣泛使用罢绽，但并不是很好的選擇）。

足夠獨立的快速静盅、簡單的哈希值的例子包括murmur良价、fnv系列的哈希值和HashMix。

要看到比加密哈希函數(shù)更快的區(qū)別蒿叠，請看這個故事明垢，當(dāng)把一個bloom filter的實現(xiàn)從md5切換到murmur時，速度提高了大約800%市咽。

在一個簡短的布隆過濾器實現(xiàn)的調(diào)查中痊银。

Chromium使用HashMix。(另外施绎，這里有一個關(guān)于他們?nèi)绾问褂胋loom filter的簡短描述)
python-bloomfilter使用加密的哈希值
Plan9使用Mitzenmacher 2005中提出的簡單哈希值
Sdroege Bloom filter使用fnv1a（包括在內(nèi)只是因為我想展示一個使用fnv的溯革。）
Squid使用MD5