哈希切割

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

解決思路

找到出現(xiàn)次數(shù)最多的IP地址

要找到前TopK的IP地址，就是要統(tǒng)計每個IP地址出現(xiàn)多少次
分割大文件:如果能將相同IP地址放到同一個文件中
哈希分割: 從源文件中獲取一個IP地址---->IP%文件份數(shù)

每拿到一個IP地址后，用函數(shù)把IP地址轉(zhuǎn)化為整型數(shù)據(jù)，再%上文件分?jǐn)?shù)，就知道把IP地址放到哪個文件中去

這樣，就可以統(tǒng)計每個IP地址出現(xiàn)多少次

//構(gòu)建鍵值對 <IP地址的整型數(shù)據(jù)，次數(shù)>

統(tǒng)計哪個IP地址出現(xiàn)的次數(shù)比較多，用unordered_map,m[ip]++;每拿到一個IP地址的++。每個IP地址出現(xiàn)的次數(shù)，已經(jīng)在unordered_map中保存起來

按類似的方法，統(tǒng)計每個文件中的IP地址的次數(shù)，最后用一個for()---->找出出現(xiàn)最多的IP地址

top K的IP

堆---->最多前K個IP地址—><次數(shù)，IP地址>

位圖

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

遍歷，時間復(fù)雜度O(N)

排序(O(NlogN))，利用二分查找: logN

位圖解決

數(shù)據(jù)是否在給定的整形數(shù)據(jù)中，結(jié)果是在或者不在，剛好是兩種狀態(tài)，那么可以使用一個二進(jìn)制比
特位來代表數(shù)據(jù)是否存在的信息，如果二進(jìn)制比特位為1，代表存在，為0代表不存在。比如：
40億的整型數(shù)據(jù)大概是16G的數(shù)據(jù)
用位圖來映射的話 大概就是2³²-2³=512M

解決

C++中提供了位圖的類，bitset

位圖的實現(xiàn)

#pragma once #include<vector> #include<iostream> using namespace std; namespace LXY {class bitset{public:bitset(size_t bitCount):_set(bitCount/8 + 1), _bitCount(bitCount){}//置1操作void set(size_t which){//如果位集合給出100個比特位，那么你給100，就表示不了，范圍為0~99if(which >= _bitCount)return;//計算對應(yīng)的字節(jié)size_t index = (which >> 3);//除以8size_t pos = which % 8;//先將1移到對應(yīng)的比特位上，再或上對應(yīng)位上的數(shù)字_set[index] |= (1 << pos);}//置0操作void reset(size_t which){if (which >= _bitCount)return;//計算對應(yīng)的字節(jié)size_t index = (which >> 3);//除以8size_t pos = which % 8;//先將1的取反0移到對應(yīng)的比特位上，再與上對應(yīng)位上的數(shù)字_set[index] &= ~(1 << pos);}//檢測which比特位是否為1bool test(size_t which){if (which >= _bitCount)return false;//計算對應(yīng)的字節(jié)size_t index = (which >> 3);//除以8size_t pos = which % 8;//與上1不等于0就代表存在return 0 != (_set[index] & (1 << pos));}//返回比特位總的個數(shù)size_t size(){return _bitCount;}//返回為1的比特位的總數(shù)size_t count(){//查表int bitCnttable[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,6, 7, 6, 7, 7, 8 };size_t szcount = 0;for (size_t i = 0; i < _set.size(); ++i)szcount += bitCnttable[_set[i]];return szcount;}public:std::vector<unsigned char> _set;size_t _bitCount;}; }void TestBitSet() {LXY::bitset bt(100);bt.set(10);bt.set(20);bt.set(30);bt.set(40);bt.set(41);cout << bt.size() << endl;cout << bt.count() << endl;if (bt.test(40))cout << "40bite is 1" << endl;elsecout << "40bite is not 1" << endl;bt.reset(40);cout << bt.count() << endl;if (bt.test(40))cout << "40bite is 1" << endl;elsecout << "40bite is not 1" << endl; }int main() {TestBitSet();system("pause");return 0; }

位圖的應(yīng)用

快速查找某個數(shù)據(jù)是否在一個集合中

排序 (數(shù)據(jù)不能有重復(fù))

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

操作系統(tǒng)中磁盤塊標(biāo)記

位圖的題

給定100億個整數(shù)，設(shè)計算法找到只出現(xiàn)一次的整數(shù)？
用兩個比特位表示一個數(shù)據(jù)，8/2=4；那么位圖中一個字節(jié)只能表示4個數(shù)據(jù)，2³²/2²=1G。
取一個數(shù)據(jù):哪個字節(jié) 哪兩個比特位

