|
前言 Hello，大家好，歡迎來(lái)到我的 C++ 系列專題！今天的主題是布隆過(guò)濾器。 如果你沒(méi)聽(tīng)過(guò)布隆過(guò)濾器，沒(méi)關(guān)系，先來(lái)看這樣一個(gè)問(wèn)題：“如何從上億條數(shù)據(jù)中查找某個(gè)記錄是否存在？”你很容易想到的是數(shù)據(jù)庫(kù)或者哈希表。數(shù)據(jù)庫(kù)就不說(shuō)了，我們來(lái)談?wù)劰１怼Ａ私膺^(guò)哈希表的同學(xué)都知道，哈希節(jié)點(diǎn)里存儲(chǔ)了 key 和 value。如果每個(gè)節(jié)點(diǎn)里的 key 和 value 占用 10 個(gè)字節(jié)，那么 1 億條數(shù)據(jù)大約就要占用 1G，對(duì)于現(xiàn)代計(jì)算機(jī)來(lái)說(shuō)， 1G 其實(shí)不算大，但是它還是消耗了太多內(nèi)存，有沒(méi)有更好的解決方案呢？答案就是布隆過(guò)濾器。 布隆過(guò)濾器 布隆過(guò)濾器的實(shí)現(xiàn)依賴 bitset，關(guān)于什么是 bitset，請(qǐng)翻閱本專題系列之前的文章。 假設(shè)系統(tǒng)的最大數(shù)據(jù)量為 1 億，定義一個(gè)長(zhǎng)度為 5 億的 bit 數(shù)組。選擇一個(gè)哈希沖突比較小的哈希函數(shù)計(jì)算每一個(gè)數(shù)據(jù)的哈希值，并設(shè)置 bit 數(shù)組相應(yīng)哈希值位置的值為1。為了避免哈希沖突，我們用多個(gè)不同的哈希函數(shù)來(lái)計(jì)算同一個(gè)數(shù)據(jù)，來(lái)產(chǎn)生不同的哈希值，同時(shí)把這多個(gè)哈希值對(duì)應(yīng)的數(shù)組位置都置為1。為什么定義一個(gè)長(zhǎng)度為 5 億的 bitset，而不是 1 億呢？ 這也是為了減小沖突的一種方式（容量越大，沖突越?。?。當(dāng)一個(gè) 1 億條數(shù)據(jù)量級(jí)，5 億的 bit 數(shù)組占用內(nèi)存才幾百 M 而已，比哈希表要小一個(gè)數(shù)量級(jí)。 布隆過(guò)濾器的 C++ 實(shí)現(xiàn) #include <iostream>#include <bitset>#include <array>#include <string>#include <sstream>class Entity {};class BloomFilter {public: std::bitset<20> bits;public: BloomFilter () { bits.reset(); } void Set(std::string& key) { int idx1 = Hash1(key); int idx2 = Hash2(key); int idx3 = Hash3(key); int idx4 = Hash4(key); bits[idx1] = 1; bits[idx2] = 1; bits[idx3] = 1; bits[idx4] = 1; } bool Get(std::string& key) { int idx1 = Hash1(key); int idx2 = Hash2(key); int idx3 = Hash3(key); int idx4 = Hash4(key); return bits[idx1] && bits[idx2] && bits[idx3] && bits[idx4]; } int Hash1(std::string& key) { int hash = 5381; unsigned long count = key.size(); while (count > 0) { hash += (hash << 5) + key[key.size() - count]; count--; } return (hash & 0x7FFFFFFF) % bits.size(); } int Hash2(std::string& key) { int seed = 131; int hash = 0; std::string str = key + 'key2'; unsigned long count = str.size(); while(count > 0) { hash = hash * seed + str[str.size() - count]; count--; } return (hash & 0x7FFFFFFF) % bits.size(); } int Hash3(std::string& key) { int hash = 0; std::string str = key + 'keykey3'; unsigned long count = str.size(); for (int i = 0; i < count; i++) { if ((i * 1) == 0) { hash ^= ((hash << 7) ^ (str[i] ^ hash >> 3)); } else { hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5))); } count--; } return (hash & 0x7FFFFFFF) % bits.size(); } int Hash4(std::string key) { int hash = 5381; std::string str = key + 'keykeykey4'; unsigned long count = str.size(); while(count > 0) { hash += (hash << 5) + (str[str.size() - count]); count--; } return (hash & 0x7FFFFFFF) % bits.size(); }};int main(){ // 插入 hash 節(jié)點(diǎn) BloomFilter bf; Entity e1, e2; std::ostringstream oss; // 任意類型轉(zhuǎn)為 string 類型 oss << &e1; std::string s1 = oss.str(); if (bf.Get(s1) == true) { std::cout << 'objecy e1 has existed!' << std::endl; } else { std::cout << 'insert object e1' << std::endl; bf.Set(s1); std::cout << bf.bits << std::endl; } std::ostringstream oss2; // 任意類型轉(zhuǎn)為 string 類型 oss2 << &e2; std::string s2 = oss2.str(); if (bf.Get(s2) == true) { std::cout << 'objecy e2 has existed!' << std::endl; } else { std::cout << 'insert object e2' << std::endl; bf.Set(s1); std::cout << bf.bits << std::endl; } // 查找指定對(duì)象是否在數(shù)據(jù)庫(kù)中 if (bf.Get(s1) == true) { std::cout << 'objecy e1 has existed!' << std::endl; } else { std::cout << 'object e1 not existing' << std::endl; } std::cin.get();} 布隆過(guò)濾器示例 總結(jié)
|
|
|
