C++位圖/布隆過濾器/海量數據處理

@TOC

零、前言

本章主要講解C++中對哈希的應用有關方面的內容，位圖，布隆，海量數據處理

一、位圖

1、位圖概念

位圖概念：

位圖其實就是哈希的變形，同樣通過映射來處理數據，只不過位圖本身并不存儲數據，而是存儲標記

通過一個比特位來標記這個數據是否存在，1代表存在，0代表不存在

位圖通常情況下用在數據量龐大，且數據不重復的情景下判斷某個數據是否存在

相關面試題描述：

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中

注意：

遍歷時間復雜度O(N)；排序(O(NlogN))利用二分查找: logN；這兩種方式除了效率不夠高，還有個問題是內存無法完全同時加載這給40億個不重復的無符號整數

10億個整數為40億字節，而10億字節為1G，所以40億個整數需要16G大小空間

位圖解決方案：

數據是否在給定的整形數據中，結果是在或者不在，剛好是兩種狀態

那么可以使用一個二進制比特位來代表數據是否存在的信息，如果二進制比特位為1，代表存在，為0代表不存在

示圖：小端平臺上

2、位圖接口的介紹以及實現

bitset中常用的成員函數如下：

使用示例：

#include #include using namespace std; int main() { bitset<8> bs; bs.set(2); //設置第2位 bs.set(4); //設置第4位 cout << bs << endl; //00010100 bs.flip(); //反轉所有位 cout << bs << endl; //11101011 cout << bs.count() << endl; //6 cout << bs.test(3) << endl; //1 bs.reset(0); //清空第0位 cout << bs << endl; //11101010 bs.flip(7); //反轉第7位 cout << bs << endl; //01101010 bs.reset(); //清空所有位 cout << bs.none() << endl; //1 bs.set(); //設置所有位 cout << bs.all() << endl; //1 return 0; }

注：使用成員函數set、reset、flip時，若指定了某一位則操作該位，若未指定位則操作所有位

位圖的簡單實現：

對于底層來說一個位代表一個數的映射，那么我們以char類型來開辟對應需要空間，同時用vector進行管理

對于開辟空間，一個char類型有8個位，所以需要個數/8即為需要開辟的大小，但是整數相除為向下取整，所以需要我們多開一個空間出來

實現代碼：

