|
前言 Hello，大家好，歡迎來到我的 C++ 系列專題！今天的主題是布隆過濾器。 如果你沒聽過布隆過濾器，沒關(guān)系，先來看這樣一個問題：“如何從上億條數(shù)據(jù)中查找某個記錄是否存在？”你很容易想到的是數(shù)據(jù)庫或者哈希表。數(shù)據(jù)庫就不說了，我們來談?wù)劰１?。了解過哈希表的同學(xué)都知道，哈希節(jié)點里存儲了 key 和 value。如果每個節(jié)點里的 key 和 value 占用 10 個字節(jié)，那么 1 億條數(shù)據(jù)大約就要占用 1G，對于現(xiàn)代計算機來說， 1G 其實不算大，但是它還是消耗了太多內(nèi)存，有沒有更好的解決方案呢？答案就是布隆過濾器。 布隆過濾器 布隆過濾器的實現(xiàn)依賴 bitset，關(guān)于什么是 bitset，請翻閱本專題系列之前的文章。 假設(shè)系統(tǒng)的最大數(shù)據(jù)量為 1 億，定義一個長度為 5 億的 bit 數(shù)組。選擇一個哈希沖突比較小的哈希函數(shù)計算每一個數(shù)據(jù)的哈希值，并設(shè)置 bit 數(shù)組相應(yīng)哈希值位置的值為1。為了避免哈希沖突，我們用多個不同的哈希函數(shù)來計算同一個數(shù)據(jù)，來產(chǎn)生不同的哈希值，同時把這多個哈希值對應(yīng)的數(shù)組位置都置為1。為什么定義一個長度為 5 億的 bitset，而不是 1 億呢？ 這也是為了減小沖突的一種方式（容量越大，沖突越小）。當(dāng)一個 1 億條數(shù)據(jù)量級，5 億的 bit 數(shù)組占用內(nèi)存才幾百 M 而已，比哈希表要小一個數(shù)量級。 布隆過濾器的 C++ 實現(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é)點 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; } // 查找指定對象是否在數(shù)據(jù)庫中 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();} 布隆過濾器示例 總結(jié)
|
|
|
