? 過濾器在數(shù)據(jù)科學(xué)中的應(yīng)用十分廣泛，包括數(shù)據(jù)庫查詢、數(shù)據(jù)快速檢索，數(shù)據(jù)去重等等。過濾器的出現(xiàn)是為了解決在大量數(shù)據(jù)的環(huán)境下，能夠更好更快的（節(jié)省計算資源或者存儲資源）篩查數(shù)據(jù)的需求。
實際的應(yīng)用場景有：
爬蟲程序的URL識別：即爬蟲在訪問 URL 時對 URL 進行判斷，如果訪問過(在集合中)就不訪問，如果沒有訪問過那么就訪問然后放入已訪問集合，提高爬蟲效率。
垃圾郵件地址的儲存，如何判斷一封郵件是否是垃圾郵件，這樣要對郵件地址進行判斷，看看是否是在垃圾郵件地址集合中。但實際上郵件地址太多，如果全部儲存的話占用大量存儲資源并且在比較的時候也會占用大量的計算資源，所以用過濾器來存儲判斷可以解決問題。
在 LevelDB 數(shù)據(jù)庫引擎中使用了 LSM tree，由于設(shè)計時為了優(yōu)化寫性能抑制了讀性能，在磁盤中（sstable）查找 key 時（雖然已經(jīng)使用文件索引并且定期合并文件來減少文件的數(shù)量，但是面對海量數(shù)據(jù)增量時還是捉襟見肘）使用 Bloom filter 這種在內(nèi)存中的高效方法來判斷文件中是否包含key。
? 以下介紹最基本的兩個過濾器，幫助大家理解過濾器技術(shù)的實現(xiàn)。
Bloom filter
? Bloom filter 使用 hash 函數(shù)的散列技術(shù)存儲信息的存在狀態(tài)而不是存儲信息本身，常常用于判斷一個信息是否在一個集合中，這樣只需要幾個bit的空間就能解決問題。
基本原理
? bloom filter作為一種海量數(shù)據(jù)處理算法，其要點在于用于存儲的位數(shù)組和用于處理的hash函數(shù)（一般有多個，并且為了精確度和數(shù)據(jù)量增加）。
初始化存儲空間：bloom filter首先在內(nèi)存中開辟一塊儲存空間，并將里面的bit位全部置為0，表示尚未有數(shù)據(jù)進行處理或者儲存。
映射集合中的數(shù)據(jù)：bloom filter通過設(shè)置k個hash函數(shù)，將一個集合中的所有數(shù)據(jù)或者說信息映射到儲存空間中，被映射到的區(qū)域bit位設(shè)置為1。
判斷數(shù)據(jù)是否屬于集合：假設(shè)任何一個信息或者數(shù)據(jù)key，要判斷其是否在集合中，bloom filter將key帶入k個hash函數(shù)進行映射（fi=fi(key)）,然后判斷其映射到的區(qū)域是否全部為1，如果全部為1，那么信息或者數(shù)據(jù)key表示在集合中，只要有一個映射位置為0，那么表示信息或者數(shù)據(jù)key不在集合中。
優(yōu)缺點
優(yōu)點：存儲數(shù)據(jù)量小，節(jié)省存儲及計算空間
缺點：只能對集合添加元素，無法刪除（也并非完全不能，可以使用 bloom filter 的變種 CounterBloom Filte，該過濾器給每一位存儲空間分配一個計數(shù)空間，每次刪除時候計數(shù)減1。這個計數(shù)空間通常需要4位計數(shù)16則溢出，具體見這篇博客。另外根據(jù)數(shù)據(jù)量，在滿足一定錯誤率的情況下 hash 函數(shù)個數(shù) k 需要變動。
Cuckoo filter理解
原理
? Cuckoo filter 同樣使用哈希表來實現(xiàn)數(shù)據(jù)到實際存儲區(qū)域的映射，不同于 Bloom filer 的是Cuckoo filter中只采用兩個哈希映射函數(shù) H1 和 H2，H3用于計算數(shù)據(jù)的 fingerprint，減小存儲量。他們的關(guān)系如下：
H1(key) = hash1(key)
H2(key) = H1(key) xor H1(key’s fingerprint)
H3(key) = key’s fingerprint = hash(key)
? 當一個數(shù)據(jù)需要存儲的時候，Cuckoo filter 使用兩個哈希函數(shù)進行映射，只要有一個映射到的區(qū)域為空，那么就將數(shù)據(jù)的指紋信息存儲到相應(yīng)的區(qū)域。如果兩個區(qū)域都被占用，那么將原來占有那個存儲區(qū)域的數(shù)據(jù)指紋踢出存儲區(qū)用來存儲新到的數(shù)據(jù)，原來的數(shù)據(jù)重新使用另外一個哈希函數(shù)映射存儲，依次反復(fù)。
? 當然這個過程可能無限反復(fù)下去，那么一般會對踢出操作設(shè)一個閾值，超過閾值則認為過濾器容量不足，需要對其進行擴容。
? 這個踢出的過程類似于布谷鳥下蛋的過程，所以稱其為布谷鳥過濾器。
附：散列技術(shù)
? 散列技術(shù)（也就是 hash 映射）因為在 bloom 過濾器 與 cuckoo 過濾器中就使用到了 hash 技術(shù)去映射
主要是散列表查找（哈希表）：
引入
? 在順序表查找（逐個比較）乃至有序表查找（折半查找）的時候難免需要使用比較，但這太消耗資源，考慮一種方法通過關(guān)鍵字Key直接得到想要查找的記錄內(nèi)存存儲的位置:存儲位置 = f（關(guān)鍵字Key）
? 這樣不需要比較就能獲得需要記錄的儲存位置，通過一個f（key）映射關(guān)系就能查找到儲存位置，這種用于存儲的技術(shù)稱之為散列技術(shù)，其中f為hash函數(shù)。散列技術(shù)既是存儲方法，又是查找方法
? 最適合精確查找，也就是查找與給定值相等的記錄。
? 不適合一個關(guān)鍵字對應(yīng)多個記錄（set is a class，key = 男）以及范圍查找（set is a class，Q：18<age<20）。
? 設(shè)計一個簡單、均勻、存儲利用率高的散列函數(shù)是關(guān)鍵。散列函數(shù)的構(gòu)造方法
- 設(shè)計原則：計算簡單（提高效率）、散列地址分布均勻（存儲空間的利用率）
1.直接定址法：f(key) = key
f(key) = a * key + b( a、b為常數(shù) )
2.數(shù)字分析法：數(shù)字反轉(zhuǎn)（1234 -> 4321）、環(huán)形位移(1234 -> 4123)
3.折疊法：分解數(shù)字相加(或者別的運算)（9876543210 -> 987+654+321+0）
4.除留余數(shù)法：f(key) = key mod p (p<=m)
5.隨機數(shù)法：f(key) = random(key)
如果是字符串或者中文可以轉(zhuǎn)化為ASCII或者Unicode碼來使用上面介紹的方法。
-
處理散列沖突的方法
如果兩個以上的關(guān)鍵字通過hash函數(shù)映射后都指向一個儲存地址的話，那就會產(chǎn)生沖突，所以解決沖突也是一個關(guān)鍵問題。
1.·開放定址法：fi(key) = (f(key) + di) mod m (di = 1,2,3,...,m-1)
·二次探測(不會讓關(guān)鍵字都聚集在一個區(qū)域)：fi(key) = (f(key) + di) mod m (di = 1^2,-1^2,2^2,-2^2,...,q^2,-q^2,q<=m/2)
·隨機產(chǎn)生di:fi(key) = (f(key) + di) mod m (di是一個隨機數(shù)列）
2.再散列函數(shù)法：fi(key) = RHi(key) (i =1,2,...k)
3.鏈地址法：在原地址制造鏈表存儲，沖突時就是為鏈表添加節(jié)點
4.公共溢出法，就是為沖突的區(qū)域（信息）制造一個統(tǒng)一存儲的區(qū)域
參考資料
[1]BURTON H. BLOOM，Space/Time Trade-offs in Hash Coding with Allowable Errors[J] Communications of the ACM，1970.7，Volume 13 / Number 7，page：422-426
[2]真實的歸宿 ，海量數(shù)據(jù)處理算法—Bloom Filter,2012-08-14 18:40
[3]劉愛貴 ，深入理解Bloom Filter,2011-07-13 12:40:43
[4] 蒼梧 ，BloomFilter——大規(guī)模數(shù)據(jù)處理利器,2011-01-02 19:08
