需要云服務(wù)器等云產(chǎn)品來學習Linux的同學可以移步/-->騰訊云<--/-->阿里云<--/-->華為云<--/官網(wǎng)，輕量型云服務(wù)器低至112元/年，新用戶首次下單享超低折扣。
?目錄
一、位圖
1、位圖的概念
2、大廠面試題
2.1位圖應(yīng)用（騰訊）
2.2位圖應(yīng)用
3、位圖的優(yōu)缺點
二、哈希切分
三、布隆過濾器
1、布隆過濾器的概念
2、布隆過濾器的應(yīng)用場景
3、布隆過濾器的刪除
4、布隆過濾器的優(yōu)缺點
5、布隆過濾器面試題
6、布隆過濾器的實現(xiàn)
一、位圖
1、位圖的概念
????????所謂位圖，就是用每一位來存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無重復的場景。通常是用來標記某個數(shù)據(jù)在或不在，它解決不了哪個數(shù)據(jù)出現(xiàn)次數(shù)最多的問題。
2、大廠面試題
2.1位圖應(yīng)用（騰訊）
給40億個不重復的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中？
????????開一個位圖，使用哈希的直接定址法，值是幾，就把位圖中的比特位標記成1，僅占用512M空間。
????????但我們不能按照比特位來開辟空間，所以使用char或int等內(nèi)置類型進行空間的開辟：
仿寫bitset：
#pragma once
#include <iostream>
#include <vector>
namespace jly
{
template <size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
}
public:
void set(size_t x)//將某個比特位標記為1
{
size_t i = x / 8;//算出x位于哪個字節(jié)
size_t j = x % 8;//算出x位于該字節(jié)的哪一位
_bits[i] |= (1 << j);
}
void reset(size_t x)//將某個比特位標記為0
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= (~(1 << j));
}
bool test(size_t x)//測試這個值在不在位圖中
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
std::vector<char> _bits;
};
void test_bitset()
{
bitset<-1> bs;
}
}????????這是一種又快又省空間的辦法，也是面試官最想聽到的回答。
????????但個人認為如果將題目要求的40億數(shù)字全部錄入位圖中，等于遍歷了一遍40億個數(shù)字，既然都遍歷一遍原數(shù)據(jù)了，那還不如在遍歷的時候直接比對呢，對吧，相比之下直接比對數(shù)據(jù)連512M的位圖都不用開。
2.2位圖應(yīng)用
1、給定100億個整數(shù)，設(shè)計算法找到只出現(xiàn)一次的整數(shù)？
????????可以認為這里的整數(shù)的最大值為unsigned int的最大值，一個整數(shù)共有三種狀態(tài)：00,01,02，分別代表不存在，出現(xiàn)一次，出現(xiàn)兩次及以上，代碼如下：
template <size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (_bs1.test(x))//01->10
{
_bs1.reset(x);
_bs2.set(x);
}
else if (_bs1.test(x)==false&&_bs2.test(x)==false)//00->01
{
_bs1.set(x);
}
}
void PrintOnce()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs1.test(i) && !_bs2.test(i))
{
std::cout << i << std::endl;
}
}
}
private:
std::bitset<N> _bs1;
std::bitset<N> _bs2;
};
void test()
{
twobitset<100> tbs;
int a[] = { 3,5,6,3,5,8,9,4,3,6,9,4 };
for (auto& e : a)
{
tbs.set(e);
}
tbs.PrintOnce();//打印8
}2、給兩個文件，分別有100億個整數(shù)，我們只有1G內(nèi)存，如何找到兩個文件交集？?
????????和第一問類似，開兩個位圖，分別將兩組數(shù)據(jù)映射進位圖，兩個位圖對應(yīng)的比特位均為1即為交集。
3、位圖應(yīng)用變形：1個文件有100億個int，1G內(nèi)存，設(shè)計算法找到出現(xiàn)次數(shù)不超過2次的所有整數(shù)
????????同第一問，開兩個位圖，00代表不存在，01代表出現(xiàn)一次，10代表出現(xiàn)兩次，11代表出現(xiàn)兩次以上。
3、位圖的優(yōu)缺點
????????優(yōu)點：節(jié)省空間，查找速度快
????????缺點：要求范圍相對集中，范圍特別分散的，空間消耗大；位圖只對整型使用，浮點數(shù)、string等其他類型無法使用。
????????如果要判斷其他類型，該類型如果可以使用哈希函數(shù)轉(zhuǎn)為整型的，可以考慮下布隆過濾器哈（見下文布隆過濾器的介紹）。
二、哈希切分
給一個超過100G大小的log fifile, log中存著IP地址, 設(shè)計算法找到出現(xiàn)次數(shù)最多的IP地址？
如果Ai沖突桶超過1G怎么辦？
1、這個桶沖突的IP很多，大多都是不重復的，map統(tǒng)計不下；
2、這個桶沖突的IP很多，大多都是重復的，map可以統(tǒng)計；
????????直接使用map中的insert將每一個沖突桶的元素插入到map中。情況一：如果insert插入失敗，說明空間不足，new節(jié)點失敗，拋出異常。解決方法是換個哈希函數(shù)，遞歸再次對這個沖突桶進行切分。情況二：map可以正常統(tǒng)計。
三、布隆過濾器
1、布隆過濾器的概念
????????布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點是高效地插入和查詢。它是用多個哈希函數(shù)，將一個數(shù)據(jù)映射到位圖結(jié)構(gòu)中，可以用來告訴你 “某樣東西一定不存在或者可能存在”。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內(nèi)存空間。
????????既然這種方法能判斷某個元素一定不存在，那么如何降低“誤判”（映射為1的概率）的概率，提升準確判定（映射為0的概率）的概率呢？
????????解決方法就是對同一個元素使用多組哈希函數(shù)進行映射，它能降低誤判率，但是增加了空間消耗。使用時需要把控好布隆過濾器的哈希函數(shù)的個數(shù)和布隆過濾器的長度。公式為【k:哈希函數(shù)的個數(shù)；m:布隆過濾器的長度；n:插入元素的個數(shù)】(選型可參照本文)
2、布隆過濾器的應(yīng)用場景
1、不需要一定準確的場景，例如個人網(wǎng)站注冊時候的昵稱判重，使用布隆過濾器可以判斷某個昵稱一定沒有被使用過，但會誤判某些造成沖突但沒有被使用的昵稱。
2、提高效率。例如客戶端查找信息時，先用布隆過濾器篩一下，如果不在，則直接將未查到的信息反饋給客戶端；如果布隆過濾器發(fā)現(xiàn)查找信息與位圖匹配，則將需要查找的信息推送給服務(wù)器中的數(shù)據(jù)庫進行精確查找。
3、布隆過濾器的刪除
????????單純的布隆過濾器是不支持刪除的，因為一個比特位可能被多個元素所映射。如果非要在布隆過濾器中實現(xiàn)reset，那就只能將位圖結(jié)構(gòu)修改為計數(shù)器結(jié)構(gòu)。數(shù)據(jù)set時，每被映射一次，計數(shù)器加1，reset時，該位計數(shù)器-1，直到該位計數(shù)器為0。毫無疑問，這種操作所需的空間消耗急劇增加。
4、布隆過濾器的優(yōu)缺點
優(yōu)點：
- 增加和查詢元素的時間復雜度為:O(K), (K為哈希函數(shù)的個數(shù)，一般比較小)，與數(shù)據(jù)量大小無關(guān)
- 哈希函數(shù)相互之間沒有關(guān)系，方便硬件并行運算
- 布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴格的場合有很大優(yōu)勢
- 在能夠承受一定的誤判時，布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢
- 數(shù)據(jù)量很大時，布隆過濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能
- 使用同一組散列函數(shù)的布隆過濾器可以進行交、并、差運算
缺點：
- 有誤判率，即存在假陽性(False Position)，即不能準確判斷元素是否在集合中(補救方法：再建立一個白名單，存儲可能會誤判的數(shù)據(jù))
- 不能獲取元素本身
- 一般情況下不能從布隆過濾器中刪除元素
- 如果采用計數(shù)方式刪除，可能會存在計數(shù)回繞問題
5、布隆過濾器面試題
給兩個文件，分別有100億個query，我們只有1G內(nèi)存，如何找到兩個文件交集？分別給出精確算法和近似算法
????????近似算法：使用布隆過濾器，先將其中一個文件set進布隆過濾器中，再將另一個文件的數(shù)據(jù)進行比對，可以淘汰一定不是交集的那部分，不過余下的那部分數(shù)據(jù)中，仍會有非交集的存在。文章來源：http://www.zghlxwxcb.cn/news/detail-406610.html
????????精確算法：使用哈希切分，將兩個大文件分別切成一個個小文件A0-A99，B0-B99（單個小文件超過1G參照上文哈希切分對于此問題的解決方法）；因為使用的是相同的哈希函數(shù)，所以交集必定存在于A0和B0，A1和B1這種相同下標的小文件中?？梢韵葘0存放至哈希表中，B0去重后與哈希表比對，就能夠精確得到交集。文章來源地址http://www.zghlxwxcb.cn/news/detail-406610.html
6、布隆過濾器的實現(xiàn)
#pragma once
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
struct BKDRHash
{
size_t operator()(const std::string& key)
{
size_t hash = 0;
for (auto& ch : key)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
struct APHash
{
size_t operator()(const std::string& key)
{
unsigned int hash = 0;
int i = 0;
for (auto ch : key)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
}
++i;
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const std::string& key)
{
unsigned int hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
struct JSHash
{
size_t operator()(const std::string& s)
{
size_t hash = 1315423911;
for (auto ch : s)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
};
//N為最大存儲的個數(shù),X為存一個值，需要開辟的比特位
template <size_t N,size_t X=5,class K=std::string,
class HashFunc1= BKDRHash,
class HashFunc2= APHash,
class HashFunc3= DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t hash1 = HashFunc1()(key) % (X * N);
size_t hash2 = HashFunc2()(key) % (X * N);
size_t hash3 = HashFunc3()(key) % (X * N);
_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
}
bool test(const K& key)
{
size_t hash1 = HashFunc1()(key) % (X * N);
size_t hash2 = HashFunc2()(key) % (X * N);
size_t hash3 = HashFunc3()(key) % (X * N);
return _bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3);
}
private:
std::bitset<X*N> _bs;
};
void test_bloomfilter1()
{
// 10:46繼續(xù)
string str[] = { "a", "s", "d", "w", "a1","1a","白1a","c11a","1a1" };
BloomFilter<10> bf;
for (auto& str : str)
{
bf.set(str);
}
for (auto& s : str)
{
cout << bf.test(s) << endl;
}
cout << endl;
srand((unsigned int)time(0));
for (const auto& s : str)
{
cout << bf.test(s + to_string(rand())) << endl;
}
}
void test_bloomfilter2()
{
srand((unsigned int)time(0));
const size_t N = 100000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
// v2跟v1是相似字符串集，但是不一樣
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
url += std::to_string(999999 + i);
v2.push_back(url);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str))
{
++n2;
}
}
cout << "相似字符串誤判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string url = "zhihu.com";
url += std::to_string(i + rand());
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串誤判率:" << (double)n3 / (double)N << endl;
}到了這里，關(guān)于【C++】哈希的應(yīng)用:位圖、哈希切分與布隆過濾器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++]哈希應(yīng)用之位圖&布隆過濾器](https://imgs.yssmx.com/Uploads/2024/04/852662-1.gif)
