文章目录
C++位图和布隆过滤器（含哈希切割）1、位图（Bitmap）1.1、位图的概念1.2、位图的使用1.3、位图的模拟实现1.4、位图相关面试题 2、布隆过滤器（Bloom Filter）2.1、布隆过滤器的概念2.2、布隆过滤器的插入2.3、布隆过滤器的模拟实现2.4、布隆过滤器相关面试题 3、哈希切分（哈希切割）4、海量数据处理
C++位图和布隆过滤器（含哈希切割）
位图和布隆过滤器都是哈希思想的应用
1、位图（Bitmap）
1.1、位图的概念
位图是一种用于表示集合的数据结构，它通常用一个比特位序列来表示一组元素的存在与否。在 C++ 中，位图通常使用一个二进制数组来实现。每个元素对应位图中的一个比特位，如果该元素存在于集合中，则对应的比特位被设置为1，否则为0。
应用场景：存储大量的布尔值信息，节省内存空间。还可以快速判断一个元素是否存在于集合中，时间复杂度为 O(1)。
优点：空间效率高，占用内存少。查询效率高，时间复杂度低。
缺点：不能存储重复元素（使用两个及以上的位图可以解决）。对于范围较大的数据，可能会占用较多的内存空间。
1.2、位图的使用
void test_bs1() { bitset<1000> bs; int a[] = {1, 5, 7, 8, 999, 44, 22, 44, 0, 3, 5, 65, 78, 95}; for (auto e: a) { bs.set(e); } for (auto e: a) { cout << e << "->" << bs.test(e) << endl; } cout << "==================" << endl; bs.reset(1); bs.reset(5); for (auto e: a) { cout << e << "->" << bs.test(e) << endl; } // a中没有的值 cout << "a中没有的值:" << 10 << "->" << bs.test(10) << endl;}
1.3、位图的模拟实现
这里我们用的int作为一个区间大小（32），所以是mod 32。如果是char就mod 8。
#include <vector>// 位图// 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】namespace xp { template<size_t N> class bitset { public: bitset() { _bs.resize(N / 32 + 1, 0); // 当N很大时，位图的长度范围是1～2^32 } void set(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; _bs[i] |= (1 << j);// 将该位置置1 } void reset(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; _bs[i] &= ~(1 << j);// 将该位置置0 } bool test(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; if (_bs[i] & (1 << j)) return true;// 这个值存在 else return false;// 这个值不存在 } private: vector<int> _bs; };
1.4、位图相关面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
答：使用位图，位图的大小取决于无符号整数的区间，无符号整数的范围是0～2^32-1即0～4294967295（大约43亿）。在32位平台下就可以将这40亿个整数映射到位图中。映射完后，判断一个数是否在这40亿个数中只需要调用test函数判断该数映射的bit位是否为1，为1就在，为0就不在。
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集。
答：使用两个位图，位图1存其中的100亿整数，位图2存其中的另100亿整数，其中位图占用的内存大小 = 2^32bit = 512MB，两个位图就是1GB。之后再一一对比两个位图中相同位置的bit位上都为1的整数就是交集。
位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
答：有两个方案：
方案一：使用一个位图，让每两个比特位映射一个整数，这样就需要2^33个比特位（必须在64位平台下），也就是1GB的内存。两个比特位表示为：00，01，10，11。当一个整数第一次映射的时候，位图的映射位置的这两个比特位中第二个比特位设置为1，第二次映射的时候，位图的映射位置的这两个比特位中第一个比特位设置为1，第二个比特位设置为0。以此类推。其中不超过两次的整数就是映射后比特位为00和01的。
方案二：使用两个位图，一个整数映射到两个位图的同一个位置，一个位图的这个位置的比特位作为第一个比特位，一个位图的这个位置的比特位作为第二个比特位，其实和方案一差不多，就是两个比特位记录出现的次数。这里两个位图占用的内存大小就是2*512MB=1GB。当一个整数第一次映射的时候，第二个位图的映射位置的比特位设置为1，第二次映射的时候，第一个位图的映射位置的比特位设置为1，第二个位图的映射位置的比特位设置为0。以此类推。其中不超过两次的整数就是映射后比特位为00和01的。
这里仅贴使用两个位图的代码：
template<size_t N> class two_bitset { public: void set(size_t x) { if (_bs1.test(x) == false && _bs2.test(x) == false) { // 00 -> 01 _bs2.set(x); } else if (_bs1.test(x) == false && _bs2.test(x) == true) { // 01 -> 10 _bs1.set(x); _bs2.reset(x); } else { _bs1.set(x); _bs2.set(x); } } size_t test(size_t x) { if (_bs1.test(x) == false && _bs2.test(x) == false) { return 0; } else if (_bs1.test(x) == false && _bs2.test(x) == true) { // 01 -> 10 return 1; } else { return 2;// 大于等于2次 } } private: bitset<N> _bs1; bitset<N> _bs2; };
2、布隆过滤器（Bloom Filter）
2.1、布隆过滤器的概念
布隆过滤器是一种空间效率很高的概率型数据结构，用于判断一个元素是否属于一个集合。它通过一系列哈希函数将元素映射到一个位数组中（即将一个元素映射到多个位置），并根据位数组中的值来判断元素是否存在。
特点：布隆过滤器可以用来快速判断一个元素不在集合中，但是无法确定一个元素是否一定在集合中。它的查询操作是常数时间复杂度，但存在一定的误判率。
应用场景：
在缓存系统中判断一个数据是否存在于缓存中，从而减少缓存不命中率。在网络爬虫中过滤已经访问过的 URL，避免重复访问。在分布式系统中进行快速的数据定位。优点：空间效率高，比哈希表占用更少的内存。查询效率高，时间复杂度低。
缺点：存在一定的误判率，即可能将不在集合中的元素误认为在集合中。不能删除元素，除非重新构建布隆过滤器。
2.2、布隆过滤器的插入
布隆过滤器的的映射规则：将一个元素映射到多个位置。下面我们模拟实现的时候，使用三个哈希函数来映射三个位置。
布隆过滤器也是使用位图来实现的，只不过它的位图的长度要更长，以防止映射位置太少而导致误判率太高。
而哈希函数个数和布隆过滤器长度的选择是有个最佳比例的（有大佬证明了）布隆过滤器
这个比例就是
其中
我们假设k为3，m/n就约等于4.34。
哈希函数：这里默认的插入对象是string，如果插入的数据是自定义类型，可以自己写仿函数传入。
struct HashFuncBKDR { size_t operator()(const string &str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; for (auto &e: str) { hash = hash * seed + e; } return hash; }};struct HashFuncAP { size_t operator()(const string &str) { unsigned int hash = 0; int i; for (i = 0; i < str.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5))); } } return hash; }};struct HashFuncDJB { size_t operator()(const string &str) { unsigned int hash = 5381; for (auto &e: str) { hash += (hash << 5) + e; } return hash; }};插入代码：
namespace xp { template<size_t N> class bitset { public: bitset() { _bs.resize(N / 32 + 1, 0); // 当N很大时，位图的长度范围是1～2^32 } void set(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; _bs[i] |= (1 << j);// 将该位置置1 } void reset(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; _bs[i] &= ~(1 << j);// 将该位置置0 } bool test(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; if (_bs[i] & (1 << j)) return true;// 这个值存在 else return false;// 这个值不存在 } private: vector<int> _bs; };}struct HashFuncBKDR { size_t operator()(const string &str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; for (auto &e: str) { hash = hash * seed + e; } return hash; }};struct HashFuncAP { size_t operator()(const string &str) { unsigned int hash = 0; int i; for (i = 0; i < str.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5))); } } return hash; }};struct HashFuncDJB { size_t operator()(const string &str) { unsigned int hash = 5381; for (auto &e: str) { hash += (hash << 5) + e; } return hash; }};template<size_t N, class K=string, class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB>class BloomFilter {public: void set(const K &s) { int hash1 = Hash1()(s) % M; int hash2 = Hash2()(s) % M; int hash3 = Hash3()(s) % M; // 映射三个位置 _bs.set(hash1); _bs.set(hash2); _bs.set(hash3); }private: static const size_t M = 8*N; xp::bitset<M> _bs;};
2.3、布隆过滤器的模拟实现
判断一个元素在不在这个位图中，可以看其映射的位置是否存在比特位为0的，为0一定不存在。其中一个位为1不一定存在，全部位（这里是3个位）位1才存在（也可能误判）。
因此整体代码为:
namespace xp { template<size_t N> class bitset { public: bitset() { _bs.resize(N / 32 + 1, 0); // 当N很大时，位图的长度范围是1～2^32 } void set(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; _bs[i] |= (1 << j);// 将该位置置1 } void reset(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; _bs[i] &= ~(1 << j);// 将该位置置0 } bool test(size_t x) { assert(x <= N); size_t i = x / 32; // 找到第几个int（32位） size_t j = x % 32; if (_bs[i] & (1 << j)) return true;// 这个值存在 else return false;// 这个值不存在 } private: vector<int> _bs; };}struct HashFuncBKDR { size_t operator()(const string &str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; for (auto &e: str) { hash = hash * seed + e; } return hash; }};struct HashFuncAP { size_t operator()(const string &str) { unsigned int hash = 0; int i; for (i = 0; i < str.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5))); } } return hash; }};struct HashFuncDJB { size_t operator()(const string &str) { unsigned int hash = 5381; for (auto &e: str) { hash += (hash << 5) + e; } return hash; }};template<size_t N, class K=string, class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB>class BloomFilter {public: void set(const K &s) { int hash1 = Hash1()(s) % M; int hash2 = Hash2()(s) % M; int hash3 = Hash3()(s) % M; // 映射三个位置 _bs.set(hash1); _bs.set(hash2); _bs.set(hash3); } bool test(const K &s) { int hash1 = Hash1()(s) % M; int hash2 = Hash2()(s) % M; int hash3 = Hash3()(s) % M; if (_bs.test(hash1) == false) return false; if (_bs.test(hash2) == false) return false; if (_bs.test(hash3) == false) return false; return true;// 也可能误判 }private: static const size_t M = 8*N; xp::bitset<M> _bs;// std::bitset<M> *_bs = new bitset<M>;// 也可以用库里面的};
2.4、布隆过滤器相关面试题
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。
答：精确算法使用哈希分割（哈希切分，下面讲）。近似算法使用布隆过滤器。
如何扩展BloomFilter使得它支持删除元素的操作。
答：使用多个位图进行对该位进行计数，但是会使得占用的内存变大。
3、哈希切分（哈希切割）
看这个问题：给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出精确算法。
我们假设一个请求（query）是50字节，那么100亿个请求，就是500亿字节，约等于50GB，一般来说50GB的文件内存是放不下的。
那么怎么处理呢？
我们可以讲这个50GB的文件使用哈希函数切分为文件大小不同的1000份小文件（初始是没有数据，只是创建了空文件，等待后续哈希函数映射进行插入数据），平均下来每个文件大小就是500MB。为什么是1000份？假设是切分为500小文件，那如果使用哈希函数时，有占用1GB以上的query放到一个小文件中，就会导致放不进内存。这种情况的概率是很大的。切分为1000份，这种情况的概率就会变小，但不保证0概率，就算某个小文件的大小大于1GB，也是可以解决的（再次切分，下面会讲）。
文字解释太生硬，下面直接看图：
问题：给一个超过100G大小的log 文件, log中存着IP地址, 设计算法找到出现次数最多的IP地址？如何找到top K的IP？
答：采用哈希切分，将这个100GB大小的文件切分大小不一为100个小文件（初始是没有数据，只是创建了空文件，等待后续哈希函数映射进行插入数据），对每个小文件使用map<string,int>（这里如果文件太大，map插入IP可能会出现异常，那么就换哈希函数进行二次切分），得到该文件出现次数最多的IP，再对比其他小文件文件的出现次数最多的IP，进行比较，得到整体出现次数最多的IP。找top K的IP只需要创建一个存K个元素的小堆，再依次对比插入。
4、海量数据处理
海量数据问题特征：数据量大，内存存不下
先考虑具有特点的数据结构能否解决。比如：位图、堆、布隆过滤器等等
大事化小思路。哈希切分（不能平均切分）切小以后，放到内存中能处理
OKOK，C++ 位图和布隆过滤器就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。
Xpccccc的github主页
