C++ 數(shù)據(jù)結(jié)構(gòu)之布隆過(guò)濾器
布隆過(guò)濾器
一、歷史背景知識(shí)
布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除錯(cuò)誤。而這個(gè)缺點(diǎn)是不可避免的。但是絕對(duì)不會(huì)出現(xiàn)識(shí)別錯(cuò)誤的情況出現(xiàn)（即假反例False negatives,如果某個(gè)元素確實(shí)沒(méi)有在該集合中，那么Bloom Filter 是不會(huì)報(bào)告該元素存在集合中的，所以不會(huì)漏報(bào)）
在 FBI，一個(gè)嫌疑人的名字是否已經(jīng)在嫌疑名單上；在網(wǎng)絡(luò)爬蟲(chóng)里，一個(gè)網(wǎng)址是否被訪(fǎng)問(wèn)過(guò)等等。最直接的方法就是將集合中全部的元素存在計(jì)算機(jī)中，遇到一個(gè)新 元素時(shí)，將它和集合中的元素直接比較即可。一般來(lái)講，計(jì)算機(jī)中的集合是用哈希表（hash table）來(lái)存儲(chǔ)的。它的好處是快速準(zhǔn)確，缺點(diǎn)是費(fèi)存儲(chǔ)空間。當(dāng)集合比較小時(shí)，這個(gè)問(wèn)題不顯著，但是當(dāng)集合巨大時(shí)，哈希表存儲(chǔ)效率低的問(wèn)題就顯現(xiàn)出來(lái) 了。
比如說(shuō)，一個(gè)象 Yahoo,Hotmail 和 Gmai 那樣的公眾電子郵件（email）提供商，總是需要過(guò)濾來(lái)自發(fā)送垃圾郵件的人（spamer）的垃圾郵件。一個(gè)辦法就是記錄下那些發(fā)垃圾郵件的 email 地址。由于那些發(fā)送者不停地在注冊(cè)新的地址，全世界少說(shuō)也有幾十億個(gè)發(fā)垃圾郵件的地址，將他們都存起來(lái)則需要大量的網(wǎng)絡(luò)服務(wù)器。如果用哈希表，每存儲(chǔ)一億 個(gè) email 地址， 就需要 1.6GB 的內(nèi)存（用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè) email 地址對(duì)應(yīng)成一個(gè)八字節(jié)的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲(chǔ)效率一般只有 50%，因此一個(gè) email 地址需要占用十六個(gè)字節(jié)。一億個(gè)地址大約要 1.6GB， 即十六億字節(jié)的內(nèi)存）。因此存貯幾十億個(gè)郵件地址可能需要上百 GB 的內(nèi)存。除非是超級(jí)計(jì)算機(jī)，一般服務(wù)器是無(wú)法存儲(chǔ)的［2］。
二、布隆過(guò)濾器原理以及優(yōu)缺點(diǎn)
如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表、樹(shù)、散列表（哈希表，Hash table）等數(shù)據(jù)結(jié)構(gòu)都是這種思想。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來(lái)越大。同時(shí)檢索速度也會(huì)越來(lái)越慢。
Bloom Filter 是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，Bloom Filter 可以看做是對(duì)bit-map的擴(kuò)展，它的原理是：
當(dāng)一個(gè)元素被加入集合中時(shí)，通過(guò)K個(gè)hash函數(shù)將這個(gè)元素映射成一個(gè)位陣列（Bit array）中的K個(gè)點(diǎn)，將它們置成1. 檢索時(shí)，我們只需要看這些點(diǎn)是不是都是1就能（大約）知道集合中有沒(méi)有它：
如果這些點(diǎn)中有任何一個(gè)0，則被檢索元素一定不在；
如果都是1，則被檢索元素很可能在。
優(yōu)點(diǎn)：
它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，布隆過(guò)濾器存儲(chǔ)空間和插入\查詢(xún)時(shí)間都是O(K),另外，散列函數(shù)相互之間沒(méi)有關(guān)系，方便硬件并行實(shí)現(xiàn)，布隆過(guò)濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)。
缺點(diǎn)：
1、布隆過(guò)濾器的缺點(diǎn)和優(yōu)點(diǎn)同樣明顯。誤算率是其中之一。隨著存入元素的增加，誤算率隨之增加。但是元素?cái)?shù)量太少，則使用散列就可以了。
2、一般情況下不能從布隆過(guò)濾器中刪除元素，我們很容易想到把位數(shù)組變成整數(shù)數(shù)組，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加1，這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了。然而要保證安全地刪除元素并非這么簡(jiǎn)單。首先我們必須保證刪除的元素的確存在布隆過(guò)濾器里面，另外計(jì)數(shù)器回繞也會(huì)造成問(wèn)題。
三、example
Google Chrome瀏覽器使用Bloom filter識(shí)別惡意鏈接（能用較小的存儲(chǔ)空間表示較大的數(shù)據(jù)集合，簡(jiǎn)單想就是把 每一個(gè)URL都可以映射成bit）的多，并且誤判率在萬(wàn)分之一以下。
C++實(shí)現(xiàn)
bit_set.h
#pragma once
#include<iostream>
using namespace std;
#include<vector>
class Bitset
{
public:
Bitset(size_t value)
{
_a.resize((value >> 5) + 1, 0);
}
bool set(size_t num)
{
size_t index = num>>5;
size_t pos = num % 32;
if (_a[index] & (1 << (31 - pos)))
{
return false;
}
else
{
_a[index] |= (1 << (31 - pos));
_size++;
return true;
}
}
bool Reset(size_t num)
{
size_t index = num >> 5;
size_t pos = num % 32;
if (Text(num))
{
_a[index] &= ~(1 << (31 - pos));
_size--;
return true;
}
else
{
return false;
}
}
bool Text(size_t num)
{
size_t index = num >> 5;
size_t pos = num % 32;
return _a[index] & (1 << (31-pos));
}
private:
vector<int> _a;
size_t _size;
};
Hash.h
#pragma once
template<class T> //各類(lèi)哈希字符串轉(zhuǎn)換函數(shù)
size_t BKDRHash(const char *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch;
}
return hash;
}
template<class T>
size_t SDBMHash(const char *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
}
return hash;
}
template<class T>
size_t RSHash(const char * str)
{
size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
template<class T>
size_t APHash(const char *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;
}
template<class T>
size_t JSHash(const char* str)
{
if (!*str)
{
return 0;
}
size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
Bloom_Filter.h
#pragma once
#include"bite_set.h"
#include"Hash.h"
#include<string>
template<class T>
struct __HashFunk1
{
size_t operator()(const T& key)
{
return BKDRHash<T>(key.c_str());
}
};
template<class T>
struct __HashFunk2
{
size_t operator()(const T& key)
{
return SDBMHash<T>(key.c_str());
}
};
template<class T>
struct __HashFunk3
{
size_t operator()(const T& key)
{
return RSHash<T>(key.c_str());
}
};
template<class T>
struct __HashFunk4
{
size_t operator()(const T& key)
{
return APHash<T>(key.c_str());
}
};
template<class T>
struct __HashFunk5
{
size_t operator()(const T& key)
{
return JSHash<T>(key.c_str());
}
};
template<class K = string,
class HashFunk1 = __HashFunk1<K>,
class HashFunk2 = __HashFunk2<K>,
class HashFunk3 = __HashFunk3<K>,
class HashFunk4 = __HashFunk4<K>,
class HashFunk5 = __HashFunk5<K>>
class BoolFilter
{
public:
BoolFilter(size_t n)
:_a(n * 10)
, _range(n * 10)
{}
void set(const K& key)
{
_a.set(HashFunk1()(key) % _range);
_a.set(HashFunk2()(key) % _range);
_a.set(HashFunk3()(key) % _range);
_a.set(HashFunk4()(key) % _range);
_a.set(HashFunk5()(key) % _range);
}
bool Text(const K& key)
{
if (!_a.Text(HashFunk1()(key)% _range))
return false;
if (!_a.Text(HashFunk2()(key) % _range))
return false;
if (!_a.Text(HashFunk3()(key) % _range))
return false;
if (!_a.Text(HashFunk4()(key) % _range))
return false;
if (!_a.Text(HashFunk5()(key) % _range))
return false;
return true;
}
private:
Bitset _a;
size_t _range;
};
相關(guān)文章
詳解C語(yǔ)言中for循環(huán)與while循環(huán)的用法
這篇文章主要通過(guò)幾個(gè)示例為大家介紹一下C語(yǔ)言中for循環(huán)與while循環(huán)的用法以及二者的區(qū)別，文中的代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C語(yǔ)言有一定幫助，需要的可以參考一下2022-07-07
C++中用new創(chuàng)建二維數(shù)組和指針數(shù)組實(shí)例代碼
這篇文章主要介紹了C++中用new創(chuàng)建二維數(shù)組和指針數(shù)組實(shí)例代碼，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友參考下2017-03-03
vscode?采用C++17版本進(jìn)行編譯的實(shí)現(xiàn)
本文主要介紹了vscode?采用C++17版本進(jìn)行編譯，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
C語(yǔ)言實(shí)現(xiàn)六邊形掃雷游戲的示例代碼
所謂六邊形掃雷，就是沒(méi)有掃雷模式的消零算法，每一個(gè)安全的點(diǎn)都需要單獨(dú)挖出來(lái)，一次顯示一個(gè)格子，感興趣的小伙伴可以跟隨小編一起了解一下2022-12-12
C語(yǔ)言通過(guò)三種方法實(shí)現(xiàn)屬于你的通訊錄
本文將實(shí)現(xiàn)一個(gè)通訊錄，來(lái)實(shí)現(xiàn)人員的增刪插改功能。文中通過(guò)三種形式來(lái)實(shí)現(xiàn)用戶(hù)的增刪插改，其實(shí)也就是一點(diǎn)點(diǎn)的優(yōu)化版本，從靜態(tài)的實(shí)現(xiàn)，到動(dòng)態(tài)的實(shí)現(xiàn)，最后以文件的形式來(lái)完成，請(qǐng)大家和我一起往下看吧2022-11-11
圣誕節(jié)快到了，讓我們用C語(yǔ)言制作一個(gè)圣誕表白程序吧，下面通過(guò)本文學(xué)習(xí)下實(shí)現(xiàn)代碼2016-12-12
C語(yǔ)言實(shí)現(xiàn)求梅森素?cái)?shù)的代碼與解析
這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言實(shí)現(xiàn)求梅森素?cái)?shù)的代碼與解析，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-12-12
VS2019項(xiàng)目打包生成.exe文件與Setup的步驟實(shí)現(xiàn)
這篇文章主要介紹了VS2019項(xiàng)目打包生成.exe文件與Setup的步驟實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
C++和OpenCV實(shí)現(xiàn)圖像字符化效果
圖像字符化的意思是將圖像以字符形式呈現(xiàn)，具有一定的娛樂(lè)價(jià)值，許多開(kāi)發(fā)人員通過(guò)python實(shí)現(xiàn)該功能，C++實(shí)現(xiàn)的代碼較少，因此本文通過(guò)C++和OpenCV實(shí)現(xiàn)，給予C++開(kāi)發(fā)人員一些可供借鑒的思路，需要的朋友可以參考下2022-06-06
C語(yǔ)言字符函數(shù)isalnum()和iscntrl()詳解
大家好，本篇文章主要講的是C語(yǔ)言字符函數(shù)isalnum()和iscntrl()詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下2022-02-02