if(00) //出現(xiàn)過0次01else if(01) //出現(xiàn)過多次10

位圖應(yīng)用變形：1個文件有100億個int，1G內(nèi)存，設(shè)計算法找到出現(xiàn)次數(shù)不超過2次的所有整數(shù)

布隆過濾器

位圖+哈希函數(shù)
特點是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”，它是用多個哈希函數(shù)，將一個數(shù)據(jù)映射到位圖結(jié)構(gòu)中。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內(nèi)存空間。多個比特位代表數(shù)據(jù)的狀態(tài)信息

布隆過濾器插入

如果向布隆過濾器中插入baidu，我們用三個哈希函數(shù)將三個位置置為1


“baidu”---->1 4 7
“tecent”---->3 4 8
hash1,hash2,hash3----->三個位置
檢測三個位置的狀態(tài)
如果三個位置只要有一個為0，說明數(shù)據(jù)一定不存在

布隆過濾器的查找

布隆過濾器的思想是將一個元素用多個哈希函數(shù)映射到一個位圖中，因此被映射到的位置的比特位一定為1。所以可以按照以下方式進(jìn)行查找：分別計算每個哈希值對應(yīng)的比特位置存儲的是否為零，只要有一個為零，代表該元素一定不在哈希表中，否則可能在哈希表中
布隆過濾器如果告訴你數(shù)據(jù)不存在，那么一定不存在，如果告訴你存在，則有可能存在。

布隆過濾器的插入和查找的實現(xiàn)

#pragma once #include"biteset.hpp" #include<iostream> #include"Common.hpp" using namespace std;//BloomFilter:位圖+多個哈希 template<class T,class HF1 = Str2INT ,class HF2 = Str2INT2,class HF3 = Str2INT3,class HF4 =Str2INT4,class HF5 = Str2INT5> //哈希函數(shù)給的越多，將來產(chǎn)生誤報的概率就也就越小 class BloomFilter { public:BloomFilter(size_t size = 10):_bt(10 * size), _size(0){}bool Insert(const T& data){//HF1()(data)可能回越界，要%上位圖的比特位數(shù)size_t index1 = HF1()(data) % _bt.size();size_t index2 = HF2()(data) % _bt.size();size_t index3 = HF3()(data) % _bt.size();size_t index4 = HF4()(data) % _bt.size();size_t index5 = HF5()(data) % _bt.size();_bt.set(index1);_bt.set(index2);_bt.set(index3);_bt.set(index4);_bt.set(index5);_size++;return true;}//檢測是否存在，每個哈希函數(shù)都得檢測bool IsIn(const T&data){size_t index = HF1()(data) % _bt.size();if (!_bt.test(index))return false;index = HF2()(data) % _bt.size();if (!_bt.test(index))return false;index = HF3()(data) % _bt.size();if (!_bt.test(index))return false;index = HF4()(data) % _bt.size();if (!_bt.test(index))return false;index = HF5()(data) % _bt.size();if (!_bt.test(index))return false;//元素可能存在return true;}//存儲多少個元素size_t count()const{return _size;} private:LXY::bitset _bt;size_t _size; };

布隆過濾器的刪除

布隆過濾器不能直接支持刪除工作，因為在刪除一個元素時，可能會影響其他元素
一種支持刪除的方法：將布隆過濾器中的每個比特位擴(kuò)展成一個小的計數(shù)器（整型數(shù)組），插入元素時給k個計數(shù)器(k個哈希函數(shù)計算出的哈希地址)加一，刪除元素時，給k個計數(shù)器減一，通過多占用幾倍存儲空間的代價來增加刪除操作。

缺陷：

無法確認(rèn)元素是否真正在布隆過濾器中

存在計數(shù)回繞

布隆過濾器優(yōu)點

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

哈希函數(shù)相互之間沒有關(guān)系，方便硬件并行運算

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

在能夠承受一定的誤判時，布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢

數(shù)據(jù)量很大時，布隆過濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能

使用同一組散列函數(shù)的布隆過濾器可以進(jìn)行交、并、差運算

布隆過濾器缺陷

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

不能獲取元素本身

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

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

布隆過濾器

給兩個文件，分別有100億個query，我們只有1G內(nèi)存，如何找到兩個文件交集？分別給出精確算法和近似算法
答：給一個布隆過濾器，將一個文件的數(shù)據(jù)映射里面去。如果整體映射不完，先映射一部分。從另外一個文件拿一個數(shù)據(jù)在布隆過濾器里面找，如果有，數(shù)據(jù)存在就算是兩個文件的交集。

倒排索引

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

哈希加密

總結(jié)

以上是生活随笔為你收集整理的海量数据处理(位图和布隆过滤器)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。