位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用 来判断某个数据存不存在的。

位图的应用

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

位图的实现

#pragma once
#include
#includeusing namespace std;namespace szg
{templateclass bitset{public:bitset(){int n = N / 8 + 1;_bitmap.resize(n);}void set(size_t x){int n = x / 8;int m = x % 8;_bitmap[n] |= 1 << m;}void reset(size_t x){int n = x / 8;int m = x % 8;_bitmap[n] &= ~(1 << m);}bool test(size_t x){int n = x / 8;int m = x % 8;return _bitmap[n] & (1 << m);}private:vector _bitmap;};void test_bitset(){//bitset<100> bs1;//bitset<-1> bs2;bitset<0xffffffff> bs2;bs2.set(10);bs2.set(10000);bs2.set(8888);cout << bs2.test(10) << endl;cout << bs2.test(10000) << endl;cout << bs2.test(8888) << endl;cout << bs2.test(8887) << endl;cout << bs2.test(9999) << endl << endl;bs2.reset(8888);bs2.set(8887);cout << bs2.test(10) << endl;cout << bs2.test(10000) << endl;cout << bs2.test(8888) << endl;cout << bs2.test(8887) << endl;cout << bs2.test(9999) << endl;}}

注意：位图的缺点时只能针对整型，且范围要集中。

布隆过滤器

讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 位图吧，确实可以将值映射到 位图的 Key，然后可以在 O(1) 的时间复杂度内返回结果，，效率奇高。但是 位图 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 位图占据的内存大小就变得很可观了。

并且以string类型经过哈希转换后映射到位图上会出现误判，会出现多个元素映射到同一个位置的情况。

为了解决位图的缺点，我们引入了布隆过滤器。（布隆过滤器只能降低误判率，不能完全消除误判）

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概 率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存 在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也 可以节省大量的内存空间。

 从图中可以看出，布隆过滤器一个元素映射多个位置（使用多个哈希函数），判断结果不在是准确的，判断结果存在时是不准确的。

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数

 布隆过滤器实现

#pragma once
#include
#include
#include
#includeusing namespace std;namespace szg
{struct BKDRHash{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}};struct APHash{size_t operator()(const 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 string& key){unsigned int hash = 5381;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}};struct JSHash{size_t operator()(const string& s){size_t hash = 1315423911;for (auto ch : s){hash ^= ((hash << 5) + ch + (hash >> 2));}return hash;}};templateclass BloomFilter{public://插入数据（设置映射）void set(const K& k){size_t hashi1 = hash1()(k) % (N * x);size_t hashi2 = hash2()(k) % (N * x);size_t hashi3 = hash3()(k) % (N * x);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);}bool test(const K& k){size_t hashi1 = hash1()(k) % (N * x);size_t hashi2 = hash2()(k) % (N * x);size_t hashi3 = hash3()(k) % (N * x);if (_bs.test(hashi1) && _bs.test(hashi2) && _bs.test(hashi3))//可能存在{return true;}else//一定不存在{return false;}}private:bitset _bs;};void test_bloomfilter1(){string str[] = { "猪八戒", "孙悟空", "沙悟净", "唐三藏", "白龙马1","1白龙马","白1龙马","白11龙马","1白龙马1" };BloomFilter<10> bf;for (auto& str : str){bf.set(str);}for (auto& s : str){cout << bf.test(s) << endl;}cout << endl;srand(time(0));for (const auto& s : str){cout << bf.test(s + to_string(rand())) << endl;}}void test_bloomfilter2(){srand(time(0));const size_t N = 100000;BloomFilter bf;std::vector 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 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 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;}}

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无 关

2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

参考

详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)