一、問題概述
?????? 布隆過濾器是由布隆提出來的，是由一個很長的二進制序列和一系列的映射函數組成。主要用于檢測一個元素是否在一個集合中。當然在設計計算機軟件時，我們也經常會判斷一個元素是否在一個集合中。比如：在字處理軟件中，需要檢查一個英語單詞是否拼寫正確，（即是否在字典中），在網絡爬蟲里，這個網站是否被訪問過。最直接的方法就是將元素都存入計算機中，遇到一個新元素時，將它和元素進行比較即可。一般是用哈希表存儲的，因為它的查詢速度快，就是比較浪費空間。集合小的時候存儲效率還好，當集合大的時候，存儲效率低的問題就顯現出來了。再比如，對于一個像 Yahoo,Hotmail 和 Gmai 那樣的公眾電子郵件提供商，總是需要過濾來自發送垃圾郵件的人的垃圾郵件。這時，我們就得記錄那些發垃圾郵件的Email地址，由于那些發送者不停地在注冊新的地址，全世界少說也有幾十億個發垃圾郵件的地址，將他們都存起來則需要大量的網絡服務器。如果用哈希表，每存儲一億個email地址，就需要1.6GB 的內存，因此存貯幾十億個郵件地址可能需要上百GB的內存。除非是超級計算機，一般服務器是無法存儲的。所以在這里我們就引入了布隆過濾器來處理這些問題。
二、布隆過濾器的基本思想
?????? 如果想判斷一個元素是不是在一個集合里，一般想到的是將所有元素保存起來，然后通過比較確定。鏈表，樹等等數據結構都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。不過世界上還有一種叫作散列表（又叫哈希表，Hash table）的數據結構。它可以通過一個Hash函數將一個元素映射成一個位陣列（Bit Array）中的一個點。這樣一來，我們只要看看這個點是不是1就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。
?????? 布隆過濾器是一種空間效率很高的數據結構。也可以看做是位圖BitMap的擴展（位圖鏈接）：
當一個元素加入集合中時，通過k個不同的哈希函數將這個元素映射成一個位數組的k個點，把它們置為1。當我們檢測看一個元素存不存在時，只需要看那k個位是否為1就可以了。主要分為兩點：
1、如果這k個位中，只要有一個位為0，就說明此元素不在集合中；
2、如果k個位都為1的話，表明此元素可能存在集合中。
第二點又體現了布隆過濾器的一個缺點：存在一定的誤判率。但是為了盡可能的降低這種誤判率，我們采用上述多個哈希函數檢測的方式。經研究表明，可將誤判率降低到萬分之一以下。
同時，布隆過濾器的優點也是非常顯著的。它的空間效率和查詢時間都遠遠超過一般的算法。存儲空間和插入/查詢時間都是常數（O(k)）。
還有重要的一點是，一般情況下，布隆過濾器不支持刪除操作，起初，有人會想到使用計數方式將位++或--來刪除元素。但是由于布隆過濾器的誤判，你可能會把錯誤的元素刪除。（下節我們會分析到這類問題哦）
三、實現代碼（vs2013）
//HashFunc.h
#pragma once
#include<string>
#include<iostream>
using namespace std;/// @brief BKDR Hash Function /// @detail 本 算法由于在Brian Kernighan與Dennis Ritchie的《The C Programming Language》一書被展示而得 名，是一種簡單快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子為31）。 template<class T> size_t BKDRHash(const T *str) { register size_t hash = 0; while (size_t ch = (size_t)*str++) { hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313.. // 有人說將乘法分解為位運算及加減法可以提高效率，如將上式表達為：hash = hash << 7 + hash << 1 + hash + ch; // 但其實在Intel平臺上，CPU內部對二者的處理效率都是差不多的， // 我分別進行了100億次的上述兩種運算，發現二者時間差距基本為0（如果是Debug版，分解成位運算后的耗時還要高1/3）； // 在ARM這類RISC系統上沒有測試過，由于ARM內部使用Booth's Algorithm來模擬32位整數乘法運算，它的效率與乘數有關： // 當乘數8-31位都為1或0時，需要1個時鐘周期 // 當乘數16-31位都為1或0時，需要2個時鐘周期 // 當乘數24-31位都為1或0時，需要3個時鐘周期 // 否則，需要4個時鐘周期 // 因此，雖然我沒有實際測試，但是我依然認為二者效率上差別不大 } return hash; } /// @brief SDBM Hash Function /// @detail 本算法是由于在開源項目SDBM（一種簡單的數據庫引擎）中被應用而得名，它與BKDRHash思想一致，只是種子不同而已。 template<class T> size_t SDBMHash(const T *str) { register size_t hash = 0; while (size_t ch = (size_t)*str++) { hash = 65599 * hash + ch; //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash; } return hash; } /// @brief RS Hash Function /// @detail 因Robert Sedgwicks在其《Algorithms in C》一書中展示而得名。 template<class T> size_t RSHash(const T *str) { register size_t hash = 0; size_t magic = 63689; while (size_t ch = (size_t)*str++) { hash = hash * magic + ch; magic *= 378551; } return hash; } /// @brief AP Hash Function /// @detail 由Arash Partow發明的一種hash算法。 template<class T> size_t APHash(const T *str) { register size_t hash = 0; size_t ch; for (long i = 0; ch = (size_t)*str++; i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ ch ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ ch ^ (hash >> 5))); } } return hash; } /// @brief JS Hash Function /// 由Justin Sobel發明的一種hash算法。 template<class T> size_t JSHash(const T *str) { if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0 return 0; register size_t hash = 1315423911; while (size_t ch = (size_t)*str++) { hash ^= ((hash << 5) + ch + (hash >> 2)); } return hash; } /// @brief DEK Function /// @detail 本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。 template<class T> size_t DEKHash(const T* str) { if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0 return 0; register size_t hash = 1315423911; while (size_t ch = (size_t)*str++) { hash = ((hash << 5) ^ (hash >> 27)) ^ ch; } return hash; } /// @brief FNV Hash Function /// @detail Unix system系統中使用的一種著名hash算法，后來微軟也在其hash_map中實現。 template<class T> size_t FNVHash(const T* str) { if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0 return 0; register size_t hash = 2166136261; while (size_t ch = (size_t)*str++) { hash *= 16777619; hash ^= ch; } return hash; } /// @brief DJB Hash Function /// @detail 由Daniel J. Bernstein教授發明的一種hash算法。 template<class T> size_t DJBHash(const T *str) { if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0 return 0; register size_t hash = 5381; while (size_t ch = (size_t)*str++) { hash += (hash << 5) + ch; } return hash; } /// @brief DJB Hash Function 2 /// @detail 由Daniel J. Bernstein 發明的另一種hash算法。 template<class T> size_t DJB2Hash(const T *str) { if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0 return 0; register size_t hash = 5381; while (size_t ch = (size_t)*str++) { hash = hash * 33 ^ ch; } return hash; } /// @brief PJW Hash Function /// @detail 本算法是基于AT&T貝爾實驗室的Peter J. Weinberger的論文而發明的一種hash算法。 template<class T> size_t PJWHash(const T *str) {static const size_t TotalBits = sizeof(size_t) * 8; static const size_t ThreeQuarters = (TotalBits * 3) / 4; static const size_t OneEighth = TotalBits / 8; static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth); register size_t hash = 0; size_t magic = 0; while (size_t ch = (size_t)*str++) { hash = (hash << OneEighth) + ch; if ((magic = hash & HighBits) != 0) { hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits)); } } return hash; } /// @brief ELF Hash Function /// @detail 由于在Unix的Extended Library Function被附帶而得名的一種hash算法，它其實就是PJW Hash的變形。 template<class T> size_t ELFHash(const T *str) { static const size_t TotalBits = sizeof(size_t) * 8; static const size_t ThreeQuarters = (TotalBits * 3) / 4; static const size_t OneEighth = TotalBits / 8; static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth); register size_t hash = 0; size_t magic = 0; while (size_t ch = (size_t)*str++) { hash = (hash << OneEighth) + ch; if ((magic = hash & HighBits) != 0) { hash ^= (magic >> ThreeQuarters); hash &= ~magic; } } return hash; } //BloomFilter.h
#pragma once
#include<string>
#include<iostream>
using namespace std;
#include"BitMap.h"
#include"HashFunc.h"
struct _HashFunc1
{size_t operator()(const string& s){return BKDRHash(s.c_str());}
};struct _HashFunc2
{size_t operator()(const string& s){return SDBMHash(s.c_str());}
};struct _HashFunc3
{size_t operator()(const string& s){return RSHash(s.c_str());}
};struct _HashFunc4
{size_t operator()(const string& s){return APHash(s.c_str());}
};struct _HashFunc5
{size_t operator()(const string& s){return JSHash(s.c_str());}
};template<class K = string,
class HashFunc1 = _HashFunc1,
class HashFunc2 = _HashFunc2,
class HashFunc3 = _HashFunc3,
class HashFunc4 = _HashFunc4,
class HashFunc5 = _HashFunc5
>
class BloomFilter
{
public:BloomFilter(size_t Num):_bm(Num*5*2),_size(Num*5*2){}void BloomSet(const K& key){size_t Hash1 = HashFunc1()(key)%_size;size_t Hash2 = HashFunc2()(key)%_size;size_t Hash3 = HashFunc3()(key)%_size;size_t Hash4 = HashFunc4()(key)%_size;size_t Hash5 = HashFunc5()(key)%_size;_bm.Set(Hash1);_bm.Set(Hash2);_bm.Set(Hash3);_bm.Set(Hash4);_bm.Set(Hash5);}bool Test(const K& key){size_t Hash1 = HashFunc1()(key)%_size;if(_bm.Test(Hash1) == false){return false;}size_t Hash2 = HashFunc2()(key)%_size;if(_bm.Test(Hash2) == false){return false;}size_t Hash3 = HashFunc3()(key)%_size;if(_bm.Test(Hash3) == false){return false;}size_t Hash4 = HashFunc4()(key)%_size;if(_bm.Test(Hash4) == false){return false;}size_t Hash5 = HashFunc5()(key)%_size;if(_bm.Test(Hash5) == false){return false;}return true;}
private:BitMap _bm;size_t _size;
};void BloomFilterTest()
{BloomFilter<> bm(1024);bm.BloomSet("11111");bm.BloomSet("11110");bm.BloomSet("11112");bm.BloomSet("11113");cout<<bm.Test("11111")<<endl;cout<<bm.Test("11101")<<endl;cout<<bm.Test("11102")<<endl;cout<<bm.Test("11113")<<endl;}四、運行結果
和waitpid()的參數解析)
的解釋與實踐)
)
![[WPS筆試題]實現棧的push,pop,max且時間復雜度為O（1）](http://pic.xiahunao.cn/[WPS筆試題]實現棧的push,pop,max且時間復雜度為O（1）)
![[劍指Offer]替換空格](http://pic.xiahunao.cn/[劍指Offer]替換空格)