<<數學之美>>中23章介紹的布隆過濾器（Bloom filter），以下是一些算法的實現及應用

1.算法應用

在如那件設計中有個最基本的功能是判斷某個元素是否在集合當中，比如爬蟲中驗證一個url是否被收錄過，如果用普通的hash來判斷那需要的內存容量是驚人的。布隆過濾器的作用就是能夠降低內存用量，他只需要hash表的1/8到1/4就能夠解決問題。

3.算法實現

3.1生成指紋函數，這裏做了一個簡化

void make_fingers(const string &url, const vector&fingers){
    for (int i=0; i

3.2生成映射，將八個指紋映射到1~MAX中的一個自然數，這裏的MAX只取到了10000，實際操作中這個數一般為16億

void make_map(const vector fingers,bitset&result) {
    for(int i=0; i

3.3 驗證函數，驗證url是否能夠匹配到

bool veri_url(const string & url, const bitset result) {
    vectorfingers;
    make_fingers(url, fingers);
    for(int i=; i

3.4 主函數

int main(int argc, char * argv[])
{
    // 需要hash的字符串
    string url = "http://yancey.sinaapp.com";
    // 保存指紋信息
    vector fingers;
    // 保存結果的向量，該向量每個比特位的初始值為0
    bitset result;
    result.reset();
    // First Step 產生八個指紋信息
    make_fingers(url, fingers);
    // Second Step 將這八個指紋信息用一個hash函數對應到1~MAX中的八個自然數.並將Bit向量中這八位設置為1
    make_map(fingers, result);
    // 驗證剛才的url
    cout << veri_url(url, result) << endl;
    return 0;
};