C++——哈希4|布隆过滤器

目录

布隆过滤器 

完整代码 

布隆过滤器应用 

布隆过滤器的查找

 布隆过滤器删除

 布隆过滤器优点

布隆过滤器缺陷

 布隆过滤器海量数据处理

---

 

布隆过滤器 

位图只能映射整形，而对于字符串却无能为力。

把字符串用哈希算法转成整形，映射一个位置进行标记

下面就是布隆过滤器设计思路

 位图是直接定址法，不存在冲突，而字符串可能转成整形后，会有重合的地方，发生下面这种冲突（误判）。

 布隆过滤器存在误判，如这里如果美团不存在，而B站存在，此时美团的位置被B站占据，有可能会误判为美团此时存在。

这种误判不可能完全去掉，但我们可以通过优化降低误判率。

优化方法：让每个值多映射几个位，如美团映射好几个位，就能减少上面误判的概率。理论而言，一个值映射的位越多，误判冲突的概率就越低，但如果映射过多，空间消耗就会增大。

 判断某邮箱是否在黑名单中，可用布隆过滤器进行简单的过滤

 

完整代码 

struct HashBKDR
{// BKDRsize_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}
};
struct HashAP
{// BKDRsize_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); i++){if ((i & 1) == 0){hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));}}return hash;}
};struct HashDJB
{// BKDRsize_t operator()(const string& key){size_t hash = 5381;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}
};//N表示准备要映射N个值
template<size_t N,class K=string,class Hash1=HashBKDR, class Hash2=HashAP, class Hash3=HashDJB>
class BloomFilter
{
public:void Set(const K& key)//一个值对应多个位置{size_t hash1 = Hash1()(key) % (_ratio * N);_bits.set(hash1);size_t hash2 = Hash2()(key) % (_ratio * N);_bits.set(hash2);size_t hash3 = Hash3()(key) % (_ratio * N);_bits.set(hash3);}bool Test(const K& key)//只要有一个位为0，就return false。{size_t hash1 = Hash1()(key) % (_ratio * N);if (!_bits.set(hash1))return false;size_t hash2 = Hash2()(key) % (_ratio * N);if (!_bits.set(hash2))return false;size_t hash3 = Hash3()(key) % (_ratio * N);if (!_bits.set(hash3))return false;return true;//返回真也可能存在误判}
private:const static size_t ratio = 5;//比例bitset<_ratio*N> _bits;
};

void TestBloomFilter1()
{BloomFilter<10> bf;string arr1[] = { "苹果", "西瓜", "阿里", "美团", "苹果", "字节", "西瓜", "苹果", "香蕉", "苹果", "腾讯" };for (auto& str : arr1){bf.Set(str);}for (auto& str : arr1){cout << bf.Test(str) << endl;}cout << endl << endl;string arr2[] = { "苹果111", "西瓜", "阿里2222", "美团", "苹果dadcaddxadx", "字节", "西瓜sSSSX", "苹果 ", "香蕉", "苹果$", "腾讯" };for (auto& str : arr2){cout << str << ":" << bf.Test(str) << endl;}
}

 上半部分是进行Set，下半部分是TestSet

测试用例2

void TestBloomFilter2()
{srand(time(0));const size_t N = 100000;BloomFilter<N> bf;cout << sizeof(bf) << endl;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(1234 + i));}for (auto& str : v1){bf.Set(str);}// 相似std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html";url += std::to_string(rand() + 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(rand()+i);v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.Test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

 

这里的比例越大，开的空间越多，误判率就会降低。 对于库中的布隆过滤器，若开的空间过大，会导致栈溢出，我们可以把空间转移到堆上去，以下是转移到堆上的代码

用我们上面自己写的代码就不会栈溢出，因为开的空间很小

template<size_t N, 
class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:void Set(const K& key){size_t hash1 = Hash1()(key) % (_ratio*N);//cout << hash1 << endl;_bits->set(hash1);size_t hash2 = Hash2()(key) % (_ratio*N);//cout << hash2 << endl;_bits->set(hash2);size_t hash3 = Hash3()(key) % (_ratio*N);//cout << hash3 << endl;_bits->set(hash3);}bool Test(const K& key){size_t hash1 = Hash1()(key) % (_ratio*N);//cout << hash1 << endl;if (!_bits->test(hash1))return false; // 准确的size_t hash2 = Hash2()(key) % (_ratio*N);//cout << hash2 << endl;if (!_bits->test(hash2))return false; // 准确的size_t hash3 = Hash3()(key) % (_ratio*N);//cout << hash3 << endl;if (!_bits->test(hash3))return false;  // 准确的return true; // 可能存在误判}// 能否支持删除->void Reset(const K& key);private:const static size_t _ratio = 5;std::bitset<_ratio*N>* _bits = new std::bitset<_ratio*N>;
};

布隆过滤器应用 

 

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特
位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为
零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可
能存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其
他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

 布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也
被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计
数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储
空间的代价来增加删除操作。
缺陷：
1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕

 布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

 布隆过滤器海量数据处理

1. 给两个文件，分别有100亿个query（字符串），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

精确算法：哈希切分

步骤：1.假设每个查询需要30byte空间，100亿个查询需要3000亿byte约等于300G

           2.假设俩个文件叫A和B，依次读取文件A中的query(查询)，然后转成整形并取模，这个query就进入编号为Ai的小文件

 之后开始找交集，对编号相同的找交集

 为什么要对应相同编号找交集？

相同的query，一定进入了相同编号的小文件，因为是同哈希函数转出来的然后对这个值取模，一系列操作都一样，只不过是放到了不同的文件中，虽然文件不同但编号相同。

近似算法：把一个文件放到布隆过滤器里面，再通过另一个文件来看数据在不在，在就是交集，不在则不是。
2. 如何扩展BloomFilter使得它支持删除元素的操作
 布隆过滤器一般不支持删除，如果有共同映射的地方，则会影响其它值。我们在这里可以使用引用计数，用多个位表示一个位置，做计数就可以支持删除，但是布隆为了支持删除，空间消耗更多，优势就削弱了

 

 删除百度

 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
与上题条件相同，如何找到top K的IP？