template class bitset { public: bitset() { _bits.resize(N / 8 + 1,0);//開辟空間并置為0 //_bits.resize((N >> 3) + 1,0); } bool test(size_t x) { size_t i = x / 8;//處于的該數組的第幾個空間 size_t j = x % 8;//處于的該空間的第幾個比特位 return _bits[i] & (1 << j); } void set(size_t x) { size_t i = x / 8;//處于的該數組的第幾個空間 size_t j = x % 8;//處于的該空間的第幾個比特位 _bits[i] |= (1 << j);//該位置置為1 } void reset(size_t x) { size_t i = x / 8;//處于的該數組的第幾個空間 size_t j = x % 8;//處于的該空間的第幾個比特位 _bits[i] &= (~(1 << j));//該位置置為0 } private: vector _bits; };

3、位圖的應用

快速查找某個數據是否在一個集合中

排序

求兩個集合的交集、并集等

操作系統中磁盤塊標記

二、布隆過濾器

1、布隆過濾器概念和介紹

布隆過濾器的提出：

我們在使用新聞客戶端看新聞時，它會給我們不停地推薦新的內容，它每次推薦時要去重，去掉那些已經看過的內容。問題來了，新聞客戶端推薦系統如何實現推送去重的？

用服務器記錄了用戶看過的所有歷史記錄，當推薦系統推薦新聞時會從每個用戶的歷史記錄里進行篩選，過濾掉那些已經存在的記錄

如何快速查找：

用哈希表存儲用戶記錄，缺點：浪費空間

用位圖存儲用戶記錄，缺點：不能處理哈希沖突

將哈希與位圖結合，即布隆過濾器

布隆過濾器概念：

布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數據結構

特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”

它是用多個哈希函數，將一個數據映射到位圖結構中的不同位置上，不僅可以提升查詢效率，也可以節省大量的內存空間

示圖：

位圖中的哈希沖突：

當字符串使用哈希時，無可避免的會出現哈希沖突的問題（可能兩個不同的內容映射相同的位置），而位圖又是一個不能解決哈希沖突的數據結構。于是布隆過濾器則是使用了多個哈希函數，將數據映射到多個位置上面，才能確保數據的準確性，減小誤判的概率

2、布隆過濾器的操作及實現

布隆的插入操作：

使用了多個哈希函數，將數據映射到多個位置上面，并將對應位置標記為1

示圖：

布隆過濾器的查找：

分別計算每個哈希值對應的比特位置存儲的是否為零，只要有一個為零，代表該元素一定不在哈希表中，否則可能在哈希表中

布隆過濾器如果說某個元素不存在時，該元素一定不存在，如果該元素存在時，該元素可能存在，因為有些哈希函數存在一定的誤判（哈希沖突）

布隆過濾器刪除：

布隆過濾器不能直接支持刪除工作，因為在刪除一個元素時，可能會影響其他元素（哈希沖突）

一種支持刪除的方法：

將布隆過濾器中的每個比特位擴展成一個小的計數器，插入元素時給k個計數器(k個哈希函數計算出的哈希地址)加一，刪除元素時，給k個計數器減一，通過多占用幾倍存儲空間的代價來增加刪除操作

缺陷：

無法確認元素是否真正在布隆過濾器中

存在計數回繞

如何選擇哈希函數個數和布隆過濾器長度：

如果一個數據要映射多個位置，如果布隆過濾器較小，則會導致數據馬上全部映射滿，此時無論進行什么操作，都會存在大量的誤報率。也就是說，布隆過濾器的長度與誤報率成反比，與空間利用率成反比

哈希函數的個數也值得思考，哈希函數越多，映射的位置也就越多，此時準確性也就越高，但隨之帶來的問題就是效率的降低。也就是說，哈希函數的個數與效率成反比，準確率成正比

示圖：

選擇公式：

注意：

k 為哈希函數個數，m 為布隆過濾器長度，n 為插入的元素個數，p 為誤報率

所以根據公式，我這里使用的哈希函數為3個，空間就應該開插入元素個數的五倍左右

實現代碼：

struct _BKDRHash { //BKDRHash size_t operator()(const std::string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { hash *= 131; hash += key[i]; } return hash; } }; struct _SDBMHash { //SDBMHash size_t operator()(const std::string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { hash *= 65599; hash += key[i]; } return hash; } }; struct _RSHash { //RSHash size_t operator()(const std::string& key) { size_t hash = 0; size_t magic = 63689; for (size_t i = 0; i < key.size(); i++) { hash *= magic; hash += key[i]; magic *= 378551; } return hash; } }; template class BloomFilter { public: bool Test(const K& key) { size_t index1 = Hash1()(key) % len; size_t index2 = Hash2()(key) % len; size_t index3 = Hash3()(key) % len; if (!_bs.test(index1) || !_bs.test(index2) || !_bs.test(index3)) return false; return true; } void Set(const K& key) { size_t index1 = Hash1()(key) % len; size_t index2 = Hash2()(key) % len; size_t index3 = Hash3()(key) % len; _bs.set(index1); _bs.set(index2); _bs.set(index3); } private: bitset<6*N> _bs; size_t len = 6 * N; }; }

3、布隆過濾器的分析

布隆過濾器優點：

增加和查詢元素的時間復雜度為:O(K), (K為哈希函數的個數，一般比較小)，與數據量大小無關

哈希函數相互之間沒有關系，方便硬件并行運算

布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴格的場合有很大優勢

在能夠承受一定的誤判時，布隆過濾器比其他數據結構有這很大的空間優勢

數據量很大時，布隆過濾器可以表示全集，其他數據結構不能

使用同一組散列函數的布隆過濾器可以進行交、并、差運算

布隆過濾器缺陷：

有誤判率，即存在假陽性(False Position)，即不能準確判斷元素是否在集合中(補救方法：再建立一個白名單，存儲可能會誤判的數據)

不能獲取元素本身

一般情況下不能從布隆過濾器中刪除元素

如果采用計數方式刪除，可能會存在計數回繞問題

三、海量數據處理

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中

這里的數據要求40億個不重復的無符號整數，使用位圖用一個位來表示一個整數，將所有的數據映射到位圖上，當進行查詢時，只要位圖的對應位置為1，則說明該數據在這40億個數據中

給定100億個整數，設計算法找到只出現一次的整數？

方法1：使用特定的位圖，每個映射的數有對應的兩個bit位進行表示映射的狀態

方法2：使用兩個位圖，同樣的兩個位圖對應的映射的數的位置共同表示映射狀態

注：沒有映射00，一次映射01，一次以上映射10

給兩個文件，分別有100億個整數，我們只有1G內存，如何找到兩個文件交集

方法1：將文件1的整數全部映射到位圖中，接著從文件2中讀取數據，并在位圖中查詢該數據，如果數據存在，則說明該數據是交集之一

方法2：使用兩個位圖，對兩個文件進行分別遍歷文件讀取數據映射到位圖上，然后對位圖進行遍歷求交集，同一個位置都為1，那么則為交集

1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數

方法1：使用特定的位圖，每個映射的數有對應的兩個bit位進行表示映射的狀態

方法2：使用兩個位圖，同樣的兩個位圖對應的映射的數的位置共同表示映射狀態

注：沒有映射00，一次映射01，兩次映射10，三次以上映射11

給兩個文件，分別有100億個query，我們只有1G內存，如何找到兩個文件交集？分別給出精確算法和近似算法

注：query一般為URL中的查詢字符串或者SQL中的查詢語句，假設每個query30個字節，那么100億個query也得300G的內存才能裝下

近似算法：使用布隆過濾器來進行處理，對一個文件將數據全部進行哈希映射，再對另一個文件中的數據進行查詢，但是可能存在哈希沖突，導致造成誤判，所以當一個數據不存在于布隆過濾器中，則它必定不存在，但是如果一個數據存在于布隆過濾器中，它也不一定存在

精確算法：如果要精確的進行查找，那就必須得將數據放入內存中，但是由于數據過大我們可以將數據存入到服務器中，先使用布隆過濾器進行處理，如果對應映射不存在，那么久一定不是交集，如果對應映射存在那么就到服務器中進行二次查詢

平均切割： 平均切割不是一個很好的方法，但是它確實是我們很容易就能思考到的方法，我們將兩個文件中的數據平均切分為M份(能放入內存)，分別存儲到一個set中，然后以此將數據進行比較，這種方法就需要以此對所有的數據進行比對，效率會比較低

哈希切割： 創建多個臨時文件，并進行標號，讀取文件數據使用字符串哈希算法進行哈希映射，映射到對應的文件并將數據存進去，對兩個文件的數據都采用這樣的做法進行切分，由于我們使用的是同一種字符串哈希算法，所以相同的字符串必定會被映射到同一個編號下的文件中，所以我們只需要依次對編號相同的Ai和Bi文件中使用set尋找交集即可（如果有些文件切分之后依然過大，可以繼續對其進行切分）

給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現次數最多的IP地址？ 與上題條件相同，如何找到top K的IP？如何直接用Linux系統命令實現？

使用哈希切割的方式來解決文件分片的問題，相同的IP地址必定會被映射到同一個文件中，所以我們依次讀取文件，使用Map進行次數統計即可之后再進行排序即可

Linux的命令：sort log_file | uniq -c | sort -nr | head -k

說明：首先使用sort log_file來將數據進行一個排序，使得相同的IP地址全部靠在一起。接著使用uniq - c進行去重，并將重復的次數顯示在每列的旁邊，通過這個次數來使用sort -nr進行降序排序，使得出現次數最的IP地址在前面，然后使用head -k 獲取前k個IP地址即可

100w個數中找出最大的100個數

由于100w個數據并不算多，可以存放進內存中，所以可以考慮以下解法

方法1：采用快排中的partition劃分思想，即單趟劃分后，樞軸s前面的數據都比他大，后面的數據都比他小，此時我們選取其中較大的那一部分，繼續劃分。當劃分后前端的數據剛好等于100后劃分結束，對前端數據進行排序即可得到結果。如果前端數據不足100，則從后端數據進行排序后取出不足的那部分補上，再進行排序即可。O(100w*100)

方法2：局部淘汰法，使用插入排序來完成，首先取出前100個數據進行排序，然后依次遍歷后面的數據，如果數據大于最小值，則將最小值刪除，然后按照插入排序的思路將數據插入進去O(100w*100)

方法3：局部淘汰法，使用一個大小為100的小堆來完成，維護一個小堆，當數據比堆頂也就是最小值大的時候，用新數據替換掉堆頂，然后調整堆的結構。遍歷完所有數據后就可以得到前100的數據。O(100w*lg100)

海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10

對于每一個電腦，都構建一個大小為10的堆(選大的構建小堆，選小的構建大堆)，選出當前電腦的TOP10，接著將所有電腦的數據匯總起來，共1000個數據，繼續用堆從其中選出TOP10

給上千個文件，每個文件大小為 1K—100M。給 n 個詞，設計算法對每個詞找到所有包含它的文件，你只有 100K 內存

使用倒排索引來解決，即建立起單詞——文件的映射，只需要遍歷所有文章，如果文章中出現過查詢詞，則將文件號追加在對應詞的倒排拉鏈中即可，如果100M的文件放不下內存中，就對數據進行切割后處理即可

C++ 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。