溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“C++位圖,哈希切分與布隆過濾器怎么應用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C++位圖,哈希切分與布隆過濾器怎么應用”吧!
所謂位圖，就是用每一位來存放某種狀態，適用于海量數據，數據無重復的場景。通常是用來標記某個數據在或不在，它解決不了哪個數據出現次數最多的問題。
2.1位圖應用
給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中？
開一個位圖，使用哈希的直接定址法，值是幾，就把位圖中的比特位標記成1，僅占用512M空間。
但我們不能按照比特位來開辟空間，所以使用char或int等內置類型進行空間的開辟：
仿寫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位于哪個字節
size_t j = x % 8;//算出x位于該字節的哪一位
_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億數字全部錄入位圖中，等于遍歷了一遍40億個數字，既然都遍歷一遍原數據了，那還不如在遍歷的時候直接比對呢，對吧，相比之下直接比對數據連512M的位圖都不用開。
2.2位圖應用
1、給定100億個整數，設計算法找到只出現一次的整數？
可以認為這里的整數的最大值為unsigned int的最大值，一個整數共有三種狀態：00,01,02，分別代表不存在，出現一次，出現兩次及以上，代碼如下：
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億個整數，我們只有1G內存，如何找到兩個文件交集？
和第一問類似，開兩個位圖，分別將兩組數據映射進位圖，兩個位圖對應的比特位均為1即為交集。
3、位圖應用變形：1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數
同第一問，開兩個位圖，00代表不存在，01代表出現一次，10代表出現兩次，11代表出現兩次以上。
優點：節省空間，查找速度快
缺點：要求范圍相對集中，范圍特別分散的，空間消耗大；位圖只對整型使用，浮點數、string等其他類型無法使用。
如果要判斷其他類型，該類型如果可以使用哈希函數轉為整型的，可以考慮下布隆過濾器哈（見下文布隆過濾器的介紹）。
給一個超過100G大小的log fifile, log中存著IP地址, 設計算法找到出現次數最多的IP地址？
如果Ai沖突桶超過1G怎么辦？
1、這個桶沖突的IP很多，大多都是不重復的，map統計不下；
2、這個桶沖突的IP很多，大多都是重復的，map可以統計；
直接使用map中的insert將每一個沖突桶的元素插入到map中。情況一：如果insert插入失敗，說明空間不足，new節點失敗，拋出異常。解決方法是換個哈希函數，遞歸再次對這個沖突桶進行切分。情況二：map可以正常統計。
布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數據結構，特點是高效地插入和查詢。它是用多個哈希函數，將一個數據映射到位圖結構中，可以用來告訴你 “某樣東西一定不存在或者可能存在”。此種方式不僅可以提升查詢效率，也可以節省大量的內存空間。
既然這種方法能判斷某個元素一定不存在，那么如何降低“誤判”（映射為1的概率）的概率，提升準確判定（映射為0的概率）的概率呢？
解決方法就是對同一個元素使用多組哈希函數進行映射，它能降低誤判率，但是增加了空間消耗。使用時需要把控好布隆過濾器的哈希函數的個數和布隆過濾器的長度。公式為k=(m/n)*lg2
【k:哈希函數的個數；m:布隆過濾器的長度；n:插入元素的個數】(選型可參照本文)
1、不需要一定準確的場景，例如個人網站注冊時候的昵稱判重，使用布隆過濾器可以判斷某個昵稱一定沒有被使用過，但會誤判某些造成沖突但沒有被使用的昵稱。
2、提高效率。例如客戶端查找信息時，先用布隆過濾器篩一下，如果不在，則直接將未查到的信息反饋給客戶端；如果布隆過濾器發現查找信息與位圖匹配，則將需要查找的信息推送給服務器中的數據庫進行精確查找。
單純的布隆過濾器是不支持刪除的，因為一個比特位可能被多個元素所映射。如果非要在布隆過濾器中實現reset，那就只能將位圖結構修改為計數器結構。數據set時，每被映射一次，計數器加1，reset時，該位計數器-1，直到該位計數器為0。毫無疑問，這種操作所需的空間消耗急劇增加。
優點：
增加和查詢元素的時間復雜度為:O(K), (K為哈希函數的個數，一般比較小)，與數據量大小無關哈希函數相互之間沒有關系，方便硬件并行運算布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴格的場合有很大優勢在能夠承受一定的誤判時，布隆過濾器比其他數據結構有這很大的空間優勢數據量很大時，布隆過濾器可以表示全集，其他數據結構不能使用同一組散列函數的布隆過濾器可以進行交、并、差運算
缺點：
有誤判率，即存在假陽性(False Position)，即不能準確判斷元素是否在集合中(補救方法：再建立一個白名單，存儲可能會誤判的數據)不能獲取元素本身一般情況下不能從布隆過濾器中刪除元素如果采用計數方式刪除，可能會存在計數回繞問題
給兩個文件，分別有100億個query，我們只有1G內存，如何找到兩個文件交集？分別給出精確算法和近似算法
近似算法：使用布隆過濾器，先將其中一個文件set進布隆過濾器中，再將另一個文件的數據進行比對，可以淘汰一定不是交集的那部分，不過余下的那部分數據中，仍會有非交集的存在。
精確算法：使用哈希切分，將兩個大文件分別切成一個個小文件A0-A99，B0-B99（單個小文件超過1G參照上文哈希切分對于此問題的解決方法）；因為使用的是相同的哈希函數，所以交集必定存在于A0和B0，A1和B1這種相同下標的小文件中。可以先將A0存放至哈希表中，B0去重后與哈希表比對，就能夠精確得到交集。
#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為最大存儲的個數,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 hash2 = HashFunc1()(key) % (X * N);
size_t hash3 = HashFunc2()(key) % (X * N);
size_t hash4 = HashFunc3()(key) % (X * N);
_bs.set(hash2);
_bs.set(hash3);
_bs.set(hash4);
}
bool test(const K& key)
{
size_t hash2 = HashFunc1()(key) % (X * N);
size_t hash3 = HashFunc2()(key) % (X * N);
size_t hash4 = HashFunc3()(key) % (X * N);
return _bs.test(hash2) && _bs.test(hash3) && _bs.test(hash4);
}
private:
std::bitset<X*N> _bs;
};
void test_bloomfilter1()
{
// 10:46繼續
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;
}到此，相信大家對“C++位圖,哈希切分與布隆過濾器怎么應用”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
